Home Page for Bob Connelly
Department of Mathematics
Malott Hall, Room 565
Cornell University
Ithaca, NY 14853
e-mail: connelly@math.cornell.edu
Telephone: (607) 255-4301 (voice mail available)
Office Hours: Tuesday-Thursday 10:00-11:30 in 565 Malott.
Last Updated: January 10, 2020
Discrete Geometry and Combinatorics Seminar, Spring 2020 If you would like to talk, please get in touch with Ed Swartz or me.
This Spring 2020 I am the Czar of Math 1120, the second course in Calculus.
My whereabouts: I am at Cornell.
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 Shlomo Gortler that shows that any packing whose graph is a
triangulation of a triangle can be obtained by flipping edges and
flowing continuously from on triangulation to the next. This
gives a new proof of, and an algorithm for, an old result of
Koebe, Andreev, Thurston.
- This is a result
with Maurice Pierre that improves an esitmate for the largest ratio of
disks of a triangulated packing in the plane using a result of Thomas
Fernique.
- This is a result with Shlomo Gortler and Louis Theran that proves the rigidity of sticky circles for generic radii.
-
This is
a result with Shlomo Gortler, Evan Solomonides and Maria
Yampolskaya that proves the isostatic conjecture which says that for a
jammed packing of disks with generic radii in an appropriate generic
toroidal container, then thre are a minimum number of contacts among
the disks. This is appear in a special issue of Discrete and
Computational Geometry in honor of Ricky Pollack.
-
This
is a result with Shlomo Gortler and Louis Theran that shows that
condition that when a framework is univerally rigid, the condition that
there be no affine flexes is even weaker than one might expect.
-
This
is a result with Shlomo Gortler and Louis Theran that shows when a
framework is generically globally rigid in a given dimension, then it
has certificate that is both universally rigid and infinitesimally
rigid.
-
This
is a result with Matthew Funkhouser, Vivian Kuperberg, Evan
Solomonides. We have conjectures about the most dense packings of
certain numbers of equal disks in a square torus, using continued
fraction approximations to 1/sqrt{3} and 2-sqrt{3} as well as a
charactization of all grid-like rigid packings of equal disks in a
square torus. This is to appear in Discrete and Combinatorial
Geometry.
-
This
is a result, with Shlomo Gortler, universal second-order rigidity
implies universal prestress stability and that triangulated convex
polytopes in three-space (with holes appropriately positioned) are
prestress stable. This proves some of the results claimed in
Rigidity. Handbook of convex geometry, Vol. A, B, 223–271,
North-Holland, Amsterdam, 1993, and extends and simplifies those
results.
-
This
is a result, with Shlomo Gortler, that characterizes the
universal rigidity of complete bipartite graphs in all cases in all
dimensions.
-
I gave some lectures, Flavors of Rigidity, at the University of Pittsburgh about rigidity theory in October 2014. Lecture 1 local and infinitesimal rigidity, Lecture 2 global rigidity, Lecture 3 universal rigidity and tensegrities, Lecture 4 realizations of frameworks.
-
This is a paper with Luis Montejano that all the ways that a rigid triangle can slide along with its vertices on straight lines.
-
This
is a paper, to appear in Discrete and Computational Geometry, with
Shlomo Gortler that describes ALL universally rigid frameworks and
tensegrities.
-
This is
a paper with Zach Abel, Sarah Eisenstat, Radoslav Fulek, Filip Moric,
Yoshio Okamoto, Tibor Szabo, and Csaba Toth, Free edge lengths in
plane graphs in Discrete Comput. Geom. 54 (2015), no. 1, 259–289, 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 Sn
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.
-
Globally Rigid Symmetric Tensegrities,
in Structural Topology, 21, (1995), with Maria Terrell, shows the
universal rigidity of tensegrities that have dihedral symmetry in
3-space, with one transitivity class of vertices, 2 classes of cables,
and one class of struts.
-
"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