Sidon Sets and graphs without 4-cycles

Abstract

The problem of determining the maximum number of edges in an $n$-vertex graph that does not contain a 4-cycle has a rich history in extremal graph theory. Using Sidon sets constructed by Bose and Chowla, for each odd prime power $q$ we construct a graph with $q^2-q-2$ vertices that does not contain a 4-cycle and has at least $\frac{1}{2}{q}^3-q^2-O(q^{3/4})$ edges. This disproves a conjecture of Abreu, Balbuena, and Labbate concerning the Turán number $\mathrm{ex}(q^2-q-2,C_4)$.

9 pages