A note on the Turán function of even cycles

By Oleg Pikhurko. 2012

69 citations recorded by the source corpus.

The Tur´an function ex(n, F) is the maximum number of edges in an F-free graph on n vertices. The question of estimating this function for F = C2k, the cycle of length 2k, is one of the central open questions in this area that goes back to the 1930s. We prove that ex(n,C2k) ≤ (k − 1) n1+1/k + 16(k − 1)n, improving the previously best known general upper bound of Verstra¨ete [Combin. Probab. Computing 9 (2000), 369–373] by a factor 8 + o(1) when n � k.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/f836e3b921d522599f08b5fda59c1102b34a86f2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Jacques Verstraëte
2. Robert Morris
3. David Saxton
4. Miklós Simonovits
5. Z. Furedi
6. Peter Keevash
7. Sam Mattheus
8. Wojciech Samotij

In Discrete Mathematics and Combinatorics

1. Jacques Verstraëte
2. Robert Morris
3. David Saxton
4. Z. Furedi
5. Miklós Simonovits
6. Peter Keevash
7. Sam Mattheus
8. Wojciech Samotij

In Electrical and Electronic Engineering

1. Z. Furedi
2. David Saxton
3. Miklós Simonovits
4. Jacques Verstraëte
5. Robert Morris
6. Peter Keevash

Citations in the corpus

• Extremal problems for cycles in graphs (2016, methodology): “A number of improvements of the value of ck were obtained, including by the author [133], Pikhurko [108] and Bukh and Jiang [15], who showed ck = O( √ k log k), answering a question of Bondy who asked if ck = o(k).”
• A survey on spectral conditions for some extremal graph problems (2021, unknown): “• (Pikhurko [167]) ex(n,C2k) ≤ (k − 1)n1+1/k + 16(k − 1)n.”
• The History of Degenerate (Bipartite) Extremal Graph Problems (2013, background): “icative constant of the upper bound in the Bondy-Simonovits theorem was improved by Verstra¨ete [246] from 100 to 8. The best known upper bound today is that of Oleg Pikhurko: Theorem 4.13 (Pikhurko, [203]). ex(n,C 2k) ≤ (k−1)n1+(1/k) + 16(k−1)n. Historical Remark 1. (a) Pikhurko, in his very nice p”
• The number of $C_{2l}$-free graphs (2013, background): “raph H. 2The first published proof of this bound was given by Bondy and Simonovits [12], but they attribute the result to Erdo˝s, see also [22] and [31, Theorem 4.6]. For more recent improvements, see [15, 45, 53]. THE NUMBER OF C2ℓ-FREE GRAPHS 3 was therefore natural for Erd˝os to conjecture that, f”