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)$ it 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.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).