THEMATIC PROGRAMS

September 19, 2018

October Workshops Proposed talk titles and abstract submissions. Accepted talks will be 20 to 30 minutes in length.

 SEPTEMBER WORKSHOPS Back to Main index October 11-14, 2011 Workshop on Rigidity October 17-21, 2011 Workshop on Rigidity and Symmetry October 24-27, 2011 Workshop on Symmetry in Graphs, Maps and Polytopes

October 11-14, 2011 Workshop on Rigidity

Alfakih, Abdo Y.
On the Universal rigidity of bar frameworks in general position

A bar framework G(p) in r-dimensional Euclidean space is a graph G whose vertices are points p1, p2,.., pn in R^r, and whose edges are line segments connecting pairs of these points. A given framework G(p) in R^r is said to be universally rigid if there does not exist a non-congruent framework G(q) in any Euclidean space with the same edge lengths as those of G(p). A framework G(p) in R^r is generic if the coordinates of p1,...,pn are algebraicaly independent over the integers. On the other hand, G(p) is in general position in R^r if there is no subset, of cardinality r+1, of the points p1, ...,pn that is affinely dependent. It is known that a generic framework G(p) on n vertices in R^r is universally rigid if and only if G(p) admits a positive semi-definite stress matrix of rank n-r-1. In this talk, I’ll show that the "if" part of this result still holds under the weaker assumption of a framework in general position. Universal rigidity has many important applications in molecular conformation and wireless sensor networks.
(This is a joint work with Yinyu Ye).

Bezdek, Karoly
Rigid ball-polyhedra in Euclidean 3-space

A ball-polyhedron is the intersection with non-empty interior of finitely many (closed) unit balls in Euclidean 3-space. One can represent the boundary of a ball-polyhedron as the union of vertices, edges, and faces defined in a rather natural way. A ball-polyhedron is called a simple ball-polyhedron if at every vertex exactly three edges meet. Moreover, a ball-polyhedron is called a standard ball-polyhedron if its vertex-edge-face structure is a lattice (with respect to containment). To each edge of a ball-polyhedron one can assign an inner dihedral angle and say that the given ball-polyhedron is rigid with respect to its inner dihedral angles if the vertex-edge-face structure of the ball-polyhedron and its inner dihedral angles determine the ball-polyhedron up to congruence locally. The main result of this talk is a Cauchy-type rigidity theorem for ball-polyhedra stating that a simple ball-polyhedron is rigid with respect to its inner dihedral angles if and only if it is a standard ball-polyhedron. This is a joint work with M. Naszodi (Eotvos Univ., Budapest).

Cheng, Jialong and Sitharam, Meera
Better Estimates of 3D rigidity

Maxwell's condition states that the edges of a graph are independent in its d-dimensional generic rigidity matroid only if (a) the number of edges does not exceed d|V| - {d+1 choose 2}, and (b)this holds for every induced subgraph. Such graphs are called Sparse orMaxwell-independent in d-dimensions.Laman's theorem shows that the converse holds in 2D. While the converse is false in 3D, we answer the following questions in the affirmative. The first question was posed by Tib'or Jord'an at the 2008 rigidity workshop at BIRS.
We consider the following questions.
Question 1:Does every maximal, Maxwell-independent set of a graph have size at least the rank?
Question 2: Is there a better and tractable combinatorial upper bound (than the number
of edges) for Sparse or Maxwell-independent graphs?We give affirmative answers to both questions. As one consequence, the answers also give simpler proofs of correctness for existing algorithms
that give rank bounds.

Connelly, Bob Cornell University
Rigidity, tensegrities, and some applications

The theory of rigid structures has been developed greatly over the last fifty years or so. This will be a discussion of some of the main results and the main concepts. One important thing is what is the definition of rigidity? Local rigidity, global rigidity, infinitesimal rigidity, static rigidity, and uniform rigidity all are good examples of definitions that are possible. I will discuss what these mean and show some of the connections and applications. Another important thing is what are the objects that are rigid. There are bar-and-joint frameworks, tensegrities, packings, bar-and-body frameworks, and body-hindge, for example. This is a background and preview of many of the talks to come.

Crapo, Henry
Isostatic Graphs and Semi-simplicial Maps

