We propose to study the following "free" packing problem: Let n > 1 be a positive integer and let r > 0 be a positive real. Then for a given integer d > 1 find the packing of n unit balls in d-dimensional Euclidean space whose density relative to the outer parallel domain of their union having radius r is as large as possible. We give estimates in terms of n, r and d.

In this joint work with K. Böröczky and A. Heppes, we consider a finite family F of unit disks in the plane with the properties:

• T(k): any k-element subfamily of F has a (line) transversal, and
  
  
• O(d): the distance between the centres of any two elements of F is greater than d.
  
  

The extreme point identification problem is to partition the finite set S = {a_i,i Î I} Ì Rⁿ into its subsets N of necessary (extreme) points and N of redundant (non-extreme) points. This problem is important because algorithms to find the convex hull of S are exponential in set cardinality and the convex hull of N is the convex hull of S. Since the necessary points of S are in one-to-one correspondence with the necessary constraints in a representation of the polar dual of S, constraint classification algorithms can be used to determine the partition. We present a hybrid constraint classification algorithm that combines the ability of probabilistic algorithms to quickly detect necessary constraints and the ability of deterministic methods to quickly detect redundant constraints. Numerical experiments establish the effectiveness of this new algorithm.

Generic global rigidity in the plane is equivalent to vertex 3-connectedness and generic redundant rigidity (the framework remains rigid after the removal of any edge) by result of Berg and Jordan, and Jackson and Jordan; this provides a deterministic polynomial-time algorithm to determine generic global rigidity in the plane. There is a certain class of graphs, generic bar-and-body frameworks, for which there is a deterministic polynomial-time algorithm for generic local rigidity. Our result is that bar-and-body frameworks in d-space are generically globally rigid if and only if they are generically redundantly rigid. Thus generic global rigidity for this class of graphs can be determined by a deterministic polynomial-time algorithm in all dimensions by results of Tay and Tay and Whiteley.

But, unlike the condition for generic local rigidity, it is difficult determine what special configurations to avoid to be sure to have global rigidity. My hope was to find special classes of graphs and configurations that are globally rigid even when perturbed slightly. But there are counterexamples to this attempt in higher dimensions, using the property that a graph is generically globally rigid in d-space if and only if its cone is generically globally rigid in (d+1)-space (a joint result with W. Whiteley mentioned in a previous talk), generic local rigidity is preserved by vertex splitting (a result of W. Whiteley), the necessity of the maximal rank of a stress matrix (due to Gortler, Healy, and Thurston) and a construction due to Jiayang Jiang and Sam Frank.

Let D(d,n) be the maximum possible edge diameter over all polytopes defined by n inequalities in dimension d. The conjecture of Hirsch, formulated in 1957, states that D(d,n) is not greater than n - d. No polynomial bound is known for D(d,n), the best one being quasipolynomial and due to Kalai and Kleitman in 1992. Goodey showed in 1972 that D(4,10) = 5 and D(5,11) = 6. Recently, Bremner and Schewe proved that D(4,11) = D(6,12) = 6. In this follow-up work, we show that D(4,12) = 7 and present evidence that D(5,12) = D(6,13) = 7.

Based on a joint work with David Bremner (University of New Brunswick), William Hua (McMaster University), Lars Schewe (TU Darmstad, Germany).

We solved a long-standing Tammes problem for N=13. The problem asks us to find a configuration of 13 points on the unit sphere in three-space with the maximum angular separation. Using the computer we enumerated all possible jammed (or contact) graphs and found that a known maximal arrangement is unique.

This is joint work with Alexey Tarasov.

A "ghost symmetry" of a point configuration is a symmetry which appears in some projection of that configuration. Since it is easy to synthesize ghost symmetries by lifting points to higher spaces, ghost symmetries are more interesting when they are abundant. This talk presents a necessary and sufficient condition for the prescribability of a planar configuration to have 3 distinct ghost symmetries. In its statement and proof, the condition appears as an analogue of the classical characterization of 1-skeleta of convex 3-dimensional polytopes due to Steinitz.

Zeolites are a type of molecule with a sieve-like structure where the "holes" of the sieve expand and contract. Using this as motivation, we study the rigidity properties of infinite periodic frameworks. We can think of such a framework in n dimensions as a multigraph embedded on an n-dimensional torus, where the torus may be of fixed or variable dimensions. We use the language of voltage graphs to describe this embedding, and we attempt to characterize the generic infinitesimal rigidity of infinite periodic frameworks by the properties of the underlying voltage graph. This talk presents such a characterization for frameworks on a fixed torus in 2 dimensions, and we outline what is known for graphs on a flexible torus.

It is shown that for every set of k disjoint convex polygonal obstacles in the plane with a total of n vertices, there is a partition of the free space around the obstacles into n-k+1 convex cells whose dual graph is 2-edge connected. Every convex cell corresponds to a node in the dual graph, and every vertex of an obstacle corresponds to an edge between two incident convex cells. Questions about the dual graph of a convex partition are motivated by the geometric disjoint compatible matching conjecture.

Joint work with M. Al-Jubeh, M. Hoffmann, M. Ishaque, and D. Souvaine.

In any abstract 4-polytope P, the faces of ranks 1 and 2 constitute, in an obvious way, the vertices of a graph which has been called the medial layer graph of P. We consider the Cayley graph for the group generated by a natural set of polarities of a finite, self-dual, regular or chiral 4-polytope P as a covering graph of the medial layer graph of P.

When an embedding of a graph in Euclidean space is congruent to any other embedding with the same edge lengths, we say it is globally rigid. How do you tell? One way is to assume that the configuration is generic, which means that the coordinates of the configuration are algebraically independent over the rationals. There is a matrix, the stress matrix, such that when it has maximal rank, it implies that the graph is generically globally rigid. We will present a summary of some recent results, joint with Bob Connelly, on transferring the generic global rigidity of a graph G between a Euclidean space of dimension d and the cone of the graph in dimension d+1. Key to the new proof is the fact that coning keeps the stress matrix at maximum rank-which is generically, necessary and sufficient for global rigidity of the underlying graph. This result also demonstrates that generic global rigidity of a graph transfers between Euclidean and spherical metrics.

However, geometrically, coning may take a globally rigid framework G(p) to one that is not globally rigid, or take a framework that is not globally rigid to one that is. We briefly indicate a set of examples and counter-examples that arise in basic discussions of global rigidity.

A related preprint is available at: http://www.math.cornell.edu/~connelly/GlobalTechniquesConing-09V2.pdf.