## References

### Previous summers

#### 2009

- Frank and Jiang,
“ New classes of
counterexamples to Hendrickson's global rigidity conjecture”,
*Discrete and Computational Geometry*. 45 (2010), no. 3, 574–591.

#### 2010

- Ahmed and George, “Rigidity in the one-dimensional projective space”.
- Jacobs, “Connecting global and universal rigidity”, arXiv:1011.4122.
- Park, “Searching for bipartite counterexamples to Hendrickson's global rigidity conjecture”. I'm told that there are one or two cases missing from the paper.
- Ratmanksi, “Universally rigid framework attachments”, arXiv:1011.4094.
- Sun and Ye, “Rigidity of graph joins and Hendrickson's conjecture”, arXiv:1011.3208.

### Background

The main background references we'll look at are the following. The links should all work within the Barnard/Columbia network; please e-mail me if you have any trouble.#### Local rigidity

- Laman,
“On
graphs and rigidity of plane skeletal structures”,
*Journal of Engineering Mathematics*, 4 (1970), 331–340. Gives the combinatorial charaterization of local rigidity in 2 dimensions. - Asimow and Roth, “The Rigidity of Graphs”,
*Transactions of the AMS*245 (1978), 279–289. Basic results on local versus infinitesimal rigidity, and rigidity of complete graphs. - Graver, Servatius, and Servatius,
*Combinatorial rigidity*, Graduate Stud. Math., Vol. 2, Amer. Math. Soc., Providence, RI, 1993, reviewed by W. Connelly.

#### Global rigidity

- Hendrickson, “Conditions for Unique Graph Realizations”, SIAM
*J. Comput.*21 (1992), 65–84. Gives two necessary (but not sufficient!) conditions for generic global rigidity. - Connelly, “On generic global rigidity”,
*DIMACS Ser. Discrete Math. Theoret. Comput. Sci.*4 (1991), 147–155 (Djvu, PDF). - Connelly, “Generic global rigidity”,
*Discrete Comput. Geom.*33 (2005), 549–563 (PDF). - Gortler, Healy, and Thurston,
“Characterizing
Generic Global Rigidity”, to appear in
*American Journal of Mathematics*.

#### Stresses, SDP, and universal rigidity

- Connelly, “Tensegrities and global rigidity” (PDF).
- Connelly, “Rigidity and Energy”,
*Inventiones Mathematicae*66 (1982), 11–33. - Gortler and Thurston, “Characterizing the universal rigidity of generic frameworks”, arXiv:1001.0172.
- Vandenberghe and Boyd,
“Semidefinite
programming”,
*SIAM Review*38 (1996) 49–95. - Freund, “Introduction to Semidefinite Programming”, Lectures at MIT, 2004.

#### Bipartite graph

- Bolker and Roth, “When is
a bipartite graph a rigid framework?”,
*Pacific Journal of Mathematics*90 (1980) 27–44. - Whiteley,
“Infinitesimal
motions of a bipartite framework”,
*Pacific Journal of Mathematics*110 (1984) 233–255.

#### Affine rigidity

- Gortler, Gotsman, Liu, and Thurston, “On affine rigidity”, arXiv:1011.5553.

#### Counting points

- Borcea and Streinu,
“The
number of embeddings of minimally rigid
graphs”,
*Discrete & Computational Geometry*,**31**(2004), no. 2, 287–303, arXiv:0207.5126.

#### Rigidity on torus

- Malestein and Theran, “Generic combinatorial rigidity of periodic frameworks”, arXiv:1008.1837.

#### Linkages

A linkage is a flexible framework; one nice result is that you can “sign your name” with a linkage.- Connelly and Demaine,
“Geometry
and Topology of Polygonal Linkages”, in
in
*CRC Handbook of Discrete and Computational Geometry*, Second Edition, 2004, chapter 9, pages 197–218. - King, “Planar linkages and algebraic sets”, arXiv:math/9807023.
- Kapovich and Millson,
“Universality
theorems for configuration spaces of planar
linkages”,
*Topology***41**(2002), 1051–1107.