Following work initiated by Tiong Seng Tay, we know that a graph $G$ is generically isostatic in dimension $D$ if it has a shellable semi-simplicial map $f$ to the $D$-simplex $K_{d+1}$. The converse is known only for $D=1,2$. We of course concentrate on the case $D=3$. In a semi-simplicial map to $K_4$, incidence must be preserved: edges whose end vertices go to the same vertex, say $j$, we call a {\it loop at $j$}, which must be sent to an edge of $K_4$ incident to $j$. We also insist that the inverse image $f^{-1}(ij)$ of any edge $ij$ of $K_4$ be a {\it tree} connecting the vertex set $f^{-1}(i)\cup f^{-1}(j)$. A map is {\it shellable} if and only if, starting from the degenerate placement of the graph as its image under $f$, {\it in} the tetrahedron, the vertices can be gradually separated without making discontinuous change in edge directions. A simple proof shows that the existence of a shellable semi-simplicial map $F:G\to K_4$ implies $G$ is $3$-isostatic. It is not known whether every $3$-isostatic graph has such a shellable map. But "normally" there are so many you would not want to bother to count them.
Computer programs, which I write in Python, can establish that a given graph is isostatic, and quickly so, simply because so many shellable maps exist. But such programs are virtually useless in showing that a 3v-6 graph is dependent, since we must wait until the dreary end of the computation, only to find that there are no shellable maps, \dots and even then not to be sure of dependency, since there is no such theorem proven.
The situation is very similar to that encountered when using Henneberg reduction (and for good reason).
In this talk we describe recent work to cut down the search for maps, and to eliminate the need to produce shellings, by concentrating on maps in which non-shellable vertex packets (inverse images of a single vertex) can not occur: those in which vertex packets induce subgraphs having no cycles. Such maps are {\it "freely shellable"}. Roger Poh has proven that for any planar graph there is a partition of its vertices into no more than three parts, each part inducing a path as subgraph. Such partitions are not necessarily vertex partitions under inverse image of a semi-simplicial map. But since maximal planar graphs are generically $3$-isostatic, we are still led to conjecture that isostatic graphs share similar properties. We conjecture:{\it A graph G is generically $3$-isostatic graph if and only if it has a semi-simplicial map to the tetrahedron in which all vertex packets induce subgraphs that are broken paths (forests with all vertices of valence $1$ or $2$).}
This conjecture is false if you insist that the induced subgraphs be paths. As an example, consider a hinged ring of six tetrahedra.

Time permitting (or on another occasion during the week) we should discuss computational methods for constructing the generically 3-rigid {\it components} of an arbitrary graph, or for finding dependencies.

Dickinson, William Grand Valley State University
Packings of Equal Circles on Flat Tori

We outline an algorithm to find all the locally maximally dense packings of a fixed number of equal circles on any flat torus. The algorithm uses the tools of rigidity theory and topological graph theory. We have applied this to the case of 3 equal circles and have determined all the locally maximally dense packings on any flat torus in this case. We have also applied this on upto six equal circles on certain flat and have determined some other optimal arrangements. This is joint work with AnnaVictoria Ellsworth and Jennifer Kenkel.

Erik Demaine, Massachusetts Institute of Technology
Linkage Folding: From Erd\H{o}s to Proteins

Linkages have a long history ranging back to the 18th century in the quest for mechanical conversion between circular motion and linear motion, as needed in a steam engine. In 1877, Kempe wrote an entire book of such mechanisms for "drawing a straight line". (In mathematical circles, Kempe is famous for an attempted proof of the Four-Color Theorem, whose main ideas persist in the current, correct proofs.) Kempe designed many linkages which, after solidification by modern mathematicians Kapovich, Millson, and Thurston, establish an impressively strong result: there is a linkage that signs your name by simply turning a crank.

Over the years mathematicians, and more recently computer scientists, have revealed a deep mathematical and computational structure in linkages, and how they can fold from one configuration to another. In 1936, Erd\H{o}s posed one of the first such problems (now solved): does repeatedly flipping a pocket of the convex hull convexify a polygon after a finite number of flips? This problem by itself has an intriguingly long and active history; most recently, in 2006, we discovered that the main solution to this problem, from 1939, is in fact wrong.

This talk will describe the surge of results about linkage folding over the past several years, in particular relating to the two problems described above. These results also have intriguing applications to robotics, graphics, nanomanufacture, and protein folding.

Erik Demaine, Massachusetts Institute of Technology
Geometric Puzzles: Algorithms and Complexity

Gortler, Steven -- Harvard
Characterizing Generic Global Rigidity

Consider a graph embedded in D-dimensional Euclidian space, with edges drawn as straight lines. We say that this embedding of the graph is globally rigid if it there is no other embedding of the graph in R^d with the same edge lengths (up to Euclidian transforms). Testing for global rigidity is in general NP-hard.
In this talk, I will describe a simple way to characterize global rigidity under the (mild) assumption that the embedding is "generic". In particular, we prove that Connelly's sufficient condition for generic global rigidity is also necessary. This condition can be tested efficiently using a randomized algorithm. This characterization also establishes that global rigidity is a generic property of a graph and dimension.I will also briefly touch on a related characterization of the universal rigidity of generic frameworks.This is joint work with Alex Healy and Dylan Thurston.

Jackson, Bill and Owen, John