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.

History

The result was stated without proof by Erdős in 1964.^[1] 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.^[2]

Lower bounds

Unsolved problem in mathematics: Do there exist 2k-cycle-free graphs (for k other than 2, 3, or 5) that have Ω(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.^[2][3][4]

It is an 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.^[5] 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.^[4]

Constant factors

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

$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

$n^{1+1/k}\left(\frac{1}{2}+o(1)\right).$^[6]

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

$0.5338n^{4/3} \le \operatorname{ex}(n,C_6) \le 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.^[3] The maximum number of edges in a 10-cycle-free graph can be at least^[4]

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

The best proven upper bound on the number of edges, for 2k-cycle-free graphs for arbitrary values of k, is

$n^{1+1/k}\left(k-1+o(1)\right).$^[5]

References

1. Erdős, P. (1964), "Extremal problems in graph theory" (PDF), Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Publ. House Czechoslovak Acad. Sci., Prague, pp. 29–36, MR 0180500.
2. Bondy, J. A.; Simonovits, M. (1974), "Cycles of even length in graphs" (PDF), Journal of Combinatorial Theory, Series B, 16: 97–105, doi:10.1016/0095-8956(74)90052-5, MR 0340095.
3. Füredi, Zoltan; Naor, Assaf; Verstraëte, Jacques (2006), "On the Turán number for the hexagon", Advances in Mathematics, 203 (2): 476–496, doi:10.1016/j.aim.2005.04.011, MR 2227729.
4. Lazebnik, F.; Ustimenko, V. A.; Woldar, A. J. (1994), "Properties of certain families of 2k-cycle-free graphs", Journal of Combinatorial Theory, Series B, 60 (2): 293–298, doi:10.1006/jctb.1994.1020, MR 1271276.
5. Pikhurko, Oleg (2012), "A note on the Turán function of even cycles" (PDF), Proceedings of the American Mathematical Society, 140 (11): 3687–3692, doi:10.1090/S0002-9939-2012-11274-2, MR 2944709.
6. Erdős, P.; Simonovits, M. (1982), "Compactness results in extremal graph theory" (PDF), Combinatorica, 2 (3): 275–288, doi:10.1007/BF02579234, MR 698653.