A large hole in pseudo-random graphs

Abstract We show that there exist constants delta 1 comma delta 2 greater than 0 <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:msub> <mml:mi>δ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>δ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:math> $\delta _1,\delta _2\gt 0$ such that if upper G <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>G</mml:mi> </mml:math> $G$ is an left parenthesis n comma d comma lamda right parenthesis <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>d</mml:mi> <mml:mo>,</mml:mo> <mml:mi>λ</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> $(n,d,\lambda )$ -graph with lamda divided by d less than or equals delta 1 <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>λ</mml:mi> <mml:mrow> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>d</mml:mi> <mml:mo>≤</mml:mo> <mml:msub> <mml:mi>δ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> $\lambda /d\le \delta _1$ , then upper G <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>G</mml:mi> </mml:math> $G$ contains an induced cycle of length at least delta 2 n divided by d <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:msub> <mml:mi>δ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mi>n</mml:mi> <mml:mrow> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>d</mml:mi> </mml:math> $\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 <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>G</mml:mi> </mml:math> $G$ is at least exponential in n log d divided by d <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>n</mml:mi> <mml:mi>log</mml:mi> <mml:mo>⁡</mml:mo> <mml:mi>d</mml:mi>