Recent and Favorite Papers and links   

    If you would like a paper version of any of the following, please e-mail me, and I will send you a copy by snail mail or a scanned pdf copy.

1. This is a little survey paper on packings in the spirit of L. Danzer's Habilitationsschrift.
   
2. Here is a survey paper on Expansive motions, where expansive motions of graphs in plane with fixed edge lengths are discussed.
   
3. When you have a jammed packing of spherical, frictionless particles, in any sort of reasonable container, the number of contacts must at least match the number of free variables.  This is what I call the "canonical push".  But this argument fails when the particals are frictionless but not round, and indeed for all but the most well-ordered packings, the number of contacts is significantly less than the number of free variables.  This is called a hypostatic configuration, since it is not statically (or infinitesimally) rigid, behaving like an underconstrained tensegrity that is prestress stable.  This is discussed in terms of granular materials here, with Aleks Donev, Sal Torquato, and Frank Stillinger. 
   
4. When a polygonal chain opens by expansion, and interesting question is how much other "stuff" can you stick on to the chain and still be sure that these "adornments" will not interfere with the opening motion?  It turns out that there is a very natural set of objects that are examples of "flowers" as defined by Gordon and Meyer and used in my Kneser-Poulsen papers with K. Bezdek.  This is explained in the paper here with Erik Demaine, Martin Demaine, Sándor Fekete, Stefan Langerman, Joseph S. B. Mitchell, Ares Ribó, and Günter Rote.  See also my presentation here. 
   
5. Jean-Marc Schlenker proved that, given a polyhedron in three-space, if it has all its vertices outside a ellipsoid, all its edges intersect the interior of the ellipsoid, and can be decomposed into a triangulation of its interior without adding new vertices, then it is infinitessimally rigid in three-space.  The ellipsoid condition is necessary for his proof, since techniques from hyperbolic geometry are used, but he conjectured that the ellipsoid condition is not necessary, only that the vertices all lie on the convex hull as extreme points.  Here we prove it for suspentions with the natural decompositon.  (This is also available on the Math ArXiv.)
   
6. In Oberwolfach, Spring 2006, I gave a talk about stress matrices, where I outlined the proof of K. Bezdek's conjecture that if a tensegrity has cables along the edges of a convex centrally symmetric polyhedron, and struts connecting antipodal vertices, then it is globally rigid and superstable.  This relies on a result of L. Lovasz concerning M-matrices.  The idea is that M-matrices can be converted, in this case, to stress matrices.  This is the moderately extended abstract with K. Bezdek.
   
7. Serge Tabachnikov studied the geometry of the tracks of bicycles, defined a polygonal analogue, and conjectured the discrete solutions to equations related to the rigidity of these polygons.  Balazs Csikos solved these equations, with a minor assist from me, in this paper.
   
8. The Sudoku puzzle has become quite popular in newspapers and magazines.  I always thought that it should have some relation to the geometry of linear subspaces over finite fields, as is the case with orthogonal latin squares.  Here is a paper to appear in the American Mathematical Monthly where such a connection is made and put in a wider context and applied to statistics with my coauthors Peter Cameron and R. A. Bailey.
   
9. Springer has translated the book on convex polyhedra by A. D. Alexandrov into English with updates and notes by Zallgaller as well as appendices clarifying a lot of the proofs.  Here is review that I did for SIAM Reviews.
   
10. The following are some lectures of mine that I gave at the Institut Henri Poincaré in March 2005 for the conference on granular materials. You can see other lectures here. The following are pdf versions of my power point talks plus references.
    The basics of rigidity (lectures I and II)
    Packings of circles and spheres (lectures III and IV)
    Percolation (lecture V)
    Prestress stability (lecture VI)
    References
    
11. Realizability of Graphs with Maria Sloughter (now Maria Belk). If the vertices of a graph G form a configuration in Euclidean N-space, when can you find another configuration in 3-space where the edges G have the same (straight line) length as they did in N-space? We give a complete answer to this question.
12. ``Improving the Density of Jammed Disordered Packings using Ellipsoids'' by Aleksandar Donev, Ibrahim Cisse, David Sachs, Evan A. Variano, Frank H. Stillinger, Robert Connelly, Salvatore Torquato and P. M. Chaikin, Science, 303:990-993, 2004. Randomly packed ellipsoids (m&ms) pack more densly than spherical balls (gumballs). abstract.
13. The Kneser-Poulsen conjecture for spherical polytopes. Discrete Comput. Geom. 32 (2004), no. 1, 101--106. If a finite set of balls of radius  pi/2 (hemispheres) in the unit sphere Sⁿ is rearranged so that the distance between each pair of centers does not decrease, then the (spherical) volume of the intersection does not increase, and the (spherical) volume of the union does not decrease. This result is a spherical analog to a conjecture by Kneser (1954) and Poulsen (1955) in the case when the radii are all equal to  pi/2.
    
