Upper bounds on the extremal number of the 4-cycle

2021/07/24 by Ma, Jie, Yang, Tianchi
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2107.11601

Abstract

We obtain some new upper bounds on the maximum number f(n) of edges in n-vertex graphs without containing cycles of length four. This leads to an asymptotically optimal bound on f(n) for a broad range of integers n as well as a disproof of a conjecture of Erdős from 1970s which asserts that f(n)=\frac12 n^3/2+\frac14 n+o(n).

Related

• On extremal numbers of the triangle plus the four-cycle
• Extremal numbers of cycles revisited
• The extremal number of cycles with all diagonals
• A Lower Bound for the Number of Edges in a Graph Containing No Two Cycles of the Same Length
• Graphs without repeated cycle lengths