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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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