14. Pushing disks apart---the Kneser-Poulsen conjecture in the plane. with K. Bezdek J. Reine Angew. Math. 553 (2002), 221--236. We give a proof of the planar case of a longstanding conjecture of Kneser (1955) and Poulsen (1954). In fact, we prove more by showing that if a finite set of disks in the plane is rearranged so that the distance between each pair of centers does not decrease, then the area of the union does not decrease, and the area of the intersection does not increase.
    
15. Generic Global Rigidity, (Discrete Comput. Geom., Volume 33, Number 4, April 2005, pages 549-563). This is a proof of the stress matrix criterion that is a sufficient condition for a framework, whose configuration is generic, to be globally rigid in Euclidean space. An application of this implies that a combinatorial condition on the graph is sufficient to insure global rigidity. A framework G(p) is globally rigid in Euclidean d-dimensional space if any other configuration q of the same labeled points in Euclidean d-dimensional space has the same edge lengths for the pairs of points that correspond to the graph G, then q is congruent to p. This together with recent results of Jordan and Sullivan give a complete combinatorial characterization of generic global rigidity in the plane.
16. Comments on Generalized Heron Polynomials and Robbins' Conjectures. If a polygon in the plane has its vertices lie on a circle, the area it bounds is a root of a polynomial whose coefficients are themselves polynomials in the lengths of its edges. David Robbins conjectured what the degree of the minimal polynomial was and that it was monic. Now his conjectures are known, and this paper gives an easy proof (using the theory of places) that the polynomial is monic.
17. ``A Linear Programming Algorithm to Test for Jamming in Hard-Sphere Packings'', by A. Donev, S. Torquato, F. H. Stillinger, and R. Connelly, J. Comp. Phys, 197 (1):139-166, June 2004. Jamming in hard sphere and disk packings, Journal of Applied Physics, by Aleksandar Donev, Salvatore Torquato, Frank H. Stillinger, Robert Connelly, vol. 95, No. 3, February, 2004.
18. "Straightening Polygonal Arcs and Convexifying Polygonal Cycles" (joint with Erik Demaine and Günter Rote) in Discrete and Computational Geometry, Vol. 30, No. 2, (Sept. 2003), 205-239).
    
Abstract: This is a solution to the infamous "Carpenter's Ruler" problem. Consider any polygonal arc or polygonal simple closed cycle, embedded in the plane. We show that there is continuous motion of the arc or cycle (a flex) preserving the lengths of edges and not having any self intersections, such that at the end, the arc is straight or the cycle is convex. Furthermore it is possible to do this flex in such a way that all pairs of vertices increase their distance except those that lie along a straight line segment of the arc or cycle. This also can be done on any finite collection of arc and cycles as long no cycle contains another arc or cycle in its bounded component. Several people attempted to define examples of arcs or cycles that were "locked" and could not be opened. But they were all able to be opened. See the animation on Erik's linkage page, where there are some interesting examples are flexed open and there are extended abstracts.

19. `` The Bellows Conjecture ,'' , joint with I. Sabitov and A. Walz in Contributions to Algebra and Geometry , volume 38 (1997), No.1, 1-10. (local version). This is joint work with I. Sabitov and A. Walz. Consider a polyhedral surface in three-space that has the property that it can change its shape while keeping all its polygonal faces congruent. Adjacent faces are allowed to rotate along common edges. Mathematically exact flexible surfaces were found by Connelly in 1978. But the question remained as to whether the volume bounded by such surfaces was necessarily constant during the flex. In other words, is there a mathematically perfect bellows that actually will exhale and inhale as it flexes? For the known examples, the volume did remain constant. Following an idea of Sabitov, who provided the first proof, but using the theory of places in algebraic geometry (suggested by Steve Chase), we show that there is no perfect mathematical bellows. All flexible surfaces must flex with constant volume.
    One of the tools used in our proof above was the theory of places. Places are closely related to (essentially equivalent to) the theory of valuations. See the valuation theory homepage for more information about the present activity in the theory of places. See also the Mathematical Recreations column of the July 1998 issue of the Scientific American by Ian Stewart. See the Oliver Club Announcement to see what a bellows looks like.
20. "Tensegrity Structures: Why are they Stable?" (in Rigidity Theory and Applications, edited by Thorpe and Duxbury, Kluwer/Plenum Publishers (1999) pages 47-54.) This is a brief introduction to some tensegrity and stress techniques, with some examples.
    
