Even circuit theorem

In extremal graph theory, the even circuit theorem is a result of Paul Erdős according to which an n-vertex graph that does not have a simple cycle of length 2k can only have O(n^{1 + 1/k}) edges. For instance, 4-cycle-free graphs have O(n^3/2) edges, 6-cycle-free graphs have O(n^4/3) edges, etc.

The result was stated without proof by Erdős in 1964.¹ Bondy & Simonovits (1974) published the first proof, and strengthened the theorem to show that, for n-vertex graphs with Ω(n^{1 + 1/k}) edges, all even cycle lengths between 2k and 2kn^1/k occur.²

Unsolved problem in mathematics

Do there exist ${\displaystyle 2k}$-cycle-free graphs (for ${\displaystyle k}$ other than ${\displaystyle 2}$, ${\displaystyle 3}$, or ${\displaystyle 5}$) that have ${\displaystyle \Omega (n^{1+1/k})}$ edges?

More unsolved problems in mathematics

The bound of Erdős's theorem is tight up to constant factors for some small values of k: for k = 2, 3, or 5, there exist graphs with Ω(n^{1 + 1/k}) edges that have no 2k-cycle.²³⁴

It is unknown for k other than 2, 3, or 5 whether there exist graphs that have no 2k-cycle but have Ω(n^{1 + 1/k}) edges, matching Erdős's upper bound.⁵ Only a weaker bound is known, according to which the number of edges can be Ω(n^{1 + 2/(3k − 3)}) for odd values of k, or Ω(n^{1 + 2/(3k − 4)}) for even values of k.⁴

Because a 4-cycle is a complete bipartite graph, the maximum number of edges in a 4-cycle-free graph can be seen as a special case of the Zarankiewicz problem on forbidden complete bipartite graphs, and the even circuit theorem for this case can be seen as a special case of the Kővári–Sós–Turán theorem. More precisely, in this case it is known that the maximum number of edges in a 4-cycle-free graph is

${\displaystyle n^{3/2}\left({\frac {1}{2}}+o(1)\right).}$

Erdős & Simonovits (1982) conjectured that, more generally, the maximum number of edges in a 2k-cycle-free graph is

${\displaystyle n^{1+1/k}\left({\frac {1}{2}}+o(1)\right).}$⁶

However, later researchers found that there exist 6-cycle-free graphs and 10-cycle-free graphs with a number of edges that is larger by a constant factor than this conjectured bound, disproving the conjecture. More precisely, the maximum number of edges in a 6-cycle-free graph lies between the bounds

${\displaystyle 0.5338n^{4/3}\leq \operatorname {ex} (n,C_{6})\leq 0.6272n^{4/3},}$

where ex(n,G) denotes the maximum number of edges in an n-vertex graph that has no subgraph isomorphic to G.³ The maximum number of edges in a 10-cycle-free graph can be at least⁴

${\displaystyle 4\left({\frac {n}{5}}\right)^{6/5}\approx 0.5798n^{6/5}.}$

For general values of k, Pikhurko proved the following upper bound

${\displaystyle \operatorname {ex} (n,C_{2k})\leq (k-1+o(1))n^{1+1/k}.}$⁵

Bukh and Jiang later improved the dependence on k to

${\displaystyle \operatorname {ex} (n,C_{2k})\leq \left(80{\sqrt {k}}\log k+o(1)\right)n^{1+1/k}.}$⁷

This bound was further improved by He to

${\displaystyle \operatorname {ex} (n,C_{2k})\leq \left(16{\sqrt {5}}{\sqrt {k\log k}}+o(1)\right)n^{1+1/k}.}$⁸