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.
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.
- 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
- Connelly, “Generic global rigidity”, Discrete Comput. Geom. 33
- Gortler, Healy, and Thurston,
Generic Global Rigidity”, to appear in American Journal of
Stresses, SDP, and universal rigidity
- Connelly, “Tensegrities and global rigidity”
- Connelly, “Rigidity and Energy”, Inventiones Mathematicae 66
- Gortler and Thurston,
the universal rigidity of generic frameworks”,
- Vandenberghe and Boyd,
programming”, SIAM Review 38 (1996) 49–95.
- Freund, “Introduction to
Semidefinite Programming”, Lectures at MIT, 2004.
Rigidity on torus
A linkage is a flexible framework; one nice result is that you can
“sign your name” with a linkage.
- Connelly and Demaine,
and Topology of Polygonal Linkages”, in
Handbook of Discrete and Computational Geometry, Second
Edition, 2004, chapter 9, pages 197–218.
and algebraic sets”, arXiv:math/9807023.
- Kapovich and Millson,
theorems for configuration spaces of planar
Topology 41(2002), 1051–1107.
- 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,
Here Hendrickson explicitly conjectures that his conditions are
necessary and sufficient. Also has more background on practical
- Singer and Cucuringu, “Uniqueness of Low-Rank Matrix
Completion by Rigidity Theory”.
of scenes with moving objects”, IEEE Comp. Soc. Conf. on
Computer Vision and Pattern Recognition (CVPR98), 1998.
- S. Axler, Linear Algebra Done Right, Springer, 1997.
- C. Meyer, Matrix Analysis and Applied Linear Algebra,
- Michael Spivak, Calculus on Manifolds: A Modern Approach to
Classical Theorems of Advanced Calculus, Westview Press, 1971.
- Douglas B. West, Introduction to Graph Theory, Prentice
- Béla Bollobás, Modern Graph theory, Springer, 1998.
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
Theory of computation
- M. Sipser, Introduction to the Theory of Computation,
Thomson Course Technology, 2001.
- 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.
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
- 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
- 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.
The program from last summer by Frank and Jiang is
(in .tar.gz format;
let me know if you have problems.) Of particular interest even to
non-programmers are their
, listing all the (many)
counterexamples to Hendrickson's conjecture that they found.
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.
Not So Short Introduction to LaTeX”, by Oetiker et al,
is a good introduction to LaTeX. Despite the name, it is not very
- The source code for the
paper from 2009 is good to take a look at. (It's also
available, including the figures, from