ETH Combinatorics Day
Wednesday, May 23, 2007
Room: FIM (HG HW-Zimmer)

-------
Imre Barany (Renyi Institute and University College London)

Title: Extremal problems for convex lattice polytopes: a survey

Abstract: In this survey I will present several extremal
problems, and some solutions, concerning convex lattice polytopes.
A typical example is to determine the smallest area that a convex
lattice polygon can have if it has exactly n vertices.

------
Gabor Elek (Budapest, Renyi Institute):

Title: Hypergraph regularity, removal lemma and the limit object. A
non-standard approach. 

Abstract: We study the analysis and measure theory on hyperfinite
spaces that is on ultraproducts of finite sets. Using this method we
provide a short proof of the celebrated
Hypergraph Removal Lemma (Rodl et. al, Gowers, Tao), 
the Hypergraph Regularity Lemma and the existence
of the Hypergraph Limit Object for convergent hypergraph sequences.

(joint work with Balazs Szegedy)

------
David Gamarnik (MIT)

Title: Correlation decay, statistical physics and applications to counting
problems

Abstract: We propose new approximation algorithms for
solving certain counting problems. Unlike prior algorithms which are based
on Markov chain sampling technique, our algorithms are deterministic and 
thus do not require randomization.  Our technique builds on the notion of
correlation decay, which originates in statistical physics in connection
with the uniqueness property of Gibbs measures on infinite lattices.

Using this technique we construct deterministic approximation algorithms
for some counting problems, including counting matchings (monomer-dimer
configurations), proper colorings,
and the problem of computing a permanent of a bi-partite graph. 

------
Jiri Matousek

Title: Graph coloring with no large monochromatic components

Abstract: For a graph G and an integer t we let mcc_t(G) be the smallest m such that
there exists a coloring of the vertices of G by t colors
with no monochromatic connected subgraph having more than
m vertices. We investigate this parameter for various classes of graphs, 
such as planar graphs (where we obtain a tight bound for mcc_2),
graph classes excluding a fixed minor, graphs of bounded degree, and d-dimensional
triangulated grids. Many challenging questions remain open.

(joint work with Nati Linial, Ales Privetivy,
Or Sheffet, and Gabor Tardos)

-------
Alexander Schrijver (CWI and University of Amsterdam)

Title: Graph and knot invariants

Abstract: The partition function of statistical mechanics leads to graph and knot
invariants, as was put forward by de la Harpe and Jones.
We discuss how such invariants can be characterized in terms of
`reflection positivity'.
The proofs uses results from invariant theory and real algebraic geometry
and are inspired by work of Balazs Szegedy and by joint work with Michael
H. Freedman and Laszlo Lovasz.

---------