ERC Workshop “High-Complexity Discrete Geometry”

Monday

Tuesday

Wednesday

Thursday

Santos 

Bárány 

Matousek

Blagojevic

Bobenko

Henk

Vallentin

Edelsbrunner

Lunch

Kenyon 

Kalai 

Pach 

Björner

Averkov

Sullivan

Joswig

Wagner

Springborn

"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.

"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.

"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.

"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₁,...,P₂ such that

        area(P₁ ∩ K) =...= area(P_n ∩ K) and perimeter(P₁ ∩ K) =...= perimeter(P_n ∩ K).

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

to use the conguration space F(ℝ², 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

collaboration with Günter Ziegler.

"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.

"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 ℝⁿ⁺¹, let its boundary dA be an n-manifold,

and let f: ℝⁿ⁺¹ → ℝ 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)

"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)

"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.

"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)

"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.

"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.

"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.

CONJECTURE (Hähnle):

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

"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.)

 "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.

"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)

"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 d-dimensional 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 n-simplex

Δⁿ → ℝ^d , there exists a point o that is contained in the T-images

of at least a c_d fraction of all d-faces of Δⁿ.

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 Δⁿ, 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 c₃.