Strong counterexamples to a supersaturation question of Ma–Yuan

Abstract

For a graph 𝐹 , let ℎ 𝐹 ⁡ ( 𝑛 , 𝑞 ) be the minimum number of copies of 𝐹 in an 𝑛 -vertex graph with e x ⁡ ( 𝑛 , 𝐹 ) + 𝑞 edges, where e x ⁡ ( 𝑛 , 𝐹 ) is the maximum number of edges in an 𝑛 -vertex 𝐹 -free graph. Let 𝑐 ⁡ ( 𝑛 , 𝐹 ) be the minimum number of copies obtained by adding one edge to an extremal 𝐹 -free graph. Mubayi’s supersaturation conjecture predicts, under a stability hypothesis, that ℎ 𝐹 ⁡ ( 𝑛 , 𝑞 ) ≥ 𝑞 ⁢ 𝑐 ⁡ ( 𝑛 , 𝐹 ) . Ma and Yuan recently constructed stable graph counterexamples for every fixed 𝑞 ≥ 4 ; they asked whether the one-edge equality ℎ 𝐹 ⁡ ( 𝑛 , 1 ) = 𝑐 ⁡ ( 𝑛 , 𝐹 ) might still hold for every graph 𝐹 containing a cycle. We give a negative answer to their question. For each integer 𝑡 ≥ 6 , let 𝐻 𝑡 be obtained from the 𝑡 -vertex path by replacing each edge with a 3 ⁢ 𝑡 -page book, using disjoint page vertices for different path edges. Then ℎ 𝐻 𝑡 ⁡ ( 𝑛 , 1 ) < 𝑐 ⁡ ( 𝑛 , 𝐻 𝑡 ) for infinitely many values of 𝑛 . Moreover, by taking 𝑡 large, the ratio ℎ 𝐻 𝑡 ⁡ ( 𝑛 , 1 ) / 𝑐 ⁡ ( 𝑛 , 𝐻 𝑡 ) can be made arbitrarily small along infinitely many values of 𝑛 .

The authors' abstract, as published at the source. European Journal of Combinatorics, 2026 · DOI ↗