21. "Second-Order Rigidity and Prestress Stability for Tensegrity Frameworks", (joint with Walter Whiteley, SIAM J. Discrete Math, Vol. 9, No. 3, pp. 453-491, August 1996. This describes several flavors of rigidity for structures that are held together with inextendable cables and incompressible struts. One application of the techniques in this paper is to prove a conjecture of B. Roth. This says that if convex polygon in the plane has struts on the external edges and cables for some of the internal diagonals and it is rigid in the plane, then it is infinitesimally rigid.
22. "Rigidity and Energy", (Rigidity and energy. Invent. Math. 66 (1982), no. 1, 11--33.) This is an early paper describing how energy methods can be used to show (global) rigidity with the use of the quadratic form coming from the stress matrix. An application of these techniques provides a proof of some of Grünbaum's conjectures about the rigidity of planar convex polygons with cables as exterior edges and struts as diagonals.
23. The following is a link to the web page of Allen Fogelsanger, my former student.  There you can download his thesis "The Generic Rigidity of Minimum Cycles", which sadly was never published.  Here is it is shown, as a very special case, that any triangulated 2-dimensional closed manifold is generically rigid in 3-space, a problem that was open for some years before his result.
    
24. The following are handwritten notes, taken by Maria Belk, of a course in 2002 I taught on the theory of rigid structures.  This is one place to look for an introduction to the subject.  Rigidity Notes Part I.  Rigidity Notes Part II.
25. In 1987 there was an abortive attempt to write a book on the theory of rigid structures.  The following are copies of rough drafts of selected chapters with the authors indicated.  Chapter 1 (an introduction by Ben Roth), Chapter 2 (infinitesimal rigidity by me), Chapter 3 (static rigidity by me), Chapter 4 (rigidity of convex surfaces by Ben Roth), Chapter 10 (on tensegrity by Walter Whiteley), Chapter 16 (on global rigidity and tensegrity by Walter Whiteley).
    
26. An Attack on Rigidity I and an Attack on Rigidity II are two of my early papers, never fully published in English.  They deal with the rigidity of suspensions.  These are frameworks constructed by taking a closed polygon, and equator, in Euclidean 3-space together with two additional vertices N and S that are each connected by bars to the equator.  If such a suspension flexes with the distance between N and S changing, then the volume enclosed is zero (not just constant).  There are other goodies such as a classification of such flexible suspensions using elliptic curves, and there are some examples of piecewise smooth flexible and rigid suspensions in other categories.  Here is a translation of the above into Russian.
27.  If you would like to build a genuinely flexible sphere, here is a one-page simple easy-to-follow set of instructions of an example by Klaus Steffen (following my example) with 9 vertices and 14 triangles. This is the smallest flexible embedded example that I know of and is a copy of the original handwritten copy that was circulated at I.H.E.S. in France about 1977.  
    

Tensegrities: Here you can view a few pictures of symmetric tensegrities. These are geometrically stable structures that can be constructed with incompressible sticks suspended in mid-air with inextendable cables. This is joint work with Allen Back, and is described in the March-April 1998 issue of the American Scientist.  Here is a copy of that paper. You can view the catalog of over 100 different stable symmetric tensegrity structures constructed with cables and struts.

I am in Ithaca, NY.

OLD NEWS:

The summer of 2001

In the summer of 2001, we had an informal seminar on discrete geometry and graph theory concerning various topics. Here is a list of talks and speakers.

The summer of 2000

In the summer of 2000, we had an informal seminar on discrete geometry and graph theory concerning the following topics: The Colin de Verdiere graph invariant, Stress matrices, global rigidity, symmetric polyhedra. For more information go to the summer seminar web page.

• Math 452, Classical Geometries, Spring 1998: This is a senior-level undergraduate course on the virtues of perspective, projective geometry and hyperbolic space among other geometric topics.
• Math 661,Discrete Geometry, Distance Geometry and Rigid Structures, Fall 1998: A graduate course discussing rigidity, tensegrity, and some of the topics mentioned above.

Math 191, Spring 2001, home page

Math 762, Spring 2001, Discrete geometry and graph theory, course description and homepage.

Math 452, Spring 2003, home page.

Math 191, Fall 2003

This semester we were experimenting with some on-line questions that students some sections of Math 191 were to do before class on material that were covered in that class.

Note that the syllabus of Math 191 has changed starting the Fall of 2004.

Courses I taught, Fall 2004:

Math 335 (= Com S 480): Cryptography
Math 441: Combinatorics

Spring 2007 Teaching:  Math 401, Tue.,Thurs. 2:55-4:10 in Malott 224 and Math 651, Tue. Thurs. 1:25-2:40 in Malott 224.

Fall 2007 Teaching:  Math 221, MWF 11:15-12:05 in Malott 251.

Last Updated:  January 23, 2008