Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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