Leah Berman

Symmetric Geometric Configurations

A geometric $(q,k)$-configuration of points and lines is a collection of points and straight lines in the Euclidean or extended Euclidean plane so that every point lies on $q$ lines and every line passes through $k$ points. Such a configuration is \emph{symmetric} if there exist non-trivial rotations or reflections of the plane mapping the configuration to itself. This talk will discuss recent results in the existence and classification of symmetric geometric configurations, with an emphasis on configurations where $q$ and $k$ are bigger than 3.

Jesus A. De Loera

Advances on Computer-based lattice point counting and integration over polytopes 

Vic Klee was one of the founders of computational convexity. In the second of a series of papers Vic and Peter Gritzmann stressed the fundamental challenges of counting lattice points, computation of volumes, and integration over convex bodies. This talk presents new algorithmic results and associated software about them:

1) Normally lattice points are counted each with ``weight'' 1. But if each lattice point $\alpha$ in the polytope $P$ is counted with a ``polynomial weight'' $f(\alpha)$ there is a generalization of Ehrhart quasipolynomials. The leading coefficient is not a simple volume anymore, but the integral of $f$ over $P$. In joint work with Baldoni, Berline, Koeppe, and Vergne, we studied the computation of coefficients of the weighted Ehrhart polynomial. For example, we prove that integrating a power of a linear function $f$ over a rational simplex can be done in polynomial time. But we prove that the problem is $NP$-hard for arbitrary polynomials.

Our symbolic algorithms for exact integration are very fast in practice. A new version of LattE is about to be released with new capabilities for volume and integration.

2) Since exact counting is $\#P$-hard it is not surprising that there is a rich and exciting theory of estimation and approximation. There are various estimating algorithms, e.g. Monte-Carlo sampling, Markov-Chain Monte-Carlo, and others. Sadly, many of these available methods are only suitable for special polytopes or make the inpractical assumption that finding a first lattice point is doable, but for general polytopes even deciding whether a lattice point lies inside is an NP-hard, a tough challenge emerges for doing practical estimation without such assumption.

We report our experimental investigations with a recent method developed by A. Barvinok and J. Hartigan. The method heuristically computes estimations on the number of lattice points inside an arbitrary polyhedron by solving specially constructed convex optimization problems on polytopes. Unlike other techniques the Barvinok Hartigan idea uses no prior knowledge about the input polyhedron and the procedure is deterministic (with probabilistic estimates) and runs in polynomial time.

Peter Gritzmann

On Clustering Bodies, Gravity Polytopes and Power Diagrams: Computational Convexity in Agriculture

We deal with structural and algorithmic aspects of certain classes of closed convex sets and diagrams in finite dimensional real spaces that occur in geometric clustering. Here, $m$ objects in some $\mathbb R^d$ have to be partitioned into $k$ clusters according to certain balancing constraints so as to optimize some objective function. The most prominent example in our context is that of the consolidation of farmland.

While the relevant specifications of the optimization problem are NP-hard in general, we show how polynomial-time approximation algorithms can be devised whenever appropriate polyhedral approximations of their related clustering bodies are available. In particular, various structural results lead to surprisingly tight approximations.

Also we introduce the gravity polytopes in $\mathbb R^{kd}$ that are related to cardinality-constraint geometric clusterings and show how their vertices encode precisely the power diagrams in $\mathbb R^d$.

(Joint work with Andreas Brieden)

Richard Guy

The Lighthouse Theorem: Throwing light on geometry, old and new

n  equally spaced rays through a point meet  n  equally spaced rays through another point in  n^2  points which form  n  equally spaced n-gons.  We use these, together with Conway's ``extraversion'', to throw light on theorems of Euclid, on Morley's theorem, on the Malfatti problem, and perhaps on theorems yet to be discovered. The talk will be even more illuminating to those who have looked at
Amer. Math. Monthly 114 #2 (Feb 2007) 97--141.

Asia Ivic Weiss

Combinatorial structure of chiral polyhedra in Euclidean space

Grunbaum was the first to attempt the classification of infinite non-planar regular polyhedra with non-planar polygons or apeirogons as faces. The classification was completed by Dress  in 1980 by addition of a single polyhedron.  In 2005 Schulte proved that discrete chiral polyhedra in Euclidean $3$-space belong to six families.  The polyhedra in three of the families have finite faces and the other three families consist of polyhedra with (infinite) helical faces.  We show that all the polyhedra with finite faces are combinatorially chiral. However, the polyhedra with helical faces are combinatorially regular. Moreover, any two polyhedra with helical faces in the same family are isomorphic.

 Joint work with D. Pellicer.

Gil Kalai

The polynomial Hirsch conjecture

Thanks to Paco Santos we now know that the Hirsch conjecture is false. I will describe what is known about the conjecture:
There is a polynomial in d and n, p(d,n) so that the diameter of the graph of every d-polytope with n facets is at most p(d,n).

