Sidon Sets and graphs without 4-cycles

2013/09/24 by Tait, Michael, Timmons, Craig · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1309.6350

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² - q - 2 vertices that does not contain a 4-cycle and has at least (1)/(2)q³ - q² - O(q^3/4) edges. This disproves a conjecture of Abreu, Balbuena, and Labbate concerning the Turán number ex(q² - q - 2, C₄).

Cited by

• New constructions and bounds for nonabelian Sidon sets with applications to Turán-type problems

Related

• Sidon sets and C₄-saturated graphs
• Extremal graphs without exponentially-small bicliques
• Non-repeated cycle lengths and Sidon sequences
• Extremal Graphs Without 4-Cycles
• On the Turán number of the hypercube