Monday, January 14, 2013
Freie Universität Berlin
Institut für Informatik
Lecture - 14:15
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
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ó.