Nikiforov's counting-to-blowup theorem — a graph with a constant fraction of the possible copies of H contains a genuine blow-up H[t] with t = Θ(log n), and the open 'hypergraph Nikiforov' generalization

Statement

Theorem (Nikiforov, clique case; Bull. London Math. Soc. 40(1) (2008), 23–25, arXiv:math/0703554). Let $r\ge 2$, $c>0$, and let $G$ be a graph on $n$ vertices with $cr\ln n\ge1$. If $G$ has at least $cn^r$ cliques on $r$ vertices, then $G$ contains a complete $r$-partite subgraph $K_r(s,\dots,s,t)$ with $$s=\lfloor c^r\ln n\rfloor,\qquad t> n^{1-c^{r-1}}.$$ (Exact statement transcribed from the primary source, Theorem 1.)

Theorem (Nikiforov, general-subgraph case; Electron. J. Combin. 15 (2008), #R6, as restated by Fox–Luo–Wigderson arXiv:1912.08328, Theorem 3). For every $\eta>0$ and every graph $H$ on $k$ vertices, there is $\lambda>0$ such that for all sufficiently large $n$: every $n$-vertex graph $G$ with at least $\eta n^k$ copies of $H$ contains a blow-up $H[t]$ (every vertex of $H$ replaced by an independent set of size $t$, every edge by a complete bipartite graph) with $t=\lambda\log n$. One can take $\lambda=\eta^k$ if $H$ is a clique, and $\lambda=\eta^{k^2}$ for arbitrary $H$. (Fox–Luo–Wigderson improve the general-$H$ dependence to $\lambda=\eta^{1-1/|E(H)|+o(1)}$ via a regularity-lemma argument, but the *qualitative* $t=\Theta(\log n)$ conclusion is Nikiforov's.)

Corollary — quantitative Erdős–Stone(–Bollobás). Any $n$-vertex $G$ with $e(G)\ge(1-1/r+c)n^2/2$ edges contains $K_{r+1}(s,\dots,s,t)$ with $s=\lfloor(c/r^r)^{r+1}\ln n\rfloor$, $t>n^{1-(c/r^r)^r}$ — obtained by first converting the edge-density hypothesis into an $(r+1)$-clique-count hypothesis via the Khadzhiivanov–Nikiforov recursive clique-count inequality $\frac{(s+1)k_{s+1}(G)}{sk_s(G)}-\frac ns\ge\frac{sk_s(G)}{(s-1)k_{s-1}(G)}-\frac{n}{s-1}$ (their 1978 Serdica paper), then applying the clique-case theorem above with $r\to r+1$.

Not to confuse with — Nikiforov's own $r$-uniform hypergraph edge-density theorem (arXiv:0711.1185, "Complete $r$-partite subgraphs of dense $r$-graphs," Discrete Math. 309(14) (2009)): for $r\ge3$, $(\ln n)^{-1/(r-1)}\le\alpha\le r^{-3}$, every $r$-uniform hypergraph on $n$ vertices with $\ge\alpha n^r/r!$ edges (not cliques-of-cliques — a single-level edge count) contains a complete $r$-partite $r$-graph $K_r(s,\dots,s,t)$ with $s=\lfloor\alpha(\ln n)^{1/(r-1)}\rfloor$, $t=\lceil n^{1-\alpha^{r-2}}\rceil$. This refines Erdős's 1964 result and is a proved theorem, single-uniformity, about edge-density forcing a blow-up of the complete $r$-partite $r$-graph itself — a different object from the conjecture below.

Open — the "hypergraph Nikiforov" conjecture (informally proposed, not yet a citable paper: forum comment by Zach Hunter on erdosproblems.com's discussion of Erdős #161, 18 Oct 2025, quoted verbatim): *For any $r$-uniform hypergraph $H$ and $c>0$, there exists $\delta>0$ so that if an $n$-vertex $r$-uniform hypergraph $G$ contains $\ge cn^{|V(H)|}$ copies of $H$, then $G$ contains a $t$-blow-up of $H$ with $t>\delta(\log n)^{1/(r-1)}$.* For $r=2$ this reduces exactly to the graph-case theorem above ($t=\Theta(\log n)$). It is open for $r\ge3$ in general. The partial result of Conlon–Fox–Sudakov (arXiv:0901.3912/1104.5544, resolving the $t=3$ case of Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0?) works by "standard hypergraph Turán," which only delivers the *weaker* exponent $t>\delta(\log n)^{1/(|V(H)|-1)}$ (using $|V(H)|-1$, which is $\ge r-1$, in the denominator) rather than the conjectured $t>\delta(\log n)^{1/(r-1)}$ — so even the special case realized in the literature is not yet the full conjectured strength.

Facts

- Tightness. Nikiforov notes (Remarks, arXiv:math/0703554) that random-graph constructions show most $n$-vertex graphs contain no complete bipartite subgraph with both parts larger than $C\log n$ for a fixed $C$; so the $\Theta(\log n)$ order of the blow-up size in the clique-case theorem is essentially best possible — it cannot be improved to any polynomial $n^\varepsilon$. - The theorem strictly strengthens ordinary supersaturation (Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983)): supersaturation only guarantees $\Omega(n^{|V(H)|})$ *copies* of $H$ once the density exceeds the Turán threshold; Nikiforov's theorem upgrades "many copies" to "the copies organize into one genuine blow-up $H[t]$ with $t$ growing (logarithmically) with $n$" — a structural, not just a counting, conclusion. - Proof mechanism is a convexity/double-counting argument, not probabilistic sampling — despite delivering the same qualitative flavor of result as Dependent random choice — pick a small random test-tuple, take its common neighborhood; the resulting set is large and almost every small subset of it still has a large common neighborhood, giving a workhorse for embedding sparse/bipartite graphs into dense hosts (dense hypothesis $\Rightarrow$ richly-connected substructure), Nikiforov's proof uses Jensen's inequality applied to the convex function $f(x)=\binom{x}{s}$ on a degree sequence (exactly the same convexity trick that underlies the Kővári–Sós–Turán theorem, Kővári–Sós–Turán theorem: the double-counting bound ex(n,K_{s,t}) = O(n^{2-1/s})), not a random tuple/alteration argument. It is a close relative in spirit — "convexity forces an average-case-good structure to actually exist" — but a different concrete mechanism. - Two distinct 2008 papers, same author, same year: the $K_r$-clique-counting case (Bull. LMS 40(1), 23–25) and the arbitrary-subgraph-$H$-counting case ("Graphs with many copies of a given subgraph," Electron. J. Combin. 15, #R6) are companion papers; most later citations (e.g. Souza 2019, Fox–Luo–Wigderson 2019/2020) cite both together as "Nikiforov's theorem." - Sharpened quantitative form (2019/2020). Fox, Luo, and Wigderson (arXiv:1912.08328) give a new proof of the general-$H$ case using graph-regularity tools (the Duke–Lefmann–Rödl weak regularity lemma, in the Fox–Li multicolor-adapted form), improving the $\eta\to\lambda$ dependence from Nikiforov's original $\lambda=\eta^{k^2}$ to $\lambda=\eta^{1-1/|E(H)|+o(1)}$ — a substantial quantitative gain, same qualitative $t=\Theta(\log n)$ conclusion. - Application: blow-up Ramsey numbers. Souza (arXiv:1910.13912) introduced blow-up Ramsey numbers $B(G\xrightarrow{r}H;t)$ (minimum $n$ such that every $r$-coloring of the blow-up $G[n]$ contains a monochromatic *canonical* copy of $H[t]$) and used Nikiforov's theorem as the key step converting "some color class of $G[n]$ has many copies of $H$ by Ramsey/pigeonhole" into "some color class contains a genuine blow-up $H[t]$," giving an exponential-in-$t$ upper bound $B\le c(G,H,r)^t$; Fox–Luo–Wigderson use their sharpened Nikiforov-type theorem to prove the exponential *rate* $b=b(H,r)$ can be taken independent of $G$ (their Theorem 2), resolving a conjecture of Souza's up to the residual dependence of the multiplicative constant $a=a(G,H,r)$ on $G$. - Application: hypergraph discrepancy / Erdős #161. Conlon–Fox–Sudakov combine Dependent random choice — pick a small random test-tuple, take its common neighborhood; the resulting set is large and almost every small subset of it still has a large common neighborhood, giving a workhorse for embedding sparse/bipartite graphs into dense hosts with a counting-to-blow-up (hypergraph-Turán) step to prove $F^{(3)}(n,\alpha)\ll_\alpha\sqrt{\log n}$ for 3-uniform hypergraphs, resolving the $t=3$ case of Erdős's 1989 discrepancy-jump question (Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0?, documented in this wiki as solved/large-almost-monochromatic-subsets-hypergraphs); the general-$t\ge4$ case is open, and the forum-proposed "hypergraph Nikiforov" conjecture above is explicitly floated as the missing ingredient that would resolve it in full. - Adjacent but distinct spectral-radius line of work. "A Spectral Erdős–Stone–Bollobás Theorem" and arXiv:2203.03142 ("New proofs of stability theorems on spectral graph problems," giving short proofs of "Nikiforov's spectral stability theorem") extend Nikiforov-style stability/blow-up phenomena to the spectral-radius (rather than edge- or clique-count) setting — a related but separate strand, not verified in full detail here, flagged for a future page if needed (candidate slug concept/spectral-turan). - Companion exact-count result: the clique density theorem. The complementary *quantitative* question — what is the exact minimum number of $K_r$'s forced once edge density exceeds the Turán threshold by a given amount — is the Lovász–Simonovits clique density conjecture, resolved in full generality by Reiher (2016), after the triangle case (Razborov) and 4-clique case (Nikiforov himself); the counting-to-blowup theorem here gives *qualitative structural* information (a genuine blow-up exists) rather than the *exact minimum count*, so the two lines of results are complementary, not competing.

Technique

WHEN it applies. Reach for this theorem whenever a problem has already been reduced to (or can be reduced to) the statement "a graph/hypergraph $G$ contains $\Omega(n^{|V(H)|})$ copies of a fixed pattern $H$" — typically via ordinary supersaturation (Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983)) applied to a density hypothesis above the Turán threshold, or via a pigeonhole/Ramsey argument (some color class in a coloring must contain many copies of $H$) — and what is actually needed downstream is not just "many copies" but a genuinely blown-up, highly organized copy $H[t]$ with parts of provable size, because blow-ups are far easier to extract further structure from (e.g. a monochromatic sub-pattern, a further embedding, an averaging argument over the independent-set parts) than an arbitrary scattered family of copies would be.

