2023/01/10 by Zhukovskii, Maksim
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2301.04198
Let d≥ 3 be a constant and let F be a d-regular graph on [n] with not too many symmetries. By the union bound, the probability threshold for the existence of a spanning subgraph in G(n,p) isomorphic to F is at least p^*(n)=(1+o(1))(e/n)2/d. We give a tight bound on the edge expansion of F guaranteeing that the probability threshold for the appearance of a copy of F has the same order of magnitude as p^*. We also prove that, within a slight strengthening of this bound, the probability threshold is asymptotically equal to p^*. In particular, it proves the conjecture of Kahn, Narayanan and Park on a sharp threshold for the containment of a square of a Hamilton cycle. It also implies that, for d≥ 4 and (asymptotically) almost all d-regular graphs F on [n], p(n)=(e/n)2/d is a sharp threshold for F-containment.