Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 14, 2013, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Asaf Ferber (Tel Aviv University)
In this talk we would like to present a general method for counting and packing Hamilton cycles in dense graphs and oriented graphs, based on permanent estimates. We then show how to utilize this approach to prove several extremal results. As a warm up we prove that every Dirac graph G contains at least (reg(G)/e)n many distinct Hamilton cycles, where reg(G) is the maximal degree of a spanning regular subgraph of G. We then show that every nearly cn-regular oriented graph on n vertices with c>3/8 contains (cn/e)n (1+o(1))n directed Hamilton cycles. This is an extension of a result of Cuckler, who settled an old conjecture of Thomassen about the number of Hamilton cycles in regular tournaments. We also show that every graph G on n vertices with minimum degree at least (1/2+ɛ)n contains at least (1-ɛ)regeven(G)/2 edge-disjoint Hamilton cycles, where regeven(G) is the maximum even degree of a spanning regular subgraph of G. This establishes an approximate version of a conjecture of Kühn, Lapinskas and Osthus.
Joint work with Michael Krivelevich (my supervisor) and Benny Sudakov.
Automatic MiSe System Software Version 1.4803M | admin login