WHY it works (the mechanism, clique case). The proof is by induction on $r$, bottoming out in a bipartite convexity lemma (Lemma 2 in the primary source): given a bipartite graph $F$ between sets $A$ ($|A|=m$) and $B$ ($|B|=n$) with $e(F)\ge cmn$, choosing $s=\lfloor c^r\ln n\rfloor$, the function $f(x)=\binom xs$ is convex, so by Jensen's inequality the *average* common-neighborhood size of an $s$-subset of $A$ (summed via double counting through $B$) is forced to be large — specifically $t>n^{1-c^{r-1}}$ — even though no single $s$-subset is chosen at random; convexity alone forces *some* $s$-subset of $A$ to have a large common neighborhood in $B$. The induction step for general $r$ first peels off a sub-family $L$ of the $r$-cliques whose $(r-1)$-clique "shadows" all have individually-large degree (a greedy removal procedure discards only a $c/2$-fraction of cliques), applies the inductive hypothesis to the shadow $(r-1)$-clique family to get an $(r-1)$-partite blow-up, then applies the bipartite convexity lemma once more between that blow-up's cliques and the remaining vertices to extend it to a full $r$-partite blow-up. This is the *same convexity engine* that proves the Kővári–Sós–Turán theorem (Kővári–Sós–Turán theorem: the double-counting bound ex(n,K_{s,t}) = O(n^{2-1/s})) — "many edges/cliques on average forces some specific sub-configuration to have an unusually large common neighborhood" — applied recursively rather than in one shot.

