Contents Online

# 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

#### 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