A large hole in pseudo-random graphs
Abstract
Abstract We show that there exist constants delta 1 comma delta 2 greater than 0 δ 1 , δ 2 > 0 $\delta _1,\delta _2\gt 0$ such that if upper G G $G$ is an left parenthesis n comma d comma lamda right parenthesis ( n , d , λ ) $(n,d,\lambda )$ -graph with lamda divided by d less than or equals delta 1 λ / d ≤ δ 1 $\lambda /d\le \delta _1$ , then upper G G $G$ contains an induced cycle of length at least delta 2 n divided by d δ 2 n / d $\delta _2n/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 upper G G $G$ is at least exponential in n log d divided by d n log d
Fields of Study & Subjects
Limits and Structures in Graph Theory
Stochastic processes and statistical mechanics
Complex Network Analysis Techniques
Publication details
- Journal / source
- Combinatorics Probability Computing
- Publisher
- Cambridge University Press (CUP)
- Volume
- 35
- Issue
- 5
- Pages
- 1–11
- Publication date
- 25 June 2026
- Language
- EN