This workshop, sponsored by AIM and the National Science Foundation, was devoted to polyhedral objects in Euclidean spaces. Specifically, which metric or combinatorial properties must change or remain constant under certain classes of deformations, such as bending, folding, stretching, or flexing? When it is impossible to carry out one or another of these operations in some prescribed manner, an object is said to possess some sort of "rigidity". This can occur, for example, when too many metric or combinatorial properties are forced to remain constant under a given operation. The past several years have seen a number of significant advances, such as a proof of the bellows conjecture (described below), constructions of unfoldings for polytopes of all dimensions, and an algorithm for Alexandrov's theorem on 3-polytopes. But with those advances has come increasing recognition that many basic questions remain largely open, particularly in higher dimensions. An example of one of the basic objects under consideration is a bar-and-joint framework. See Figure 1.

Figure 1

The bars in such a configuration are stiff or rigid, and the joints are flexible (in a 2- or 3-dimensional sense). The most basic question is: When is the bar-and-joint framework rigid (i.e., will not bend or flex)? What conditions can we put on the (lengths of the) bars or the combinatorics of the framework to guarantee rigidity?

Questions of this kind certainly have pure mathematical interest, but they also come up in a number of applied contexts:

• The configuration of a molecule can be thought of as a combinatorial framework. The atoms are the vertices, but the "joins" are no longer flexible (being constrained by various forces at the atomic level). The angles at each vertex will be fixed; distances between atoms are essentially constant. For a protein molecule---just to take a specific example---the shape of the molecule affects the way that it interacts with other molecules. Rigidity of the shape insures robustness of certain types of interactions. Protein molecules are sequences of amino acids. As the amino acids are added, the molecule folds up into a more compact shape. One would like to be able to anticipate how the folding will occur, given the sequence of amino acids for the particular protein or to understand the rigidity properties of the shape after folding.
• Combinatorial frameworks arise in design problems of robotics. A big issue in robotics is stability and balance, and these questions may be studied using rigidity theory.
• Unfoldings of polyhedra are a matter of great interest, for they help us to understand the structures of these geometric objects, and also how molecules and other geometric objects are formed.
• It is useful to be able to calculate the volumes of convex polyhedra. In higher dimensions, this is quite a difficult problem with complexity exceeding the dimension of the ambient space.
• Questions of embedding of combinatorial objects---with restrictions on crossings--- help us to understand the role of geometry versus combinatorics.
• Many architectural structures are combinatorial frameworks whose rigidity properties are crucial for design and safety issues.
• In geometry, a surface can often be usefully approximated by a combinatorial framework. The combinatorial structure can be thought of as a "discrete" approximation; such a structure on a computer to perform calculations or to draw pictures.
• Underlying much of this discussion is the concept of deformation. When we ask whether a structure is rigid, we are implicitly asking how much it can be deformed. And to what.

Rigidity tells us about degrees of freedom for motions of a combinatorial framework. Euclidean 3-space has six degrees of freedom (rotations plus translations) and we want to be able to understand, and explicitly describe, systems that have fewer degrees. We would like to be able to detect rigidity in terms of the number vertices in the system, the number of edges in the system, and the combinatorial relations among these elements.

In the plane this last set of questions is very well understood. In R³, there are no known effective algorithms for answering the question, but there are tests.

In addition to studying bars and joints as illustrated in Figure 1, there is also interest in systems of 2-dimensional faces connected by "hinges" or other types of joins. This point of view has led to a number of important problems, including the so-called bellows conjecture which we discuss next.

The study of flexible objects has led to a fruitful interaction of geometry and algebra. In 1977, R. Connelly showed that there exists a surface in Euclidean three-space composed of rigid triangles, hinged along their edges, that is flexible. In 1995 I. Sabitov showed the very remarkable "bellows property" for such flexible surfaces: the volume they bound is constant during the motion; thus there is no perfect mathematical bellows. But even more remarkable is that there is a monic polynomial, whose coefficients are themselves polynomials in the edge lengths, which is satisfied by the volume. This is a new fundamental property of triangulated surfaces in Euclidean three-space; it is an algebraic identity, but it does not seem to be part of what is known in algebraic geometry. Another example is the area of a cyclic polygon in the plane, which is integral over the ring generated by the edge lengths (a favorite problem studied by David Robbins just before his death, and solved just after his death by Fedorchuk-Pak and others). These suggest problems such as the following, some of which could benefit from key insights using algebraic geometry of configuration spaces -- perhaps the kind of algebraic geometry considered by Develin, Martin, and Reiner in their work on rigidity.

An interesting set of questions that arises from this point of view is as follows: Given some combinatorial data (about vertices, edges, faces, etc.), what are all possible configurations of the system? What can one say about the configuration space? Does the configuration space have isolated points? How bad or complex can the configuration space be? One recent (and surprising) result says that the configuration space can be arbitrarily complicated: any space that can be described by polynomials can be the configuration space for some combinatorial system.

The AIM workshop on Rigidity and Polyhedral Combinatorics brought together mathematicians with diverse backgrounds and interests to develop new ideas for attacking these combinatorial problems. Differential, algebraic, combinatorial, and computational geometers interacted fruitfully to develop this rapidly growing subject area.