Counting and packing Hamilton cycles in dense graphs and oriented graphs

13 November 2012
14:30
Asaf Ferber
Abstract
<p>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&nbsp;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&nbsp;even&nbsp;degree of a spanning regular subgraph of $G$. This proves an approximate version of a conjecture made by Osthus and K\"uhn.&nbsp; Joint work with Michael Krivelevich and Benny Sudakov.</p>
  • Combinatorial Theory Seminar