Alexandr V. Kostochka

Grünbaum and coloring intersection graphs of geometric figures

A seminal paper by Asplund and Grünbaum started studying colorings of intersection graphs of geometric figures, and in particular studying upper bounds on the chromatic number of such graphs in terms of their clique number or girth. We discuss the impact of this paper and of some other papers by Grünbaum on the topic. We also discuss recent progress in coloring of intersection graphs of chords of a circle.
Intersections of Chains of Affinely Equivalent Polytopes
In 1952 Borovikov published a proof of the conjecture of Kolmogorov that the intersection of a chain of simplexes in Euclidean space must be a simplex.  In a 1964 paper, Eggleston, Gr\"unbaum, and Klee extended the result to infinite-dimensional Hausdorff linear topological spaces, using Choquet simplexes; and they suggested another approach to the question, connected to their theorem that a (d-1)-dimensional  polytope with at most d+1 vertices lying in a d-simplex must have volume ((d-1)-measure) at most that of some facet of the simplex, with strict inequality unless the polytope is itself a facet. We consider the following question, analogous to Kolmogorov's:  What are the possibilities for the intersection of a chain of polytopes (or compact convex sets), each of which is affinely equivalent to a given polytope? In finite-dimensional spaces we obtain a generalization of the result of Borovikov, while in infinite-dimensional spaces we obtain an analogue of the result on Choquet simplexes of Eggleston, Grünbaum, and Klee.

Bojan Mohar

Rough structure theorem for symmetric graphs with small separations

Let $G = (V,E)$ be a vertex-transitive (finite or infinite, directed or undirected) graph, let $A$ be a finite set of vertices with $|A| \le |V|/2$, and let $k$ be the number of vertices that are not in $A$ but have a neighbor in $A$. We show that if the diameter of $G$ is large enough, then either $|A| \le 2k3$, or $G$ has a (bounded) ring-like structure and $A$ is efficiently contained in an interval. This result can be viewed as a rough structure characterization for small separations in symmetric graphs. Applications to the study of product sets, to expansion in groups, and to symmetries in minor-closed families will be presented.

Joint work with Matt DeVos.

Joseph O'Rourke

Unfolding Convex Polyhedra 

The surface of a convex polyhedron can be cut open and flattened to the plane as a simple polygon. In particular, the unfolding does not self-overlap. So the polygon may be cut out of paper and folded to the convex polyhedron. 

It is most natural to restrict the cuts to follow the edges of the polyhedron. It remains an open problem to settle whether or not every convex polyhedron can be cut open to a "net" along edges. This problem was first explicitly formulated by Geoffrey Shephard in 1975, and Branko Grünbaum conjectured that every convex polyhedron has such a net. I will review the (scant) progress on this question since, including Grünbaum's counterexample for nonconvex polyhedra. 

Without the edge restriction, there are several methods known to cut open any convex polyhedron to a polygon. I will describe two: one old one, based on an idea of Alexandrov from the 1940's, and a new generalization I obtained in joint work with Jin-ichi Itoh and Costin Vilcu.

Tomaž Pisanski

From graphs to configurations and back

It is almost impossible to study geometric configurations without considering the associated graphs. On the other hand many important graphs and graph families arise from configurations. Several connections between the two subjects of study are quite useful. We present some examples of these connections, the most notable being the Levi graph of a configuration.  The presence of symmetries usually enables us to reduce the size of graphs and apply the covering projection, a well-known method from algebraic topology. Many graph invariants, such as girth, hamiltonicity, etc. have natural analogs in configurations, however, the geometric flavor of configurations leads to some unexpected connections between configurations and graphs. Our overview of these pathways will focus on two topics: cyclic configurations with the corresponding  cyclic Haar graphs and a generalization of the girth-cages problem. Most of the talk is inspired by the work of Branko Grünbaum or is based on our joint work.

Richard Pollack

Double Permutation Sequences and Arrangements of Planar Families of Convex Sets

We recall Permutation Sequences and Allowable Permutation Sequences and the Theorem that every Allowable Permutation Sequence can be realized by an arrangement of pseudolines.

We (re)introduce Double Permutation Sequences, which provide a combinatorial encoding of arrangements of convex sets in the plane. We also recall the notion of a Topological Affine Plane and several (some new) of its properties. In particular, that for every Allowable Double Permutation Sequence there is a universal Topological Affine Plane P (i.e. any finite arrangement of pseudolines is isomorphic to some arrangement of finitely many lines of P), and that every Allowable Double Permutation sequence can be realized by an arrangement of simply connected sets and pseudoline double tangents to every pair of these sets.

All of this work is joint with Jacob E. Goodman and some involves numerous other people, among whom are Raghavan Dhandapani, Andreas Holmsen, Shakhar Smorodinsky, Rephael Wenger, and Tudor Zamfirescu.

