ERC Workshop “High-Complexity Discrete Geometry”


October 24-27, 2011

This will be a conference/workshop with lectures, presentations, informal discussions and posters that treat high-complexity discrete geometric structures and problems from different points of view, including extremal discrete geometry, polytopes and complexes, topological complexity, discrete differential geometry, circle/Delaunay geometry, symmetry, etc.




Invited speakers (*to be confirmed)
Gennadiy Averkov
(U Magdeburg)
Herbert Edelsbrunner
Rick Kenyon
Boris Springborn
(TU Berlin)
Imre Bárány
Martin Henk
(U Magdeburg)
Jiri Matousek
(Charles University)
John M. Sullivan
(TU Berlin)
Anders Björner
Michael Joswig
(TU Darmstadt)
Janos Pach
(EPFL and Renyi Institute)
Frank Vallentin
(TU Delft)
Pavle Blagojevic
(SANU / FU Berlin)
Gil Kalai
(Hebrew University)
Francisco Santos
(U Cantabria)
Uli Wagner
(ETH Zürich)
Alexander I. Bobenko
(TU Berlin)
Günter M. Ziegler
(FU Berlin)
Günter Rote
(FU Berlin)
Raman Sanyal
(FU Berlin)
Elke Pose
(FU Berlin)
The conference will start on Monday, October 24 at 10am. On Sunday 17:00-19:00, October 23, there will be a welcome reception at the Villa, Arnimallee 2. The conference will end on Thursday, October 27, at noon. The schedule will allow for plenty of interaction. A conference dinner "Berliner Buffet" takes place on Tuesday evening, Oktober 25 2011, 18:30 at "Alte Pumpe" (costs 25€, students 12€). Young people are especially encouraged to participate (with a poster); posters will be on display during the conference.
Location and lodging
The conference takes place at
Seminaris Conference Center.
Rooms have been blocked.
Please book directly at the hotel.
Booking code: ERC Workshop
Seminaris Conference Center and Hotel
Takustrasse 39, Berlin-Dahlem
Fon: +49 (0) 30 - 557797-0
Fax: +49 (0) 30 - 557797-100
Registration and financial support
The registration deadline is June 30, 2011.  Limited funding is available for travel and lodging. Please register by email.




























Monday Morning:

    Welcome 10:00

    Lecture 10:15


    Lecture 11:30



     9:30 Lecture

    10:30 Coffee Break

    11:00 Lecture

    12:00 Lunch

    14:00 Lecture

    15:00 Coffee Break

    15:30 Lecture

    16:30 Lecture



Gennadiy Averkov:     slides

"On integral polytopes with a small number of interior integral points" 


In this talk I will discuss old and new results on several

classes of integral polytopes with a given number of interior integral

points. The main aim is to present results about the finiteness of

such classes modulo affine transformations that preserve the integer

lattice. I will pay special attention to inclusion-maximal integral

polytopes without interior integral points and to integral simplices

with precisely one interior integral point.



Imre Barany: slides

"Tensors, colours, and octahedra"


Several classical results in convexity, like

the theorems of Caratheodory, Helly, and Tverberg, have

colourful versions. In this talk I plan to explain

how two methods, the octahedral construction and Sarkaria's

tensor trick, can be used to prove further extensions and

generalizations of such colourful theorems.



Anders Björner: slides



The concept of connectivity is central in graph theory as

well as in topology. Some measure of connectivity is often

the crucial technical ingredient that drives proofs in

topological combinatorics.


The intuitive notion of being connected has

been extended in several ways. This circle of ideas will be

briefly reviewed and some examples, thoughts, and modest

results will be presented.



Pavle Blagojevic: slides

"A view on equivariant topology of the configuration spaces"


In June 2007, Nandakumar and Ramana Rao asked whether for a given convex body K

in the plane and a given natural number n > 1 there exists a partition of the plain into

n convex pieces P1,...,P2 such that

        area(P1 ∩ K) =...= area(Pn ∩ K) and perimeter(P1 ∩ K) =...= perimeter(Pn ∩ K).

A beautiful idea of Karasev, and also of Aronov and Hubart,

