Let be a constant and let be a -regular graph on with not too many symmetries. By the union bound, the probability threshold for the existence of a spanning subgraph in isomorphic to is at least . We give a tight bound on the edge expansion of guaranteeing that the probability threshold for the appearance of a copy of has the same order of magnitude as . We also prove that, within a slight strengthening of this bound, the probability threshold is asymptotically equal to . 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 and (asymptotically) almost all -regular graphs on , is a sharp threshold for -containment.

生成讲解博客的中文版本

生成AI智能校验的中文版本