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