Maksim Zhukovskii

Thresholds for regular subgraphs of random graphs

Let d\geq 3 be a constant and let F be a d-regular graph on {1,...,n}. It is well known that if a large proportion of the vertices of F belong to subgraphs with edge boundary at most d, then the threshold for the appearance of a copy of F in the binomial random graph is asymptotically bigger than the expectation threshold. We prove that this boundary condition is the sole reason for such an asymptotic gap: If every non-trivial subgraph of F has edge boundary at least d+1, then the probability threshold and the expectation threshold differ by a constant factor. Furthermore, under additional conditions on symmetries and edge boundaries of subgraphs of F, we prove that the probability threshold and the expectation threshold are asymptotically equal. In particular, it proves the conjecture of Kahn, Narayanan and Park (2020) on the sharp threshold for the containment of the square of a Hamilton cycle. It also implies asymptotics of sharp thresholds for (asymptotically) almost all d-regular graphs.