HOW it is used to prove things (recombination guidance for a solver). 1. Reduce your target claim to a copy-count. If you want to find a large blow-up of a fixed pattern $H$ inside a dense/structured host, first establish (usually via supersaturation, Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983), or directly from a density/Turán-type hypothesis) that the host contains $\ge cn^{|V(H)|}$ copies of $H$. This is normally the "easy" half; Nikiforov's theorem is what turns it into something with genuine internal structure. 2. Invoke Nikiforov (clique or general-$H$ form) to upgrade counting to structure. The output is a blow-up $H[t]$, $t=\Theta_{c,H}(\log n)$ in the graph case — deterministic in the sense that the *existence* is guaranteed, and the growth rate in $n$ is always logarithmic (optimal, per the tightness fact above), though the multiplicative constant depends on the copy-count density $c$ or $\eta$ and on $|V(H)|$ (and can be sharpened via the Fox–Luo–Wigderson regularity-based bound if a better constant is needed). 3. Exploit the blow-up's extra structure for the final step. Typical downstream moves: (a) apply pigeonhole/Ramsey arguments *inside* the large independent-set parts of the blow-up (this is exactly the Souza / Fox–Luo–Wigderson blow-up-Ramsey-number route); (b) use the blow-up as a "canonical" substructure whose parts can be further refined or intersected with other structures (the Conlon–Fox–Sudakov hypergraph-discrepancy route, composed with Dependent random choice — pick a small random test-tuple, take its common neighborhood; the resulting set is large and almost every small subset of it still has a large common neighborhood, giving a workhorse for embedding sparse/bipartite graphs into dense hosts); (c) derive a classical extremal theorem as a corollary by choosing $H=K_r$ and converting an edge-density hypothesis into a clique-count hypothesis via a clique-count recursion inequality (the Erdős–Stone–Bollobás corollary above). 4. For hypergraph-uniformity problems ($r\ge3$), check which of the two Nikiforov-adjacent results actually applies before reaching for the open conjecture: if your host is $r$-uniform and your hypothesis is literally "many edges" (not "many copies of some smaller pattern $H$"), Nikiforov's own proved edge-density theorem (arXiv:0711.1185) already gives a complete $r$-partite blow-up with parts of size $\Theta((\log n)^{1/(r-1)})$ — no conjecture needed. Only reach for the open "hypergraph Nikiforov" conjecture if your hypothesis is genuinely "many copies of a fixed sub-hypergraph pattern $H$" (with $|V(H)|$ possibly $>r$, i.e. a genuine counting-to-blowup statement one level up from raw edge density) — this is exactly the gap that blocks the general-$t$ case of Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0?, and any solver making progress on it (even the weaker $t>\delta(\log n)^{1/(|V(H)|-1)}$ exponent that the existing CFS machinery reaches, versus the conjectured $t>\delta(\log n)^{1/(r-1)}$) would be a genuine, reportable partial result, not merely a literature-reading exercise. 5. If the convexity/counting engine here feels too weak (e.g. because the copy-count hypothesis $cn^{|V(H)|}$ is not available, only ordinary edge-density), first pass through a supersaturation argument (Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983)) to manufacture the copy-count hypothesis, exactly as the Erdős–Stone–Bollobás corollary does via the Khadzhiivanov–Nikiforov recursive clique-count inequality.

