TAU Combinatorics Seminar 2021/22

When: Sunday, October 10, 10am
Speaker: Raphael Yuster, University of Haifa
Title: Hamilton cycles above expectation in $r$-graphs and quasi-random $r$-graphs

Abstract:

Let $H_r(n,p)$ denote the maximum number of (tight) Hamilton cycles in an $n$-vertex $r$-graph with density $p \in (0,1)$.

The expected number of Hamilton cycles in the random $r$-graph $G_r(n,p)$ is clearly $E(n,p)=p^n(n-1)!/2$ and in the random $r$-graph $G_r(n,m)$ with $m=p\binom{n}{r}$ it is, in fact, easily shown to be slightly smaller than $E(n,p)$.

For graphs, $H_2(n,p)$ is proved to be only larger than $E(n,p)$ by a polynomial factor and it is an open problem whether a quasi-random graph with density $p$ can be larger than $E(n,p)$ by a polynomial factor.

For hypergraphs the situation is drastically different. For all $r\ge 3$ it is proved that $H_r(n,p)$ is larger than $E(n,p)$ by an exponential factor and, moreover, there are quasi-random $r$-graphs with density $p$ whose number of Hamilton cycles is larger than $E(n,p)$ by an exponential factor.