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

In this note, we show that for any m ∈ {1, 2, . . . , 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+ ( m 2 ) vertices with m + m 4 8q −O( m4 q3/2 +m) edges. As an application, we give the best known lower bounds on the Turan number ex(n, C4) for certain values of n. In particular, we disprove a conjecture of Abreu, Balbuena, and Labbate concerning ex(q − q − 2, C4) where q is a power of 2.