check
Combinatorics: Raphael Yuster (Haifa) | Einstein Institute of Mathematics

Combinatorics: Raphael Yuster (Haifa)

Date: 
Mon, 07/03/202211:00-13:00
HUJI Combinatorics Seminar 




When: Monday March 7th, 2022, at 11AM (Israel time)


Where: Sprinzak 202



Speaker: Raphael Yuster (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 (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 >= 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.