#
Monday Lecture and Colloquium

**Monday, January 14, 2013 **

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

room 005

** Lecture - 14:15**

###
Yoshi Kohayakawa - Universidade de São Paulo

### Problems and results in probabilistic additive combinatorics

*Abstract:*

We discuss some problems and results in the area of probabilistic
extremal problems, with emphasis on problems from additive
combinatorics. In particular, we shall discuss results on the density
of Sidon sets contained in random sets of integers, mostly obtained by
estimating the number of Sidon sets of a given cardinality. Our
counting results also address a problem proposed by Cameron and Erdős. Generalizations to B_h-sets will be discussed.

This is joint
work with Sang June Lee, Vojtech Rödl, and Wojciech Samotij.

**Colloquium - 16:00**

###
Lothar Narins - Freie Universität Berlin

### Extremal 3-Graphs for Ryser's Conjecture

*Abstract:*

Ryser's Conjecture states that any r-partite r-uniform hypergraph has a vertex cover of size at most r - 1 times the size of the largest matching. For r = 2, the conjecture is simply König's Theorem. It has also been proven for r = 3 by Aharoni using topological methods. Our ambitious goal is to try to extend Aharoni's proof to r = 4. We are currently still far from this goal, but we start by characterizing those hypergraphs which are tight for the conjecture for r = 3. Our proof of this characterization is also based on topological machinery, particularly utilizing results on the (topological) connectedness of the independence complex of the line graph of a graph.

Joint work with Penny Haxell and Tibor Szabó.

Letzte Aktualisierung:
09.01.2013