Related

- Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983) — the weaker "density above Turán threshold $\Rightarrow \Omega(n^h)$ copies" statement that Nikiforov's theorem strictly strengthens (copies $\Rightarrow$ genuine blow-up); typically the input this theorem consumes. - Kővári–Sós–Turán theorem: the double-counting bound ex(n,K_{s,t}) = O(n^{2-1/s}) — the Kővári–Sós–Turán double-counting/convexity lemma; the same Jensen's-inequality mechanism (convex binomial-coefficient function on a degree sequence) is the bipartite base case that Nikiforov's induction reduces to. - Dependent random choice — pick a small random test-tuple, take its common neighborhood; the resulting set is large and almost every small subset of it still has a large common neighborhood, giving a workhorse for embedding sparse/bipartite graphs into dense hosts — a sibling "dense hypothesis $\Rightarrow$ richly-connected substructure" technique family (random-tuple common-neighborhoods rather than convexity/induction); Conlon–Fox–Sudakov compose the two directly (dependent random choice + a Nikiforov-style counting-to-blowup step) to resolve the $t=3$ case of Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0?. - Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? — OPEN for general $t\ge4$: Erdős's 1989 hypergraph discrepancy-jump problem; the $t=3$ case is resolved (Conlon–Fox–Sudakov) using a special case of the counting-to-blowup mechanism documented here, and the "hypergraph Nikiforov" conjecture in the Statement section above is the explicitly-proposed (forum-only, uncitable-as-a-paper) route to the general case. - solved/large-almost-monochromatic-subsets-hypergraphs — Conlon–Fox–Sudakov's resolution of the $t=3$ case of Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0?, the concrete worked example combining Dependent random choice — pick a small random test-tuple, take its common neighborhood; the resulting set is large and almost every small subset of it still has a large common neighborhood, giving a workhorse for embedding sparse/bipartite graphs into dense hosts with a hypergraph-Turán counting-to-blowup step. - concept/turan-number — the extremal edge-count function $\mathrm{ex}(n,H)$ whose density-exceeding regime is the standard entry point (via supersaturation) into Nikiforov's copy-count hypothesis.