2023/08/03 by Yahav Alon, Michael Krivelevich, Alon, Yahav +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2308.01564
openalex publication_date 2023/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is known that the complete graph Kn contains a pancyclic subgraph with n+(1+o(1))⋅ log 2 n edges, and that there is no pancyclic graph on n vertices with fewer than n+log 2 (n-1) -1 edges. We show that, with high probability, G(n,p) contains a pancyclic subgraph with n+(1+o(1))log2 n edges for p ≥ p^*, where p^*=(1+o(1))ln n/n, right above the threshold for pancyclicity.