pith. sign in

arxiv: 2605.23301 · v1 · pith:YALAOHE2new · submitted 2026-05-22 · 🧮 math.CO

Finding blowups one vertex at a time

Jacob Fox , Yuval Wigderson , Yunkun Zhou This is my paper

Pith reviewed 2026-05-25 04:16 UTC · model grok-4.3

classification 🧮 math.CO
keywords Nikiforov theoremgraph blowupsextremal graph theoryiterative proofssubgraph countinglogarithmic order
0
0 comments X

The pith

A new iterative proof of Nikiforov's theorem improves the constant in the guaranteed size of H-blowups.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives a new proof of the theorem that any graph with sufficiently many copies of a fixed graph H must contain a large blowup of H. Previous proofs were non-iterative, but this one builds the blowup by adding one vertex at a time. This change allows a better lower bound on the order of the blowup in terms of the number of copies. The result strengthens a key connection between local subgraph counts and global structured subgraphs in extremal graph theory.

Core claim

If an N-vertex graph contains at least γ N^h copies of a fixed h-vertex graph H, then it contains an H-blowup of order c_H(γ) log N, where the new proof establishes a larger value of the constant c_H(γ) than was previously known.

What carries the argument

The iterative process of selecting successive vertices for the blowup while maintaining a positive density of potential copies.

Load-bearing premise

That the iterative selection of each next vertex can continue until the full logarithmic number of vertices is reached without the potential falling to zero.

What would settle it

A counterexample graph with γ N^h copies of H but whose largest H-blowup has order smaller than the improved c_H(γ) log N.

read the original abstract

An influential theorem of Nikiforov states that if an $N$-vertex graph $G$ contains at least $\gamma N^h$ copies of some fixed $h$-vertex graph $H$, then $G$ contains an $H$-blowup of order $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(\gamma)$. In contrast to previous proofs, our proof is iterative, finding the blowup one vertex at a time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript gives a new iterative proof of Nikiforov's theorem: any N-vertex graph containing at least γ N^h copies of a fixed h-vertex graph H contains an H-blowup on c_H(γ) log N vertices. The proof constructs the blowup vertex by vertex and obtains a strictly larger value of c_H(γ) than previous arguments.

Significance. If the quantitative improvement holds, the result strengthens the best-known bound in a central theorem of extremal graph theory. The iterative method supplies an explicit construction that may be useful for related embedding problems; the paper also ships a fully explicit (though still exponential) expression for the improved constant.

major comments (2)
  1. [§3, Lemma 3.2] §3, Lemma 3.2: the potential function Φ_t used to control the number of H-copies after t vertices have been chosen is defined with a multiplicative loss factor of (1-ε) per step; the paper must verify that the cumulative loss after Ω(log N) steps still leaves a positive-density copy count, otherwise the claimed improvement in c_H(γ) does not follow from the inductive step.
  2. [§4, Eq. (4.5)] §4, Eq. (4.5): the final lower bound on c_H(γ) is obtained by solving a recurrence whose base case depends on the initial copy density γ; a concrete numerical comparison with the previous best constant (e.g., from the proof in [reference]) is needed to confirm the improvement is strict rather than merely existential.
minor comments (2)
  1. [§3] The notation for the successive vertex sets V_1, …, V_t is introduced without an explicit inductive hypothesis statement; adding a displayed inductive claim at the beginning of §3 would improve readability.
  2. [Figure 1] Figure 1 caption refers to 'the blowup order' but the axis label is unlabeled; clarify that the vertical axis shows the guaranteed order as a function of log N.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive recommendation and the careful comments. We respond to each major comment below.

read point-by-point responses

  1. Referee: [§3, Lemma 3.2] §3, Lemma 3.2: the potential function Φ_t used to control the number of H-copies after t vertices have been chosen is defined with a multiplicative loss factor of (1-ε) per step; the paper must verify that the cumulative loss after Ω(log N) steps still leaves a positive-density copy count, otherwise the claimed improvement in c_H(γ) does not follow from the inductive step.

    Authors: The parameter ε is chosen as a function of the target iteration count t=Θ(log N) and the initial density γ (specifically ε=Θ(γ/log N)); the product ∏(1-ε) is then bounded below by a positive constant e^{-O(1)} independent of N. This calculation appears after the statement of Lemma 3.2 and ensures the final copy density remains Ω(γ). We will add a short explicit remark making the dependence of ε on log N and the resulting lower bound on the product fully transparent. revision: partial

  2. Referee: [§4, Eq. (4.5)] §4, Eq. (4.5): the final lower bound on c_H(γ) is obtained by solving a recurrence whose base case depends on the initial copy density γ; a concrete numerical comparison with the previous best constant (e.g., from the proof in [reference]) is needed to confirm the improvement is strict rather than merely existential.

    Authors: The closed-form solution of the recurrence in (4.5) is strictly larger than the constant obtained from earlier proofs for every fixed γ>0. To make the strict improvement concrete, the revised manuscript will include a short table comparing the new and previous numerical values of c_H(γ) for representative small γ and for H=K_3. revision: yes

