Date
Tue, 13 Nov 2012
Time
14:30 - 15:30
Location
SR1
Speaker
Asaf Ferber
Organisation
Tel Aviv

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\"uhn.  Joint work with Michael Krivelevich and Benny Sudakov.

Please contact us with feedback and comments about this page. Last updated on 03 Apr 2022 01:32.