A large hole in pseudo-random graphs

2025/05/29 by Diskin, Sahar, Krivelevich, Michael, Markbreit, Itay +1
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2505.23384

Abstract

We show that there exist constants δ₁,δ₂>0 such that if G is an (n,d,λ)-graph with λ/d≤δ₁, then G contains an induced cycle of length at least δ₂n/d. We further demonstrate that, up to a constant factor, this is best possible. Utilising our techniques, we derive that the number of non-isomorphic induced subgraphs of such G is at least exponential in nlog d/d, and further demonstrate that this is tight up to a constant factor in the exponent.

Citations

• Non-isomorphic subgraphs in random graphs
• Maximum induced trees and forests of bounded degree in random graphs
• Site Percolation on Pseudo-Random Graphs
• Long induced paths in a configuration model
• The largest hole in sparse random graphs
• Hamilton Cycles in Random Graphs: a bibliography
• Expanders - how to find them, and what to find in them
• The phase transition in site percolation on pseudo-random graphs
• The phase transition in random graphs - a simple proof
• Pseudo-random graphs
• A proof of Alon's second eigenvalue conjecture and related problems

Related

• The largest hole in sparse random graphs
• Large subgraphs in pseudo-random graphs
• Long cycles in subgraphs of (pseudo)random directed graphs
• Detecting a long even hole
• Induced subgraphs of graphs with large chromatic number. IV. Consecutive\n holes