The study of geometric rigidity can be traced back to historical figures such as A. Cauchy who, in 1813, proved convex polyhedra are rigid. Subsequent work extending Cauchy’s theorem by Dehn, Alexandrov and Pogolerov continued into the 1940’s and 50’s. Similarly, combinatorial rigidity can be traced to J. C. Maxwell who, in 1864, developed necessary combinatorial, graph-based, conditions for bar-joint structures to be rigid. Hilda Polaczek-Geiringer proved in 1920 that Maxwell’s condition is sufficient in 2 dimensions. In fact, for most categories of frameworks, each constraint typically involves a pair of primitives. Hence, the framework and the constraint system has an underlying constraint graph of vertices representing the primitives and edges representing the constraints. Generic properties of the constraint system or the framework are often purely combinatorial properties of the underlying constraint graph. The useful interplay between the geometric and the combinatorial was further apparent in e.g. the relation between planar framework self-stresses, Maxwell-Cremona reciprocal diagrams, and polyhedral liftings; and the relation between conformal maps and Koebe’s theorem from the 30’s on rigidity of circle packings corresponding to maximal planar contact graphs.

Additionally, distance geometry questions going back to Schoenberg in the 20’s naturally entered the picture since constraints underlying many categories of frameworks are metric constraints. As a consequence of Schoenberg’s general result for Hilbert spaces, the realizability or solvability of a distance constraint system in (real) Euclidean space of a given dimension is equivalent to its completability as a distance matrix with appropriate rank (and semidefiniteness) conditions. Algebraically, the Cayley-Menger determinantal relations - used by Menger in the 20’s to characterize Euclidean realizability of distance constraints - can be viewed as szyzygies of polynomial invariants of the Euclidean group. A similar triad connects incidence constraints, Grassman-Pluecker relations and the projective group. Algorithmically, the characterization of (generic) rigidity-related properties of frameworks, as well as describing and exploring the solution spaces of geometric constraint sytems are fundamental problems with clear classical connections, for example, to: Galois field extensions (e.g. via ruler and compass constructions); Kempe’s 1876 description of algebraic curves using bar-joint linkages with prescribed bar lengths; Grassman-Cayley algebra derivations in projective geometry; and more generally polynomial system solving and ideal membership questions.

Hence right from its origins, the rigidity of frameworks emerged as a source of rich, crosscutting problems at the nexus of geometry, algebra, combinatorics and algorithmic foundations. Moreover, being remarkably amenable to spatially and mechanically intuitive explanations of deep results, the area has attracted and welcomed researchers in a variety of fields and perspectives.

Yet, it is only much later, prompted by a re-discovery of the Polaczek-Geiringer theorem by Laman in 1970, that rigidity theory began to develop as a mathematical subject area in its own right, leading to a steady output of substantial results in the decades since then. For a time, the flip side of this intense, focused development was somewhat reduced emphasis on the area’s natural connections with other areas. Recently, however, a multitude of problems from outside the core rigidity community have necessitated ‘rigidity-type’ results and methods. Some prominent examples include Kalai’s proof of the Lower Bound Theorem for manifolds and the recent work by several groups on low rank matrix completion problems. Such results, along with rigidity-related problems arising in novel applications from materials modeling to machine learning, have led to a revitalization of the historical connections (and development of new connections) to distance geometry, semidefinite analysis and algebraic geometry.

The purpose of this program is to bring together a diverse range of experts and early career researchers to study and report progress on geometric constraint systems and their applications. Participants are expected from several synergistic areas within mathematics (discrete, algebraic and distance geometry, graphs and matroids) as well as theoretical computer science, engineering and the natural sciences.

The Organizing Committee would like to express our thanks to staff at the University Waterloo. Without their help we would not be able to have long-term visitors in residence for the program.

GOVERNMENT SUPPORT