Counting and packing Hamilton cycles in dense graphs and oriented graphs

Counting and packing Hamilton cycles in dense graphs and oriented graphs

Tue, 13/11/2012
14:30 		Asaf Ferber (Tel Aviv) Combinatorial Theory Seminar Add to calendar SR1
Counting and packing Hamilton cycles in dense graphs and oriented graphs
In this talk we present a general method using permanent estimates in order to obtain results about counting and packing Hamilton cycles in dense graphs and oriented graphs. 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 continue with strengthening a result of Cuckler by proving that the number of oriented Hamilton cycles in an almost $ cn $-regular oriented graph is $ (cn/e)^n(1+o(1))^n $, provided that $ c $ is greater than $ 3/8 $. Last, we prove that every graph $ G $ of minimum degree at least $ n/2+\epsilon n $ contains at least $ reg_{even}(G)-\epsilon n $ edge-disjoint Hamilton cycles, where $ reg_{even}(G) $ is the maximal even degree of a spanning regular subgraph of $ G $. This proves an approximate version of a conjecture made by Osthus and Kühn.  Joint work with Michael Krivelevich and Benny Sudakov.