Discrete Geometry and Graph Theory

    (An informal summer seminar organized with Károly Bezdek, Bob Connelly and Kostya Rybnikov)

    Place: Malott 224

    Time: Tuesday, Thursday, Friday 3:00 to 4:00 PM, from June 27, 2000 to August 4, 2000.

    Topics: The Colin de Verdiére graph invariant, Stress matrices, global rigidity, symmetric polyhedra.

    Abstracts and speakers (subject to change and extension):

    1. June 27: Connelly: A discussion of the Colin de Verdiere number of a graph and its basic properties. Some properties of the M matrix used in the definition. A discussion of some of the tools used such as the Perron-Frobenius Theorem, and the montone minor property of the Colin de Verdiere number.
    2. June 29: Connelly: The correspondence between the M matrix in the definition of the Colin de Verdiere number and the stress matrix of the associated braced graph. An outline of a proof of Lovasz's Theorem on the stress matrix of a braced polytope in 3-space.
    3. June 30: Rybnikov: A description of d-stresses and how to create k-stresses from them for d-complexes in d-space.
    4. July 4 (possibly delayed due to the holiday): Bezdek: An explicit proof of the stability of centrally symmetric polytopes in 3-space, where edges are cables and struts connect antipodal pairs of vertices.
    5. July 6: Our new results...
    6. July 11: Kostya's results on higher-order stresses
    7. July 13: Bob does intensive calculations (which people do not believe) to show that the bar framework consisting of a cube suspended inside a cube (a teseract) is a finite mechanism in three-space.
    8. July 14: Kostya talks about liftings of polyhedra.
    9. July 18: Open.
    10. July 25: Open
    11. August 4: Bob gave the details of a counterexample to a conjecture of Kostya about the rigidity of the bar framework obtained by taking a cube inside a larger cube with corresponding edges joined. This framework is a finite mechanism.

    It might be interesting to look at some of the papers by Lovasz on his home page at Yale. Or you can use his Microsoft homepage.

    Bob Erdahl visited on August 3 at 3 PM in Malott 224. Here is an abstract of his talk:

      Space filling zonotopes, dicings and regular matroids

      A space filling zonotope is one that can be used to tile space, in a facet-to-facet way, by translates. A dicing, on the other hand, is a way to cut space up - it is similar to dicing a carrot. I will explain how space filling zonotopes and dicings are dual notions in the theory of geometric lattices, and how the study of this duality has led to a partial answer to a question that was asked by George Voronoi over 90 years ago. Another interesting fact is that affine classes of space filling zonotopes are in one-to-one correspondence with regular matroids. I will explain how these notions fit into Voronoi's therory of lattice types. I show that the Voronoi polytope for a lattice can always be written as a Minkowski sum of simpler Voronoi polytopes. These summands are the building blocks, and correspond to Voronoi polytopes for "edge forms" in Voronoi's theory of lattice types. In 2- and 3-dimensions there is only one type of building block, a line segment. All Voronoi polytopes in these dimensions are Minkowski sums of line segments, so are zonotopes. In four dimensions a single new type of building block appears, the 24-cell, and in higher dimensions there are more. A non-trivial edge form is characterized by the property that the affine type of its Voronoi cell changes under any perturbation different from scaling.

    We hope to continue the seminar this Fall.

    Last updated: August 17, 2000