Circularity Check

0 steps flagged

No circularity: direct new proof of external Nikiforov theorem via iterative vertex selection

full rationale

The paper supplies an independent iterative proof of an externally stated theorem (Nikiforov) whose conclusion is not obtained by fitting parameters inside the paper or by reducing to a self-citation chain. The claimed improvement on c_H(γ) is asserted to follow from the quantitative control in the new construction; no equation or step is shown to be definitionally equivalent to its own inputs. The derivation is therefore self-contained against the external benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper is a proof of an existing theorem; it introduces no new free parameters, invented entities, or non-standard axioms beyond ordinary graph-theoretic definitions.

axioms (1)
  • standard math Standard definitions and counting arguments in extremal graph theory (e.g., double counting of copies of H).
    Invoked implicitly by any proof of Nikiforov's theorem.

pith-pipeline@v0.9.0 · 5608 in / 1130 out tokens · 19356 ms · 2026-05-25T04:16:06.100098+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 2 canonical work pages

  1. [1]

    Balister, B

    P. Balister, B. Bollob´ as, M. Campos, S. Griffiths, E. Hurley, R. Morris, J. Sahasrabudhe, and M. Tiba, Upper bounds for multicolour Ramsey numbers,J. Amer. Math. Soc.39(2026), 765–780

    2026

  2. [2]

    Bollob´ as and P

    B. Bollob´ as and P. Erd˝ os, On the structure of edge graphs,Bull. London Math. Soc.5(1973), 317–321

    1973

  3. [3]

    Bollob´ as, P

    B. Bollob´ as, P. Erd˝ os, and M. Simonovits, On the structure of edge graphs. II,J. London Math. Soc. (2)12(1975/76), 219–224

    1975

  4. [4]

    Campos, S

    M. Campos, S. Griffiths, R. Morris, and J. Sahasrabudhe, An exponential improvement for diagonal Ramsey,Ann. of Math. (2)203(2026), 869–932

    2026

  5. [5]

    Conlon and J

    D. Conlon and J. Fox, Bounds for graph regularity and removal lemmas,Geom. Funct. Anal. 22(2012), 1191–1256

    2012

  6. [6]

    Conlon, J

    D. Conlon, J. Fox, and B. Sudakov, Erd˝ os–Hajnal-type theorems in hypergraphs,J. Combin. Theory Ser. B102(2012), 1142–1154

    2012

  7. [7]

    R. A. Duke, H. Lefmann, and V. R¨ odl, A fast approximation algorithm for computing the frequencies of subgraphs in a given graph,SIAM J. Comput.24(1995), 598–620

    1995

  8. [8]

    Erd˝ os, M

    P. Erd˝ os, M. Goldberg, J. Pach, and J. Spencer, Cutting a graph into two dissimilar halves, J. Graph Theory12(1988), 121–131

    1988

  9. [9]

    Erd¨ os and A

    P. Erd¨ os and A. H. Stone, On the structure of linear graphs,Bull. Amer. Math. Soc.52(1946), 1087–1091

    1946

  10. [10]

    Fox and L

    J. Fox and L. M. Lov´ asz, A tight lower bound for Szemer´ edi’s regularity lemma,Combinatorica 37(2017), 911–951

    2017

  11. [11]

    J. Fox, S. Luo, and Y. Wigderson, Extremal and Ramsey results on graph blowups,J. Comb. 12(2021), 1–15

    2021

  12. [12]

    J. Fox, H. T. Pham, and Y. Zhao, Tower-type bounds for Roth’s theorem with popular differ- ences,J. Eur. Math. Soc. (JEMS)25(2023), 3795–3831

    2023

  13. [13]

    Garbe and J

    F. Garbe and J. Hladk´ y, A tower lower bound for the degree relaxation of the regularity lemma, Comb. Theory5(2025), Paper No. 8, 17pp

    2025

  14. [14]

    Gir˜ ao, Z

    A. Gir˜ ao, Z. Hunter, and Y. Wigderson, Blowups of triangle-free graphs,Adv. Comb.(2025), Paper No. 10, 23pp

    2025

  15. [15]

    Gishboliner, A

    L. Gishboliner, A. Shapira, and Y. Wigderson, Is it easy to regularize a hypergraph with easy links?,Int. Math. Res. Not. IMRN(2026), Paper No. rnag018, 18pp

    2026

  16. [16]

    W. T. Gowers, Lower bounds of tower type for Szemer´ edi’s uniformity lemma,Geom. Funct. Anal.7(1997), 322–337

    1997

  17. [17]

    Green, A Szemer´ edi-type regularity lemma in abelian groups, with applications,Geom

    B. Green, A Szemer´ edi-type regularity lemma in abelian groups, with applications,Geom. Funct. Anal.15(2005), 340–376

    2005

  18. [18]

    Gupta, N

    P. Gupta, N. Ndiaye, S. Norin, and L. Wei, Optimizing the CGMS upper bound on Ramsey numbers, 2024. Preprint available at arXiv:2407.19026

    work page arXiv 2024

  19. [19]

    Hosseini, S

    K. Hosseini, S. Lovett, G. Moshkovitz, and A. Shapira, An improved lower bound for arithmetic regularity,Math. Proc. Cambridge Philos. Soc.161(2016), 193–197

    2016

  20. [20]

    Kalyanasundaram and A

    S. Kalyanasundaram and A. Shapira, A Wowzer-type lower bound for the strong regularity lemma,Proc. Lond. Math. Soc. (3)106(2013), 621–649. 20

    2013

  21. [21]

    K¨ ovari, V

    T. K¨ ovari, V. T. S´ os, and P. Tur´ an, On a problem of K. Zarankiewicz,Colloq. Math.3(1954), 50–57

    1954

  22. [22]

    Morris, Some recent results in Ramsey theory, 2026

    R. Morris, Some recent results in Ramsey theory, 2026. Preprint available at arXiv:2601.05221

    work page arXiv 2026

  23. [23]

    Moshkovitz and A

    G. Moshkovitz and A. Shapira, A short proof of Gowers’ lower bound for the regularity lemma, Combinatorica36(2016), 187–194

    2016

  24. [24]

    Moshkovitz and A

    G. Moshkovitz and A. Shapira, A sparse regular approximation lemma,Trans. Amer. Math. Soc.371(2019), 6779–6814

    2019

  25. [25]

    Moshkovitz and A

    G. Moshkovitz and A. Shapira, A tight bound for hypergraph regularity,Geom. Funct. Anal. 29(2019), 1531–1578

    2019

  26. [26]

    Nikiforov, Graphs with many copies of a given subgraph,Electron

    V. Nikiforov, Graphs with many copies of a given subgraph,Electron. J. Combin.15(2008), Note 6, 6pp

    2008

  27. [27]

    Nikiforov, Graphs with manyr-cliques have large completer-partite subgraphs,Bull

    V. Nikiforov, Graphs with manyr-cliques have large completer-partite subgraphs,Bull. Lond. Math. Soc.40(2008), 23–25

    2008

  28. [28]

    R¨ odl and M

    V. R¨ odl and M. Schacht, Complete partite subgraphs in dense hypergraphs,Random Structures Algorithms41(2012), 557–573

    2012

  29. [29]

    Shapira and R

    A. Shapira and R. Yuster, On the density of a graph and its blowup,J. Combin. Theory Ser. B100(2010), 704–719

    2010

  30. [30]

    Souza, Blowup Ramsey numbers,European J

    V. Souza, Blowup Ramsey numbers,European J. Combin.92(2021), Paper No. 103238, 14pp

    2021

  31. [31]

    Szemer´ edi, Regular partitions of graphs, inProbl` emes combinatoires et th´ eorie des graphes (Colloq

    E. Szemer´ edi, Regular partitions of graphs, inProbl` emes combinatoires et th´ eorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976),Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, 399–401

    1976

  32. [32]

    Wigderson, Upper bounds on diagonal Ramsey numbers [after Campos, Griffiths, Morris, and Sahasrabudhe],Ast´ erisque462(2025), 85–138

    Y. Wigderson, Upper bounds on diagonal Ramsey numbers [after Campos, Griffiths, Morris, and Sahasrabudhe],Ast´ erisque462(2025), 85–138. AppendixA.Proof of Lemma 6.1 In this section, we present the proof of Lemma 6.1. Before doing so, we recall a number of concepts and results related to Szemer´ edi’s regularity lemma. Givenε∈(0,1), a pair of vertex sets ...

    2025