to use the conguration space F(ℝ2, n) of n pairwise distinct points in the plane

as a conguration space raised important questions:

How well we understand the equivariant topoogy of the conguration space F(ℝd, n)?

Is everything we need to know already contained in the research of Fadell and Neuwirth,

Cohen and Taylor, Stanley, Sundaram and Welker, or Vassiliev?

Guided by the question of Nandakumar and Ramana Rao,

we present the following highlights of the equivariant topology of the

conguration space F(ℝd, n):

  • the equivariant Goresky{MacPherson formula for G-invariant c-arrangements where
    c > 1, describe
  • the R[n]-module structure on the cohomology H(F(Rd; n);R) with the view towards
    the computation of
  • the kernel of the natural map in the equivariant cohomology



The results that will be presented in this talk are obtained in

collaboration with Günter Ziegler.



Alexander Bobenko: slides

"Discrete and computational Riemann surfaces"


I will present a survey of the theory of discrete Riemann surfaces.

The aim is to discretize the notions and theorems of the classical theory.

Two definitions of discrete holomorphicity will be considered.

The approach based on the discrete Cauchy-Riemann equations leads to a

linear theory with discrete holomorphic differentials and period matrices of

Riemann surfaces.

Another approach based on a discretized notion of conformal equivalence for triangulated

surfaces leads to a nonlinear theory.

The latter naturally implies metrics with constant curvature and a uniformization

of discrete Riemann surfaces.

The discrete theory should contain the classical smooth theory as a limiting case,

as the discretization is refined.

We will discuss the convergence of discrete Riemann surfaces through their period matrices

and uniformization groups.



Herbert Edelsbrunner: slides

"Alexander duality for functions"


Consider a decomposition of the (n+1)-sphere into spaced U and V

whose intersection is an n-manifold, M. Alexander duality relates

the homology of U with that of V, and using the Mayer-Vietoris

exact sequence, we get a relation between the homology of M and U.

This talk presents extensions of this classical version of Alexander

duality to real-valued functions.  One of the results is the following:

Let A be a compact set in ℝn+1, let its boundary dA be an n-manifold,

and let f: ℝn+1 → ℝ be a smooth function without critical points

whose restriction to dA is tame.  Then the persistence diagram of

f restricted to dA is the disjoint union of the persistence diagram of

f restricted to A and the reflection of this diagram.

(Joint work with Michael Kerber)



Martin Henk: slides

"Roots of Steiner polynomials"


For two convex bodies K, E of the n-dimensional

Euclidean space and a non-negative real number  the volume

of the Minkowski sum K+ E

is a polynomial of degree n in , known as the

(relative) Steiner polynomial of K (with respect to E).


Regarding this (geometric) polynomial as a polynomial in a

complex variable we are interested in geometric properties of its

roots, e.g., their location in the complex plane (depending on the

involved bodies and dimension), size, relation to other functionals and

characterization of (families of) convex bodies by mean of properties

of the roots. In this talk I will survey on recent results on this

topic, which had its starting point in a problem posed by Teissier

in 1982 in the context of Algebraic/Toric Geometry.


(Based on joint works with Maria Hernandez Cifre and Eugenia Saorin Gomez)



Michael Joswig: slides

"Polytopes and Their Splits"


A split of a convex polytope is a non-trivial decomposition into two parts along

a hyperplane which does not separate any edge of the polytope. The study of

splits of polytopes is motivated by phylogenetic problems in algorithmic

biology. In this talk we will explore the role of the splits among all

(regular) polytopal subdivisions of a given polytope.



Gil Kalai: slides
"Some problems in topological combinatorics"


I will describe some problems and speculations in topological combinatorics:

Those include some questions about the combinatorics of cocycles and relations

with Turan-type problems, with Frankl-Rodl-Wilson type theorems,

and with the Borsuk's problem,a conjecture with Roy-Meshulam regarding

fractional Helly's theorem, and if times allow a few other questions.



Rick Kenyon: slides

"Dimers and integrability"


The dimer model is the probability model of random perfect matchings of a

graph. Natural parameters are edge weights.


We show that the parameter space of dimer models

(equivalently, the space of line bundles) on a bipartite

graph on a torus has the structure of a ``cluster variety", and is

equipped with a Poisson structure

defining an integrable system. A complete set of commuting Hamiltonians

can be given explicitly in terms of dimers.

(Joint work with A. Goncharov)



Jiri Matousek: slides

"Discrepancy, Bansal's algorithm and the determinant bound"


Last year Nikhil Bansal found a polynomial-time algorithm for computing

low-discrepancy colorings, based on semidefinite programming.

It makes several existential bounds for the discrepancy of certain set systems,

such as all arithmetic progressions on {1,2,...,n}, constructive,

which has been a major open problem in discrepancy theory.

We use Bansal's result, together with the duality of semidefinite programming

and a linear-algebraic lower bound for discrepancy due to Lovasz, Spencer,

and Vesztergombi, to answer an old question of Sos, concerning the maximum

possible discrepancy of the union of two set systems.



Janos Pach: slides

"Generalized arithmetic progressions"

Extending Furstenberg's ergodic theoretic proof for Szemeredi's theorem

on arithmetic progressions, Furstenberg and Weiss (2003) proved the following

qualitative result.

For every d and k, there exists an integer N such that no matter how we color the vertices

of a complete binary tree T(N) of depth N with k colors, we can find a monochromatic replica

of T(d) in T(N) such that

       (1) all vertices at the same level in T(d) are mapped into vertices at the same level

             in T(N)

       (2) if a vertex x of V(T(d)) is mapped into a vertex y in T(N),

             then the two children of x are mapped into descendants of the two children

             of y in T(N), respectively;

       (3) the levels occupied by this replica form an arithmetic progression in {0,1,...,N-1}.

This result and its density versions imply van der Waerden's and Szemeredi's theorems.

Using simple counting arguments and a randomized coloring algorithm called random split,

we prove the following related result.

Let N=N(d,k) denote the smallest positive integer such that no matter how we color

the vertices of a complete binary tree T(N) of depth N with k colors,

we can find a monochromatic replica of T(d) in T(N) which satisfies properties (1) and (2) above.

Then we have N(d,k)=Θ(dk log k).

We also prove a density version of this result, which, combined with Szemeredi's theorem,

provides a very short combinatorial proof of a quantitative version of the

Furstenberg-Weiss theorem.


Joint work with Jozsef Solymosi and Gabor Tardos.



Francisco Santos: slides

"How false is the Hirsch Conjecture?"


About a year ago I announced the first counter-example to the (bounded)

Hirsch conjecture: a 43-dimensional polytope with 86 facets and diameter

(at least) 44. It was based on the construction of a 5-prismatoid of width 6,

with 48 vertices. Since then, several improvements or related results have

been obtained:

  • Together with Tamon Stephen and Hugh Thomas, I showed that prismatoids

of dimension less than 5 cannot lead to non-Hirsch polytopes using my methods.

  • Together with Benjamin Matschke and Christophe Weibel, I constructed smaller

5-prismatoids of length 6, now with only 25 facets. These produce

counter-examples to the Hirsch conjecture in dimension 20.

But, all in all, the main open problems underlying the Hirsch Conjecture remain

as open as before. In particular, it would be very interesting to know the

answer to any of the following questions:

  • Is there a polynomial bound f(n) for the diameter of n-faceted polytopes?

( Polynomial Hirsch Conjecture ).

  • Is there a linear bound? Is f(n)="2n" such a bound?

One possibility, suggested by the work of Eisenbrand et al. in the abstract

setting of connected layer sequences would be that the following

quadratic Hirsch Conjecture holds. I will devote some time to explain the

context and evidence for it.


"The diameter of every d-polytope with n facets is bounded above by nd".



Boris Springborn: slides

"What hyperbolic polyhedra can do for your conformal mapping needs"

This talk is concerned with a discrete version of conformal maps.

A very simple definition of "discrete conformal equivalence" of triangle meshes leads to a

surprisingly rich and practical theory. I will discuss some of its salient features,

and what all this has to do with three-dimensional hyperbolic polyhedra.

(joint work with A. I. Bobenko and U. Pinkall.)



John Sullivan: slides

"Low-complexity triangulations of the three-sphere"

There are 4761 triangulations of the three-sphere with no edges of valence more than 5.

We examine these from several geometric and combinatorial points of view,

to see in which senses they have low complexity.

In particular, each gives rise to a spherical cone metric, which in most cases can be

smoothed by a curvature flow.

Some of these ideas extend to TCP triangulations, where some edges of

valence 6 are allowed.



Frank Vallentin: slides

"Computing upper bounds for densest packings with congruent copies

 of a convex body"


I will discuss the problem of upper bounding the maximum density of

a packing  of congruent copies of a convex body K in Euclidean space.

If K is the unit ball then this is the sphere packing problem.

Recently, the case of regular tetrahedra got quite some attention

(but see also Hilbert's 18th problem) and only very weak upper bounds

are known here.


In the talk I will present a theorem and some computational strategies

that can be used to find upper bounds for the maximum density of a packing

of any given body K. The theorem relies on the harmonic analysis of the

Euclidean motion group which is a noncompact and noncommutative group.

It generalizes a theorem of Cohn and Elkies that gives the best known

upper bounds for the densities of sphere packings in dimensions 4 to 36.

(Joint work with Fernando de Oliveira Filho)



Uli Wagner: slides

"Isoperimetric Inequalities in the Simplex and Multiplicities of Maps, after Gromov"


Let X be a set of n points in d. By results of Boros and Füredi (d=2)

and Bárány (arbitrary d), there always exists a point o in d (not

necessarily in X) that is contained in at least a constant fraction cd

of all d-dimensional simplices spanned by X.


Gromov recently introduced a new, topological proof method that

yields improved (but not yet sharp) lower bounds for cd and, furthermore,

yields a topological extension: For any continuous map T from the n-simplex

Δnd , there exists a point o that is contained in the T-images

of at least a cd fraction of all d-faces of Δn.


A key ingredient in Gromov's proof are isoperimetric inequalities in the

simplex: Given an (n-k)-dimensional "surface" (cycle with Z_2-coefficients)

z in Δn, what is the size of the smallest (n-k+1)-dimensional chain

b with boundary z?


We describe Gromov's topological proof as well as some recent further

progress on the isoperimetric problem in the simplex, due to Matousek-W.

and Král'-Mach-Sereni, which, in particular, leads to better lower bounds for c3.





  • Name: Ben Braun
    Title of poster: Mahonian Partition Indentities via Polyhedral Geometry
    Affiliation: University of Kentucky

  • Name: László Kozma
    Title of poster: Minimum Average Distance Triangulations
    Affiliation: Saarland University, Germany

  • Name: Matthias Lenz
    Title of poster: Log-concavity of f-vectors of matroid complexes and zonotopal algebra
    Affiliation: TU Berlin/ Berlin Mathematical School

  • Name: Eran Nevo
    Title of poster: Nonsimplicial nonpolytopal spheres with nonnegative toric g-vector
    Affiliation: Ben-Gurion University of the Negev

  • Name: Michael Cuntz
    Title of poster: Simplicial arrangements and integrality
    Affiliation: University of Kaiserslautern

  • Name: Antonios Varvitsiotis
    Title of poster: Characterizing graphs with gram dimension at most four.
    Affiliation: CWI Amsterdam

  • Name: Eric Colin de Verdiere and Xavier Goaoc
    Title of poster: Helly numbers of disconnected families
    Affiliation: CNRS, Ecole normale superieure, Paris, and Inria, Nancy, France

  • Name: Arnau Padrol
    Title of poster: Constructing neighborly oriented matroids
    Affiliation: Universitat Politècnica de Catalunya

  • Name: Laszlo Major
    Title of poster: On face vectors of polytopes: unimodality and generalized Euler's relations
    Affiliation: Department of Mathematics, Tampere University of Technology, Finland



LOGO-ERC-70 Funded by
European Science Foundation
ERC Grant "Structured Discrete Models"
Letzte Aktualisierung: 11.10.2012