#### Other references

- Saxe, “Embeddability of weighted graphs
in
*k*-space is strongly NP-hard”, Proc. 17th Allert Conf. Commun. Control Comput., 1979. - Hendrickson, “The
molecule problem: Exploiting structure in
global optimization”,
*SIAM J. Optim.*5 (1995), no. 4, 835–857. Here Hendrickson explicitly conjectures that his conditions are necessary and sufficient. Also has more background on practical applications. - Singer and Cucuringu, “Uniqueness of Low-Rank Matrix Completion by Rigidity Theory”.
- Davis, “Mosaics of scenes with moving objects”, IEEE Comp. Soc. Conf. on Computer Vision and Pattern Recognition (CVPR98), 1998.

### Textbooks

#### Linear algebra

- S. Axler,
*Linear Algebra Done Right*, Springer, 1997. - C. Meyer,
*Matrix Analysis and Applied Linear Algebra*, SIAM, 2001.

#### Differential geometry

- Michael Spivak,
*Calculus on Manifolds: A Modern Approach to Classical Theorems of Advanced Calculus*, Westview Press, 1971.

#### Graph theory

- Douglas B. West,
*Introduction to Graph Theory*, Prentice Hall, 2001. - Béla Bollobás,
*Modern Graph theory*, Springer, 1998.

#### Graph enumeration

Graph enumeration techniques are clever ways of listing all graphs with a given number of vertices. In the context of rigidity, the key will be to do the search cleverly and prune out partial graphs as quickly as possible. (I haven't yet been*Generating graphs*in the Stony Brook Algorithm Repository (and references there).- McKay,
“Practical
graph isomorphism”,
*Congressus Numerantium*,**30**(1981) 45–87. - McKay, “Isomorph-Free Exhaustive Generation”,
*Journal of Algorithms*,**26**(1998), 306–324.

#### Theory of computation

- M. Sipser,
*Introduction to the Theory of Computation*, Thomson Course Technology, 2001.

#### Geometry

- H. M. S. Coxeter,
*Projective Geometry*, Second edition, University of Toronto Press, 1974. A beautiful book, although it hardly mentions the cross-ratio. - H. M. S. Coxeter,
*Introduction to Geometry*, Second edition, Wiley, 1989. A fairly comprehensive book, including chapters on affine and projective geometry.

#### Algebraic Geometry

This is a huge subject, and you should try not to get too bogged down in it&dots; But these references at least have the basic definitions.- I. R. Shafarevich,
*Basic Algebraic Geometry I*, translated by M. Reid, Springer-Verlag, 1995. - M. Artin,
*Algebra*, Prentice-Hall, 1991 has a short discussion of algebraic geometry in Section 10.8. You'll also need material from earlier on, particularly Section 10.7. - R. Hartshorne,
*Algebraic Geometry*, Springer-Verlag, 1977. This is a standard reference, but is likely to make your head spin. - J. Bochnak, M. Coste, M. Roy,
*Real Algebraic Geometry*, Springer, 1998. Real algebraic geometry has a rather different flavor than standard algebraic geometry, which works over the complex numbers, and this (rather thick) book explains it.

### Programs

The program from last summer by Frank and Jiang is available here (in .tar.gz format; let me know if you have problems.) Of particular interest even to non-programmers are their detail results, listing all the (many) counterexamples to Hendrickson's conjecture that they found.### Writing

When you get to writing up your results, the following references will be useful:- Landes, A Scrutiny of
the Abstract, II, Bulletin of the American Association of
Petroleum Geologists,
**50**(1966), 1992–1999. - “The Not So Short Introduction to LaTeX”, by Oetiker et al, is a good introduction to LaTeX. Despite the name, it is not very long.
- The source code for the paper from 2009 is good to take a look at. (It's also available, including the figures, from the arXiv.)