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.

1. 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.
   
2. 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.
   
3. This is a result with Shlomo Gortler and Louis Theran that proves the rigidity of sticky circles for generic radii.
4. 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.
   
5. 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. 
6. 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.
7. 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.
8. 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.
9. This is a result, with Shlomo Gortler,  that characterizes the universal rigidity of complete bipartite graphs in all cases in all dimensions.
10. 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.
11. This is a paper with Luis Montejano that all the ways that a rigid triangle can slide along with its vertices on straight lines.
12. This is a paper, to appear in Discrete and Computational Geometry, with Shlomo Gortler that describes ALL universally rigid frameworks and tensegrities.
13. 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.
14. This is a paper, with Tibor Jordan and Walter Whiteley, that characterizes generic global rigidity for bar-and-body frameworks in any dimension.
15. 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.
16. 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.
17. 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.
18. 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.
19. These are the slides of a talk I gave at the Fields Institute in Toronto, in October about packings in a triangular torus.
20. 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.
21. 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.
22. Here is a power point talk that I gave at NYU on November 3, 2009 that describes some of the events concerning global rigidity.
23. 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.
24. The basics of the global rigidity of tensegrities are explained here, especially in terms of the stress matrices.
25. 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. 
26. 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)
27. 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.
28. 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.
29. 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.
30. This is a link to an update of the tensegrity catalog. It is more extensive and shows many more possibilities than the older one.
31. This is a little survey paper on packings in the spirit of L. Danzer's Habilitationsschrift about the rigidity of packings.
32. Here is a survey paper on Expansive motions, where expansive motions of graphs in the plane with fixed edge lengths are discussed.
33. 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.
34. 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.
35. 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.)
36. 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.
37. 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.
38. 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.
39. 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.
40. 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
41. 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.
42. ``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.
43. 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.
44. 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.
45. 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.
46. 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.
47. ``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.
48. "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).
49. 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.


50. `` 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.
51. "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.
52. "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.
53. "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.
54. 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.
55. "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.
56. 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.
57. 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.
58. 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).
59. 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.
60. 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 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.

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