Andrzej Rucinski -Adam Mickiewicz University, Poznan

Regularity of Hypergraphs with Application to Hamiltonicity

Abstract: In 1952 Dirac proved that every graph on n>=3 vertices with minimum degree at least n/2 contains a Hamilton cycle. More recently, Katona and Kierstead asked if an analogous result is true for k-uniform hypergraphs, where a Hamilton cycle is defined as such a cyclic ordering of the vertices v_1,...,v_n, that for each i=1,...,n the k-tuple of consecutive vertices beginning with v_i forms a hyperedge, and the minimum degree is replaced by the minimum (k-1)-tuple degree, that is the number of hyperedges containing a given (k-1)-element set of vertices.

This year together with Rödl and Szemeredi we proved an approximate version of the conjecture for triple systems (k=3) which asserts that for every gamma>0 there exists n_0 such that whenever in a 3-uniform hypergraph on n >= n_0 vertices every pair of vertices belongs to at least n/2 hyperedges, then the hypergraph contains a Hamilton cycle.

One crucial tool used in our proof is a hypergraph analog of the celebrated Szemeredi Regularity Lemma by Frankl and Rödl. It provides a partition of each sufficiently large hypergraph into pieces, most of which look random-like, and thus can be almost completely covered by short hyperpaths. These paths are finally glued together to yield the desired Hamilton cycle.

During the lecture I will introduce both regularity lemmas (for graphs and for triple systems), illustrate their power by a few applications and finally outline the proof of the above mentioned result.

Colloquium - 16 Uhr s.t.

Dirk Schlatter-Humboldt-Universität zu Berlin

Random triangulations

Abstract: We consider two models for random (labelled) triangulations: the uniform model, in which each triangulation is equally likely to appear, and a model which is defined by the following random process: start with the empty graph, and add edges sequentially at random, as long as the resulting graph remains planar.

In the special case of triangulating a convex polygon by straight lines, we will determine a probability distribution for the edges to be chosen during this process such that the two models coincide. This yields a simple exact generating algorithm for outerplanar triangulations.