Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information
Date and Time: Tuesday, September 19, 2006, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Michael Krivelevich (Tel Aviv University)
How many edge disjoint Hamilton cycles can one pack in a graph G? Since every such cycle consumes exactly two edges incident to every vertex of G, the obvious upper bound for this quantity is one half of the minimum degree of G (rounded down, to be more accurate). In our recent work with Alan Frieze we show that for the random graph G(n,p), as long as the edge probability p(n) satisfies: p(n)=o(log n) this trivial upper bound is almost surely tight.
In my talk I will discuss this result, its predecessors and (conjectured) successors, and will also indicate some ideas used in its proof.
Automatic MiSe System Software Version 1.4803M | admin login