A large hole in pseudo-random graphs

Abstract

We show that there exist constants

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 / d $n\log d/d$

, and further demonstrate that this is tight up to a constant factor in the exponent.