Finding blowups one vertex at a time

Jacob Fox, Yuval Wigderson, Yunkun Zhou · 2026

Read Finding blowups one vertex at a time by Jacob Fox, Yuval Wigderson, Yunkun Zhou (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-2605-23301.txt.

Introduction

Fox, Wigderson, and Zhou provide a new proof of Nikiforov theorem. It states that if an N-vertex graph contains at least gamma N to the power h instances of some fixed h-vertex graph H, so G contains an H-blowup. The blowup has order c sub H of gamma times log N. Their proof improves the top known bound on the constant c sub H of gamma. In contrast to previous proofs, their proof is iterative, locating the blowup one vertex at a time.

Catalog record

CREATORJacob Fox, Yuval Wigderson, Yunkun Zhou
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90726
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

Finding blowups one vertex at a time Thanks: JF: Department of Mathematics, Stanford University, Stanford, CA 94305. Email: [email protected] . Research supported by NSF awards DMS-2154129 and DMS-2452737. YW: Institute for Theoretical Studies, ETH Zürich, 8006 Zürich, Switzerland. Email: yuval.wigderson@eth-its. ethz.ch . Research supported by Dr. Max Rössler, the Walter Haefner Foundation, and the ETH Zürich Foundation. YZ: Email: [email protected] . Jacob Fox, Yuval Wigderson, Yunkun Zhou Abstract . An influential theorem of Nikiforov states that if an N N -vertex graph G G contains at least γ ​ N h \gamma N^{h} copies of some fixed h h -vertex graph H H , then G G contains an H H -blowup of order c H ​ ( γ ) ​ log ⁡ N c_{H}(\gamma)\log N . We provide a new proof of this theorem, which in particular improves the best known bound on the constant c H ​ ( γ ) c_{H}(\gamma) . In contrast to previous proofs, our proof is iterative, finding the blowup one vertex at a time. 1. Introduction Given an integer t and a graph H , its t -blowup H[t] is the graph obtained from H by replacing every vertex by an independent set of order t , and every edge by a complete bipartite graph between the two corresponding independent sets. Blowups occupy a central role in extremal graph theory, and many of the field’s central theorems can be phrased as statements about blowups, including the Erdős–Stone theorem [ 9 ] and the Kővári–Sós–Turán theorem [ 21 ] , which states that if an N -vertex graph contains at least \gamma N^{2} copies of K_{2} (i.e. edges), then it contains a copy of K_{2}[t] , for t=\Omega_{\gamma}(\log N) . The following remarkable and influential theorem of Nikiforov [ 27 , 26 ] extends this to yield a large blowup of any graph. Theorem 1.1 . Let H be an h -vertex graph and let \gamma>0 . If N is sufficiently large, then every N -vertex graph with at least \gamma N^{h} copies of H contains an H -blowup H[t] , where t\geqslant c_{H}(\gamma)\log N, and c_{H}(\gamma)>0 is a constant depending only on \gamma and H . By considering a random graph with edge density \gamma^{1/e(H)} , it is not hard to show that this result is best possible up to the value of c_{H}(\gamma) for nonempty H . Nikiforov’s theorem has several important consequences, among them a short proof of the Bollobás–Erdős–Simonovits theorem [ 2 , 3 ] . Nikiforov’s original proof of Theorem 1.1 is very short and elegant, and the technique he introduced to prove it has since found many other applications (e.g. [ 6 , 30 ] ). Nevertheless, Theorem 1.1 occupies a bit of an unusual space in the theory, because several natural variants of it, though easy to conjecture, appear extremely difficult to prove. Most notably, the extension of Theorem 1.1 to hypergraphs remains an outstanding open problem, whose resolution would have a number of interesting applications. Because of this, there has been a great deal of interest in providing alternative proofs of Theorem 1.1 , in the hopes that new perspectives would shed greater light on the problem, and hopefully lead to techniques that are more widely applicable. In particular, there is a lot of interest in understanding the quantitative aspects of Theorem 1.1 , and specifically in determining the behavior c_{H}(\gamma) as a function of \gamma (this question was perhaps first explicitly raised in [ 29 , Problem 2] ). We henceforth use the notation c_{H}(\gamma) to denote the optimal constant in Theorem 1.1 , that is, the supremum over all c>0 such that every N -vertex graph with at least \gamma N^{h} copies of H contains an H -blowup of size (c-o(1))\log N , where the o(1)\to 0 as N\to\infty . The only known upper bound on c_{H}(\gamma) , from an elementary analysis of the random graph G(n,\gamma^{1/e(H)}) , shows that c_{H}(\gamma)=O_{H}(1/{\log\frac{1}{\gamma}}) . By contrast, Nikiforov’s proof yields a polynomial lower bound, namely c_{H}(\gamma)=\Omega_{H}(\gamma^{h}) for every 1 1 1 Nikiforov actually only claimed this bound [ 27 ] for H=K_{h} , and the weaker bound c_{H}(\gamma)=\Omega_{H}(\gamma^{h^{2}}) for a general h -vertex graph [ 26 ] . However, it is not hard to see that the result for cliques immediately implies the same bound for all graphs (see Proposition 6.4 below). h -vertex graph H . This is a rather wide gap, and reflects our poor understanding of the problem. In particular, if the logarithmic upper bound does not give the true value of c_{H}(\gamma) , meaning that there is a better construction than a random graph, this may explain the difficulty of extending Theorem 1.1 to other settings, as the heuristics driving the various conjectural extensions of Nikiforov’s theorem often rely on the intuition coming from random graphs and hypergraphs. Motivated by the twin goals of finding new proofs of Theorem 1.1 , and of improving the bounds on c_{H}(\gamma) , many researchers have studied this problem. The first improvement was due to Rödl and Schacht [ 28 ] , who gave a new proof of Theorem 1.1 , and in so doing proved that 2 2 2 Here and in what follows, a o(1) in the exponent represents a quantity tending to 0 as \gamma\to 0 . c_{H}(\gamma)\geqslant\gamma^{1+o(1)} for every graph H . While still polynomial, their bound is much better than Nikiforov’s bound of \gamma^{h} , and in particular the exponent is independent of H . This bound was further slightly improved by Fox, Luo, and Wigderson [ 11 ] , to c_{H}(\gamma)\geqslant\gamma^{1-1/e(H)+o(1)} , yielding a small power savings depending on H . Finally, Girão, Hunter, and Wigderson [ 14 ] recently proved that c_{H}(\gamma)=\Theta_{H}(1/{\log\frac{1}{\gamma}}) whenever H is triangle-free, thus completely resolving the problem in this case. Our main result in the present paper is a further polynomial improvement for all graphs. Theorem 1.2 . For every graph H , we have c_{H}(\gamma)\geqslant\gamma^{1/2+o(1)} . More precisely, if H has h vertices and N is sufficiently large with respect to \gamma , then every N -vertex graph with at least \gamma N^{h} copies of H contains an H -blowup H[t] , where t\geqslant\frac{\delta_{H}\sqrt{\gamma}}{(\log\frac{1}{\gamma})^{2}}\log N and \delta_{H}>0 is a constant depending only on H . In particular, our result is the first to obtain a power savings over the Rödl–Schacht bound that is independent of H . However, we believe that our main contribution is not the precise bound c_{H}(\gamma)\geqslant\gamma^{1/2+o(1)} , but rather the new technique we introduce, and we are hopeful that this technique will prove useful in related settings. We provide a detailed overview of our technique in Section 2 , but let us briefly remark on the differences between our approach and previous ones. Like all of the previous proofs [ 27 , 26 , 28 , 11 , 14 ] , we find the parts of the blowup H[t] one at a time. However, in these earlier proofs, each blowup part is found in a “one-shot” way, by applying (a variant of) the Kővári–Sós–Turán theorem to some appropriate auxiliary bipartite graph. In our approach, by contrast, we find the t vertices of a part of H[t] one vertex at a time,

Read the complete text