A large hole in pseudo-random graphs

We show that there exist constants ${\delta }_1,{\delta }_2>0$ such that if $G$ is an $(n,d,\lambda )$-graph with $\lambda \mathrm{/}d\le {\delta }_1$, then $G$ contains an induced cycle of length at least ${\delta }_{2}n\mathrm{/}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 $n\log d\mathrm{/}d$, and further demonstrate that this is tight up to a constant factor in the exponent.