A large hole in pseudo-random graphs

Abstract

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

11 pages