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 $2 k$ 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 $2 k$ and $2 kn 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

\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 $2 k$ -cycle.^[2]^[3]^[4]

It is unknown for $k$ other than 2, 3, or 5 whether there exist graphs that have no $2 k$ -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/(3 k - 3))$ for odd values of $k$ , or $Ω(n 1 + 2/(3 k - 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 $2 k$ -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}\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$ .^[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.5798n^{6/5}.

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

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

^[5]

References

^ 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.
^ ^a ^b 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.
^ ^a ^b 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.
^ ^a ^b ^c Lazebnik, F.; Ustimenko, V. A.; Woldar, A. J. (1994), "Properties of certain families of $2 k$ -cycle-free graphs", Journal of Combinatorial Theory, Series B, 60 (2): 293–298, doi:10.1006/jctb.1994.1020, MR 1271276.
^ ^a ^b 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.
^ Erdős, P.; Simonovits, M. (1982), "Compactness results in extremal graph theory" (PDF), Combinatorica, 2 (3): 275–288, doi:10.1007/BF02579234, MR 0698653, archived from the original (PDF) on 2016-03-04, retrieved 2015-11-06.

[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.

[bs74-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.

[fnv06-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.

[luw94-4] Lazebnik, F.; Ustimenko, V. A.; Woldar, A. J. (1994), "Properties of certain families of $2 k$ -cycle-free graphs", Journal of Combinatorial Theory, Series B, 60 (2): 293–298, doi:10.1006/jctb.1994.1020, MR 1271276.

[p12-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 0698653, archived from the original (PDF) on 2016-03-04, retrieved 2015-11-06.

[1]

[2]

[3]

[4]

[5]

[6]