Journal of Combinatorics

Volume 5 (2014)

Number 2

Sidon sets and graphs without 4-cycles

Pages: 155 – 165

DOI: http://dx.doi.org/10.4310/JOC.2014.v5.n2.a1

Authors

Michael Tait (Department of Mathematics, University of California at San Diego)

Craig Timmons (Department of Mathematics, University of California at San Diego)

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)$.

Keywords

Turan number, Sidon set, 4-cycle

Full Text (PDF format)