Home Page for Bob Connelly
Department of Mathematics
Malott Hall, Room 433
Cornell University
Ithaca, NY 14853
e-mail: connelly@math.cornell.edu
Telephone: (607) 255-4301 (voice mail available)
Office Hours: Wednesdays 1:30-2:15 in 433 Malott.
Last Updated: January 24, 2014
Discrete Geometry and
Combinatorics Seminar, Spring 2014. If you would like to talk, please
get in touch with Lou Billera, Ed Swartz or me.
My whereabouts: I am at Cornell.
Prove it! Math 3040
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.
- This is a paper with
Zach Abel, Sarah Eisenstat, Radoslav Fulek, Filip Moric, Yoshio
Okamoto, Tibor Szabo, and Csaba Toth, which shows when for a given
cycle with given edge lengths, there is an embedding in the plane that
extends to an ebedding in the plane to a larger graph that contains it,
where the lengths of the other edges are not constrained.
- This is a paper, with
Tibor Jordan and Walter Whiteley, that characterizes generic global
rigidity for bar-and-body frameworks in any dimension.
- This
is a little result, with Luis Montejano, that shows that the only way a
rigid body can move such its vertices stay on fixed straight lines is
when it is part of a hypercycloid motion of one circle (or cylinder)
rolling in another of twice the diameter.
- This
is a paper with Jeff Shen and Alex Smith in an REU program in the
summer of 2012 which gives information about periodic jammed packings
on a torus particularly with respect to the situation with finite
coverings.
- This is a paper with Victor
Alexandrov about flexible suspensions that do not preserve the Dehn
invariant. Illinois J. Math. Volume 55, Number 1 (2011), 127-155.
- This is
a
paper is a paper with Will Dickinson where we consider packings of
equal circles in a triangular torus. This motivated by a
conjecture of Laszlo Fejes T\'oth about finite rearrangements of a
triangular packing of disks in the plane. This has appeared in
the Philosophical Transactions of the Royal Society, Rigidity of
periodic and symmetric structures in nature and engineering, ``Periodic
Planar Disk Packings", with Will Dickinson, volume 372, number 2008,
Article ID 201020039.
- These are the slides of a talk I gave at the Fields Institute in Toronto, in October about packings in a triangular torus.
- A semester long thematic program at the Fields Institute
in Toronto, Canada on Discrete Geometry and Applications was held
from July 2012 to December 2012. There were several workshops,
graduate courses, and special lectures. Check it out.
- Combining Globally Rigid Frameworks
is a paper that I have submitted. It is about a method of
creating new generically globally rigid frameworks from old ones in Proc. Steklov Inst. Math. 275 (2011), no. 1, 191–198.
- Here is a power point talk that I gave
at NYU on November 3, 2009 that describes some of the events
concerning global rigidity.
- The background of the geometry related to stress matrices as well
as some questions for a "get-together" in July
2009 in Budapest, Hungary are explained Questions, Conjectures and Remarks on Globally Rigid Tensegrities.
- The basics of the global rigidity of tensegrities are explained here, especially in terms of the stress
matrices.
- This paper with Walter
Whiteley shows how generic global rigidity for bar frameworks is equivalent
to the coned graph being generically globally rigid in one higher dimension.
- Here is a simple page of Maple script to detect generic rigidity
and generic global rigidity for any graph in any dimension as mentioned
above. This is the basic code, and this is a sample page to construct the graphs.
This is just Maple text which should work for your Maple software. This
is an algorithm described in S. Gortler, A. Healy, and D. Thurston: Characterizing
generic global rigidity, arXiv:0710.0907v1. (2007)
- Here is paper with K. Bezdek,
and B. Csikos where show that the Kneser-Poulsen property for the perimeter
of the intersection of four congruent disks. This is in contrast to the
case for unions of several disks.
- Here is a paper "When is a symmetric pin-jointed
framework isostatic?", with P. W. Fowler, S. D. Guest, B. Schulze, and W.
J. Whiteley, in the International Journal of Solids a Structures, 46 (2009)
763-773. This answers the question in the title for several examples of
symmetry groups in dimensions 2 and 3.
- When the disks in the Kneser-Poulsen theory are replaced by appropriate
distributations, one can use the standard Kneser-Poulsen theory to expand
its applicability. See my paper with Károly
Bezdek about this property.
- This is a link
to an update of the tensegrity catalog. It is more extensive and shows many
more possibilities than the older one.
- This is a little survey paper on packings
in the spirit of L. Danzer's Habilitationsschrift about the rigidity of
packings.
- Here is a survey paper on Expansive motions,
where expansive motions of graphs in the plane with fixed edge lengths are
discussed.
- 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.
- 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.
- 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 suspensions with the natural decompositon. (This is also
available on the Math ArXiv.)
- 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.
- 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.
- 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.
- 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.
- 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
- 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.
- ``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.
- 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^{n} 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.
- 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.
- 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.
- 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.
- ``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.
- "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.
- `` 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.
- "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.
- "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.
- "The Rigidity of Certain Cabled Frameworks
and the Second-Order Rigidity of Arbitrarily Triangulated Convex Surfaces."
The title is the theorem. This also shows that polyhedra in 3-space with
convex holes in the interior of their faces are second-order rigid, and therefore
rigid when triangulated. It is also possible to show that these frameworks
are prestress stable, a somewhat stronger result.
- "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.
- 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.
- 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.
- 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).
- 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.
- 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.
Symmetric Tensegrities
The updated and more comprehensive catalog created by Allen Back, Bob Terrell and me is
here.
You can view rotatable pictures of symmetric tensegrities, but you must
bear with four choices before you see any picture. These are
geometrically stable structures that can be constructed with
incompressible sticks suspended in mid-air with inextendable
cables. Allen Back and I have a paper where some of the theory is
described in the March-April
1998 issue of the American Scientist. Here
is a copy of that paper. Here is a brief overview of the catalog.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
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.
Math 294, Fall 2000, home page
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.
Some of my old courses:
- 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.
My courses Spring 2001:
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.
Spring 2008 Teaching: Math 304, Prove it! 10:10-11:25
Tue. Thurs. Malott 224;
Math 452, Classical
Geometries, 2:55-4:10 Tue. Thurs. Malott 230.
Discrete
Geometry and Combinatorics Seminar, Archives
Spring 2009 course: Math 7620
Fall 2009 course: Math 1910
Fall 2010 course: Math 1920 Engineering Calculus
This link is to the Blackboard site. You need to log in to get the information.
Spring of 2012: Math 3040, Prove it!
Research Experience for Undergraduates (REU) at Cornell (Summer 2012): This is Project 2.
Fall 2012: Math 1920
Link to Cornell Mathematics
home page
Link to CUinfo