Let be a given finite (possibly empty) family of connected graphs, each containing a cycle, and let be an arbitrary finite -free graph with minimum degree at least . For , we form a -random subgraph of by independently keeping each edge of with probability . Extending a classical result of Ajtai, Koml'os, and Szemer'edi, we prove that for every positive , there exists a positive (depending only on ) such that the following holds: If , then with probability tending to as , the random graph contains a cycle of length at least , where is the minimum number of vertices in an -free graph of average degree at least . Thus in particular as above typically contains a cycle of length at least linear in .

生成讲解博客的中文版本

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