Frank Ruskey

Branko Grunbaum and Venn Diagrams

In this talk we survey Branko Grunbaum's pioneering contributions to the combinatorial and geometric study of Venn diagrams, and outline some of the beautiful flowers that grew from the seeds that he planted.

Francisco Santos

A counter-example to the Hirsch conjecture

I have been in Seattle only once, in January 2002, when I visited to give a colloquium talk at UW. Although Victor Klee was already retired--he was 76 years old--he came to the Department of Mathematics to talk to me. We had a nice conversation during which he asked "Why don't you try to disprove the Hirsch Conjecture?"

I have later found out that he asked the same question to many people, including all his students, but the question and the way it was posed made me feel special at that time. This talk is the answer to that question. I will describe the construction of a 43-dimensional polytope with 86 facets and diameter bigger than 43. The proof is based on a generalization of the $d$-step theorem of Klee and Walkup.

Egon Schulte

Grunbaum's Impact on Discrete Geometry and Symmetry

Branko Grunbaum has made fundamental contributions to our understanding of discrete symmetric structures in geometry and combinatorics, such as polytopes, polyhedra, maps, graphs, complexes, and tilings.

In the mid 1970's, Branko initiated the modern theory of abstract polytopes and combinatorial symmetry. Over the years, this theory has proved extremely well-suited to address many basic problems on discrete geometric structures, and has established itself as the driving force behind many exciting developments in this area. At about the same time, Branko introduced a radically new, skeletal, graph-theoretic approach to polyhedral structures and symmetry. Then in the 1980's, Branko's pioneering work with Geoffrey Shephard on tilings again featured a rich display of symmetry, and sparked a surge of interest in tiling theory.

We describe some of Branko Grunbaum's major contributions to discrete geometry and symmetry.

Marjorie Senechal

Tilings, Lost and Found

Thirty five years ago, in his legendary “Lectures on Lost Mathematics,” Branko Grünbaum pointed to significant, fascinating, challenging – yet forgotten -- problems in tiling theory and rigidity theory. Many of them had been inspired by conundrums in crystallography, chemistry, art, and engineering but, within “mainstream” mathematics, they shed their geometric/scientific skins and emerged as “an independent form of life, complete with procreation of derived
questions rarely of interest to anybody but the most devoted followers of some particular cult.” Through his lectures and myriad papers, Branko rekindled both fields. Today the study of tilings, ridigity, and relations between them is burgeoning. But –  my example will be aperiodic tiles and nonperiodic tilings – we must take care lest history repeat.

Bernd Sturmfels

The Convex Hull of a Space Curve
The boundary of the convex hull of a compact algebraic curve in real 3-space defines a real algebraic surface. For general curves, that boundary surface is reducible, consisting of tritangent planes and a scroll of stationary bisecants. We express the degree of this surface in terms of the degree, genus and singularities of the curve. We present methods for computing their defining polynomials, and we discuss a wide range of examples. Most of these are innocent-looking trigonometric curves such as (cos(t), sin(2t), cos(3t)). This is joint work with Kristian Ranestad.

Steve Wilson


"Maniplex" is generalization of both "map" and "polytope", and very slightly generalizes "abstract polytope ".  We will concentrate in this talk on the operators that construct one maniplex from another.

Joseph Zaks

My Geometric results influenced by Victor Klee and by Branko Grunbaum

    I will concentrate on a few of my geometric results, influenced by my work under Vic and Branko,  which I have obtained since I left my secured nest in Seattle (1969).
    My most remarkable result was the proof (1986) that there can be at most eight tetrahedra in a neighborly family in E^3, in which I have settled a famous open problem.
    In a reply to a problem that Vic raised in 1969 in his column "Open Problems"  in the Monthly, I had showed that there exist two (non-convex) bodies A and C in E^3 , such that for all bodies B,  for which A \subseteq B \subseteq C, the maximum areas of the intersections of B with hyperplanes, parallel to a fixed hyperplane H,  are a fixed constant, independent of H.
    I will present the proof (by my Ph.D. student W. Hibi, 2005) of a Beckman-Quarles type theorem, stating that every unit-preserving mapping of the rational d-space  Q^d  to itself is an isometry, provided d  ≥  5.

Günter M. Ziegler

On Delaunay Polytopes and on Associahedra

We characterize the cyclic polytopes and the stacked polytopes that can be realized as Delaunay polytopes, that is, with all vertices on a sphere. This implies an Upper Bound Theorem and a Lower Bound Theorem for Delaunay Polytopes.

We report about three systematic and “natural” constructions of the associahedron, as a fiber polytope, via root systems, and as Minkowski sums. We show that the three constructions produce distinct results: Even with a suitable choice of parameters they can be distinguished in terms of parallel facets. Only one of the three constructions is known to produce Delaunay polytopes.

(Joint work with Cesar Ceballos and with Bernd Gonska)