ERC Workshop “HighComplexity Discrete Geometry”
October 2427, 2011
This will be a conference/workshop with lectures, presentations, informal discussions and posters that treat highcomplexity 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. 
Contents
Invited speakers (*to be confirmed)  
Gennadiy Averkov (U Magdeburg) 
Herbert Edelsbrunner (Duke/IST) 
Rick Kenyon (Brown) 
Boris Springborn (TU Berlin) 
Imre Bárány (Rényi/UCL) 
Martin Henk (U Magdeburg) 
Jiri Matousek (Charles University) 
John M. Sullivan (TU Berlin) 
Anders Björner (KTH) 
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) 

Organizers  
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:0019: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, BerlinDahlem Fon: +49 (0) 30  5577970 Fax: +49 (0) 30  557797100 berlin@seminaris.de 

Registration and financial support  
The registration deadline is June 30, 2011. Limited funding is available for travel and lodging. Please register by email. 
Monday 
Tuesday 
Wednesday 
Thursday 
Lunch 



Monday Morning:
Welcome 10:00
Lecture 10:15
Break
Lecture 11:30
otherwise:
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 inclusionmaximal 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 
"Connectivity"
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 P_{1},...,P_{2} such that area(P_{1} ∩ K) =...= area(P_{n} ∩ K) and perimeter(P_{1} ∩ K) =...= perimeter(P_{n} ∩ 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 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 CauchyRiemann 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 nmanifold, M. Alexander duality relates the homology of U with that of V, and using the MayerVietoris 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 realvalued functions. One of the results is the following: Let A be a compact set in ℝ^{n+1}, let its boundary dA be an nmanifold, 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 ndimensional Euclidean space and a nonnegative 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 nontrivial 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 Turantype problems, with FranklRodlWilson type theorems, and with the Borsuk's problem,a conjecture with RoyMeshulam 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 polynomialtime algorithm for computing lowdiscrepancy 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 linearalgebraic 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"
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,...,N1}. This result and its density versions imply van der Waerden's and Szemeredi's theorems. 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 FurstenbergWeiss 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 counterexample to the (bounded) Hirsch conjecture: a 43dimensional polytope with 86 facets and diameter (at least) 44. It was based on the construction of a 5prismatoid of width 6, with 48 vertices. Since then, several improvements or related results have been obtained:
of dimension less than 5 cannot lead to nonHirsch polytopes using my methods.
5prismatoids of length 6, now with only 25 facets. These produce counterexamples 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:
( Polynomial Hirsch Conjecture ).
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. CONJECTURE (H hnle): "The diameter of every dpolytope with n facets is bounded above by nd". 
Boris Springborn:  slides 
"What hyperbolic polyhedra can do for your conformal mapping needs" 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 threedimensional hyperbolic polyhedra. 
John Sullivan:  slides 
"Lowcomplexity triangulations of the threesphere"
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 c_{d} of all ddimensional simplices spanned by X.
Gromov recently introduced a new, topological proof method that yields improved (but not yet sharp) lower bounds for c_{d} and, furthermore, yields a topological extension: For any continuous map T from the nsimplex Δ^{n} → ℝ^{d} , there exists a point o that is contained in the Timages of at least a c_{d} fraction of all dfaces of Δ^{n}.
A key ingredient in Gromov's proof are isoperimetric inequalities in the simplex: Given an (nk)dimensional "surface" (cycle with Z_2coefficients) z in Δ^{n}, what is the size of the smallest (nk+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 MatousekW. and Král'MachSereni, which, in particular, leads to better lower bounds for c_{3}. 
 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: Logconcavity of fvectors of matroid complexes and zonotopal algebra
Affiliation: TU Berlin/ Berlin Mathematical School  Name: Eran Nevo
Title of poster: Nonsimplicial nonpolytopal spheres with nonnegative toric gvector
Affiliation: BenGurion 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
Funded by European Science Foundation ERC Grant "Structured Discrete Models" 