Two counterexamples to a conjecture about even cycles

David Conlon, Eion Mulrenin, Cosmin Pohoata · 2026

Read Two counterexamples to a conjecture about even cycles by David Conlon, Eion Mulrenin, Cosmin Pohoata (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-24515.txt.

Introduction

Conlon and co-authors give two counterexamples to a conjecture of Verstraëte about even cycles in graphs. The conjecture says any graph with no cycle of length 2k should contain a subgraph, free of cycles of length 2l, that keeps a fixed share of the edges. It was proved for l equal to 2 by Kühn and Osthus in 2004. The new counterexamples cover l equal to 4 and k equal to 5. One comes from a dense cycle-free subgraph of the hypercube, the other from Wenger's extremal construction.

Catalog record

CREATORDavid Conlon, Eion Mulrenin, Cosmin Pohoata
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18218
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.24515

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Two counterexamples to a conjecture about even cycles Thanks: The first author was supported by NSF Award DMS-2348859 and the third author was supported by NSF Award DMS-2246659. David Conlon, Eion Mulrenin, Cosmin Pohoata Abstract . A conjecture of Verstraëte states that for any fixed ℓ < k \ell<k there exists a positive constant c c such that any C 2 ​ k C_{2k} -free graph G G contains a C 2 ​ ℓ C_{2\ell} -free subgraph with at least c ​ | E ⁡ ( G ) | c|E(G)| edges. For ℓ = 2 \ell=2 , this conjecture was verified by Kühn and Osthus in 2004. We identify two counterexamples to this conjecture for ℓ = 4 \ell=4 and k = 5 k=5 : the first comes from a recent construction of a dense C 10 C_{10} -free subgraph of the hypercube and the second from Wenger’s construction for extremal C 10 C_{10} -free graphs. 1. Introduction For a family \mathscr{F} of graphs and a positive integer n , the extremal number \operatorname{ex}(n,\mathscr{F}) is the maximum number of edges in an n -vertex graph which contains no member of \mathscr{F} as a subgraph. Trivially, \operatorname{ex}(n,\mathscr{F})\leq\operatorname{ex}(n,F) for all F\in\mathscr{F} . Conversely, the compactness conjecture of Erdős and Simonovits [ 8 ] asserts that if \mathscr{F} is a finite family which does not contain a forest or, equivalently, if \operatorname{ex}(n,F)=\Omega(n^{1+\varepsilon}) for some \varepsilon>0 and all F\in\mathscr{F} , 1 1 1 Without this hypothesis, families such as \mathscr{F}=\{K_{1,2},2K_{2}\} , where 2K_{2} is a matching with two edges, give simple counterexamples. See for example [ 16 ] for more details. then there is some F\in\mathscr{F} such that \operatorname{ex}(n,F)=O(\operatorname{ex}(n,\mathscr{F})) . This conjecture is of most interest when the family \mathscr{F} includes bipartite graphs, since a celebrated result of Erdős and Stone [ 9 ] asymptotically determines the behavior of the extremal number for all non-bipartite graphs. In particular, one might ask whether the conjecture holds for the family \mathscr{C}_{2k}:=\{C_{3},C_{4},\dots,C_{2k}\} of all cycles of length at most 2k , where it is essentially asking if \operatorname{ex}(n,C_{2k})=O(\operatorname{ex}(n,\mathscr{C}_{2k})) — see, for example, [ 14 , Conjecture IV] for an explicit statement of this question as a conjecture. Despite the fact [ 3 ] that both of these functions are known to be O(n^{1+1/k}) , this simple question of whether they agree up to a constant has only been resolved for k\in\{2,3,5\} , with the corresponding lower bounds in these cases witnessed by the so-called generalized polygons [ 13 ] . Inspired by this problem, a number of natural extremal questions about the relationships between graphs avoiding particular even cycles have been studied. One of the first results in this vein was a theorem of Győri [ 11 ] , who proved that every C_{6} -free bipartite graph G contains a C_{4} -free subgraph with at least \frac{1}{2}|E(G)| edges. Several years later, Kühn and Osthus [ 12 ] extended Győri’s result by proving that for all k\geq 3 , every C_{2k} -free bipartite 2 2 2 By the elementary fact that any graph can be made bipartite by deleting at most half the edges, this theorem remains true for non-bipartite G , but at the cost of an extra factor of 1/2 . graph G has a C_{4} -free subgraph with at least \frac{1}{k-1}e(G) edges. In the same paper [ 12 ] , Kühn and Osthus stated the following conjecture, which they attribute to Verstraëte (cf. [ 14 , Conjecture VIII] ) and which would easily imply that \operatorname{ex}(n,C_{2k})=O(\operatorname{ex}(n,\mathscr{C}_{2k})) , saying that their theorem should extend to all pairs of even cycles. Conjecture 1.1 . For all integers 2\leq\ell<k , there exists a positive constant c such that every C_{2k} -free bipartite graph G has a C_{2\ell} -free subgraph F with |E(F)|\geq c|E(G)| . Kühn and Osthus also verified this conjecture for other values of \ell and k , including, for any given \ell , infinitely many values of k . Despite this evidence for the conjecture, our first result says that arbitrarily large counterexamples exist for C_{8} and C_{10} . Theorem 1.2 . For any positive constant c and any positive integer N_{0} , there exists an integer N\geq N_{0} and a C_{10} -free bipartite graph G on N vertices with the property that every subgraph with at least c|E(G)| edges contains a C_{8} . We cannot claim much credit for this construction, as it is a straightforward consequence of a beautiful recent result by Grebennikov and Marciano [ 10 ] of a dense C_{10} -free subgraph of the hypercube. However, as the graphs G in Theorem 1.2 have only \Theta(N\log N) edges, it is natural to wonder whether denser counterexamples exist. Our second result, which is our main contribution, confirms this, showing that there is a family of counterexamples with essentially the maximum possible number of edges. Theorem 1.3 . For any positive constant c and any positive integer N_{0} , there exists an integer N\geq N_{0} and a C_{10} -free bipartite graph W with N vertices on each side, N^{6/5} edges and the property that every subgraph with at least c|E(W)| edges contains a C_{8} . We will take the graphs W to be those from Wenger’s construction [ 15 ] for extremal C_{10} -free graphs, which we describe in Section 3 below. 2. Proof of Theorem 1.2 Here and throughout, Q_{n} denotes the n -dimensional hypercube with 2^{n} vertices and n2^{n-1} edges and, for graphs G and H , \operatorname{ex}(G,H) denotes the maximum number of edges in an H -free subgraph of G . Theorem 1.2 is an immediate consequence of the following two theorems. Theorem 2.1 (Grebennikov and Marciano, 2025 [ 10 ] ) . For every positive integer n , there is a subgraph F_{n} of Q_{n} which is C_{10} -free and has |E(F_{n})|>0.024|E(Q_{n})| . Theorem 2.2 (Chung, 1992 [ 4 ] ) . \operatorname{ex}(Q_{n},C_{8})=o(|E(Q_{n})|) . Proof of Theorem 1.2 . Suppose for the sake of contradiction that there is c>0 such that every C_{10} -free bipartite graph G has a C_{8} -free subgraph with at least c|E(G)| edges. Taking such a subgraph of the graph F_{n} , which is a subgraph of Q_{n} and so necessarily bipartite, from Theorem 2.1 for each n , we obtain a sequence of C_{8} -free subgraphs of Q_{n} containing at least 0.024c|E(Q_{n})| edges of Q_{n} , contradicting Theorem 2.2 . ∎ For the interested reader, we include a brief sketch of the construction of the graphs F_{n} in Theorem 2.1 , which was itself inspired by the recent work of Ellis, Ivan, and Leader [ 7 ] on the Turán densities of daisies. The main task is to construct a subgraph of Q_{n} of positive relative density with no copy of C_{6}^{-} , the graph obtained by removing an edge from a copy of C_{6} in Q_{n} . Note that every C_{6}^{-} is a path of length five, but not every path of length five is a C_{6}^{-} . This is sufficient because of the inequality \operatorname{ex}(Q_{n},C_{10})\geq\frac{1}{3}\cdot\operatorname{ex}^{*}(Q_{n},C_{6}^{-}) noted by Axenovich, Martin, and Winter [ 1 ] , where \operatorname{ex}^{*}(Q_{n},C_{6}^{-}) denotes the maximum number of edges in a subgraph of Q_{n} with no C_{6}^{-} . Grebennikov and Marciano construct the required subgraph as follows: • First

Read the complete text