Small dense subgraphs of polarity graphs and the extremal number for the 4-cycle

Michael Tait; Craig Timmons

paper

Small dense subgraphs of polarity graphs and the extremal number for the 4-cycle

arXiv:1502.02722

Abstract

In this note, we show that for any $m \in {1, 2, \dots, q + 1}$ , if $G$ is a polarity graph of a projective plane of order $q$ that has an oval, then $G$ contains a subgraph on $m + (2 m)$ vertices with $m^{2} + \frac{m ^{4}}{8 q} - O (\frac{m ^{4}}{q ^{3/2}} + m)$ edges. As an application, we give the best known lower bounds on the Turán number $ex (n, C_{4})$ for certain values of $n$ . In particular, we disprove a conjecture of Abreu, Balbuena, and Labbate concerning $ex (q^{2} - q - 2, C_{4})$ where $q$ is a power of $2$ .