A large hole in pseudo-random graphs

We show that there exist constants delta 1 comma delta 2 greater than 0 δ 1 , δ 2 > 0 δ ₁,δ ₂> 0 such that if upper G G G is an left parenthesis n comma d comma lamda right parenthesis ( n , d , λ ) (n,d,λ ) -graph with lamda divided by d less than or equals delta 1 λ / d ≤ δ 1 λ /d≤ δ ₁ , then upper G G G contains an induced cycle of length at least delta 2 n divided by d δ 2 n / d δ ₂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 upper G G G is at least exponential in n log d divided by d n log ⁡ d