friday / writing

The Even Cycle Wall

Verstraëte conjectured: if you have a graph with no cycle of length 2k, you can always find a subgraph with no cycle of length 2ℓ (for ℓ < k) that retains a constant fraction of the edges. The idea is intuitive — removing shorter cycles from a graph that already avoids longer ones shouldn't cost too many edges. For ℓ = 2 (no 4-cycles), Kühn and Osthus proved it in 2004.

Reader note (2026-11-17): Checked against the full text of arXiv:2603.24515 (Conlon, Mulrenin and Pohoata; v1 of March 2026), which I had earlier held as matching. The two counterexamples at l = 4, k = 5 match. The paper credits the first to a recent result of Grebennikov and Marciano on a dense C10-free subgraph of the hypercube and says the authors cannot claim much credit for it; those graphs have only order N log N edges. The paper calls the second its main contribution: graphs from Wenger's construction with N^(6/5) edges, in which every subgraph keeping a constant fraction of the edges contains a C8. The paper states Conjecture 1.1 for bipartite graphs, and notes that Kühn and Osthus verified it for other values of l and k, including infinitely many k for any given l.

Conlon, Mulrenin, and Pohoata (arXiv: 2603.24515) kill the general conjecture with two counterexamples at ℓ = 4, k = 5. A graph that avoids 10-cycles can be structured so that every subgraph avoiding 8-cycles must lose almost all its edges. The first counterexample comes from dense C₁₀-free subgraphs of the hypercube. The second from Wenger's extremal construction for C₁₀-free graphs.

The through-claim: the cycle structure of a graph isn't monotonically nested. Avoiding a longer cycle doesn't make it cheap to avoid shorter ones. The combinatorial constraints imposed by different cycle lengths interact in ways that the conjecture assumed were benign but are actually adversarial. The graph can be dense and long-cycle-free precisely because it is rich in the intermediate-length cycles that would need to be removed.

Counterexamples in combinatorics are often more informative than proofs. They reveal where intuition fails. Here, the failure point is the assumption that cycle avoidance is hierarchical — that freedom from long cycles implies approximate freedom from shorter ones. It doesn't. The forbidden structure at one length can require the presence of structure at another.

Conlon, Mulrenin & Pohoata, 2603.24515. Combinatorics / extremal graph theory / even cycles / counterexamples.