A large hole in pseudo-random graphs

Source 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 / d $n\log d/d$ , and further demonstrate that this is tight up to a constant factor in the exponent.