The leading constant in the Bollobás–Erdős blow-up function $c_r(ε)$ as $ε$ tends to 0

For an integer $r ≥ 2$ and $ε > 0$, let $c_r(ε)$ be the largest constant $k$ such that every sufficiently large $n$-vertex graph with more than $((r-2)/(2(r-1)) + ε)n^2$ edges contains $K_r(t)$, the complete $r$-partite graph with $t$ vertices in each part, for some $t ≥ k log n$ (this is the notation of Bollobás and Erdős, 1973). The order of $c_r(ε)$ as $ε → 0$ is known: $c_r(ε) = Θ(1/log(1/ε))$ with absolute implicit constants, proved for $r = 2$ by Bollobás and Erdős (1973), for every fixed $r$ up to $r$-dependent constants by Bollobás, Erdős and Simonovits (1976), and with an absolute constant by Chvátal and Szemerédi (1981); Shapira and Yuster (2026) recently determined the tight order at every edge density. The leading constant, however, is unknown for every $r$: for $r = 2$ it is only known to lie between $1$ and $2$ (in units of $1/log(1/(2ε))$), with the random graph conjectured extremal. The problem asks to determine whether the limit $c_r^* = lim_{ε→0} c_r(ε)·log(1/ε)$ exists and to compute its value, at least for $r = 2$.

Background

A complete $r$-partite graph $K_r(t)$, also called a balanced blow-up of the complete graph $K_r$, consists of $r$ disjoint independent sets of $t$ vertices each (the parts), where two vertices are joined by an edge exactly when they lie in different parts. Turán's theorem, the founding result of extremal graph theory, states that an $n$-vertex graph with more than $(1 - 1/(r-1))n^2/2$ edges must contain $K_r$, and that this edge count is best possible; the extremal example is the complete $(r-1)$-partite Turán graph. The Erdős–Stone theorem (1946) strengthens this qualitatively: for every fixed $r ≥ 2$ and $ε > 0$, every sufficiently large $n$-vertex graph with more than $((r-2)/(2(r-1)) + ε)n^2$ edges contains $K_r(t)$ for some $t$ that tends to infinity with $n$. The quantitative question is how large a $t$ is forced by a given excess density $ε$.

Bollobás and Erdős (1973) introduced the function $g(n, r, ε)$, defined as the largest $t$ such that every $n$-vertex graph with more than $((r-2)/(2(r-1)) + ε)n^2$ edges contains $K_r(t)$, and showed that $g(n, r, ε) = Θ(log n)$ for fixed $r$ and $ε$, refuting the then-expected order $(log n)^{1/(r-1)}$. (The 1973 paper prints 'min' in its defining formula, but since $K_r(t)$ contains $K_r(t-1)$ the least such $t$ would be trivially $1$; the reading its theorems require — restated explicitly as 'the maximal value of $t$' in the 1976 sequel of Bollobás, Erdős and Simonovits — is the largest guaranteed $t$, and the two readings differ by at most an additive $1$.) They then defined $c_r(ε)$ as the supremum of the constants $k$ such that $g(n, r, ε) ≥ k log n$ for all sufficiently large $n$, and posed the problem of the asymptotic behavior of $c_r(ε)$ as $ε → 0$. Two classical tools delimit the answer. First, the Kővári–Sós–Turán theorem (1954) on the Zarankiewicz problem — the problem of bounding the maximum number of edges in a bipartite graph hosting no complete bipartite subgraph $K_{s,t}$ — bounds the number of edges in a $K_{t,t}$-free graph; it yields $c_2(ε) ≥ 1/log(1/(2ε))$. Second, the probabilistic method (random graphs with $ε n^2$ edges) shows $c_2(ε) ≤ 2/log(1/(2ε))$; for $r ≥ 3$, adding random edges inside one class of a Turán graph gives $c_r(ε) ≤ 2/log(1/(2(r-1)^2 ε))$ (Bollobás and Erdős 1973, Remark 2). These bounds leave a multiplicative constant gap, and closing it is the subject of this problem.

The order question was settled in two steps. Bollobás, Erdős and Simonovits (1976) proved $g(n, r, ε) ≥ a·log n / ((r-1)·log(1/(2ε)))$ for an absolute constant $a > 0$, establishing the order $Θ_r(1/log(1/ε))$ conjectured in the 1973 paper, and conjectured that the factor $r-1$ can be removed. Chvátal and Szemerédi (1981) proved this conjecture: $b_n(r, δ) ≥ log n / (500·log(1/δ))$ for every $r ≥ 2$ and $0 < δ ≤ 1/r$, where $b_n(r, δ)$ denotes the guaranteed blow-up size at edge density $1 - 1/r + δ$ (equivalent to the 1973 notation via $r → r-1$, $δ = 2ε$). Combined with the classical constructions this pins $c_r(ε) = Θ(1/log(1/ε))$ with absolute implicit constants for all $r ≥ 2$. Shapira and Yuster (2026) completed the order picture by determining the tight order at every edge density, $b_n(r, δ) = Θ(log n / ((1/r - δ)·r·log(1/δ)))$, the previously open regime being near-complete graphs.

What remains open is the leading constant, and it is open even in the simplest case $r = 2$, where the question becomes the leading constant of the dense Zarankiewicz problem: how large a balanced complete bipartite subgraph $K_{t,t}$ must appear in a graph with $ε n^2$ edges. The bounds $1 ≤ c_2(ε)·log(1/(2ε)) ≤ 2$ have not been improved on either side; the conjectural truth is the random-graph value $2$. The same constant question drives an active neighboring program on blow-ups forced by subgraph density: Nikiforov (2008) proved that $γ n^h$ copies of an $h$-vertex graph $H$ force an $H$-blow-up of order $c_H(γ)·log n$; Girão, Hunter and Wigderson (2025) determined $c_H(γ) = Θ_H(1/log(1/γ))$ for triangle-free $H$; and Fox, Wigderson and Zhou (2026) proved $c_H(γ) ≥ γ^{1/2+o(1)}$ for all $H$, while stating that whether the true behavior is logarithmic or polynomial (that is, whether random graphs are extremal) is the most interesting open question of that program, and that the hypergraph extension remains an outstanding open problem.

Problem Statement

Fix an integer $r ≥ 2$. For $ε > 0$ and positive integers $n$, let $g(n, r, ε)$ denote the largest integer $t$ such that every $n$-vertex graph with more than $((r-2)/(2(r-1)) + ε)n^2$ edges contains $K_r(t)$, the complete $r$-partite graph with $t$ vertices in each part ($K_2(t)$ is the balanced complete bipartite graph $K_{t,t}$). Since $K_r(t)$ contains $K_r(t-1)$, this is the meaningful reading of the definition in Bollobás and Erdős (1973), whose printed formula reads 'min' but whose theorems all concern this largest guaranteed $t$ (the two readings differ by at most an additive $1$); the sequel by Bollobás, Erdős and Simonovits (1976) states the definition explicitly as the maximal value of $t$. Let $c_r(ε)$ be the supremum of the constants $k$ such that $g(n, r, ε) ≥ k log n$ for all sufficiently large $n$, where the threshold $n_0$ may depend on $k$, $r$ and $ε$. This is the notation of Bollobás and Erdős (1973); it is known that $c_r(ε) = Θ(1/log(1/ε))$ as $ε → 0$, with absolute implicit constants.

The problem is to determine the leading constant:

(1) Prove or disprove that the limit $c_r^* = lim_{ε→0} c_r(ε)·log(1/ε)$ exists, and determine its exact value; if the limit does not exist, determine the exact values of the liminf and the limsup.

(2) Central case $r = 2$. The known bounds are $1/log(1/(2ε)) ≤ c_2(ε) ≤ 2/log(1/(2ε))$, equivalently $c_2^*$ (if it exists) lies in $[1, 2]$; note that $log(1/(2ε))/log(1/ε) → 1$ as $ε → 0$, so the two logarithmic units are asymptotically interchangeable. Prove that $c_2^* = 2$: that is, prove that for every $η > 0$ there exists $ε_0 > 0$ such that for every $0 < ε < ε_0$ there exists $n_0 = n_0(ε, η)$ such that for every $n > n_0$, every $n$-vertex graph with more than $ε n^2$ edges contains $K_{t,t}$ for some $t ≥ (2 - η)·log n / log(1/(2ε))$; this would confirm that random graphs are extremal for the dense Zarankiewicz problem. Alternatively, refute random-graph extremality: exhibit $η > 0$ and $ε_0 > 0$ such that for every $0 < ε < ε_0$ and arbitrarily large $n$ there is an $n$-vertex graph with more than $ε n^2$ edges containing no $K_{t,t}$ with $t ≥ (2 - η)·log n / log(1/(2ε))$.

Settling item (1) for every fixed $r ≥ 2$ resolves the full general question.

References

1. B. Bollobás and P. Erdős, On the structure of edge graphs, Bulletin of the London Mathematical Society 5 (1973), no. 3, 317–321. DOI: 10.1112/blms/5.3.317. URL: https://doi.org/10.1112/blms/5.3.317. Open-access copy: https://www.renyi.hu/~p_erdos/1973-18.pdf.
2. B. Bollobás, P. Erdős, and M. Simonovits, On the structure of edge graphs II, Journal of the London Mathematical Society (2) 12 (1976), no. 2, 219–224. DOI: 10.1112/jlms/s2-12.2.219. URL: https://doi.org/10.1112/jlms/s2-12.2.219. Open-access copy: https://www.renyi.hu/~p_erdos/1975-28.pdf.
3. V. Chvátal and E. Szemerédi, On the Erdős–Stone theorem, Journal of the London Mathematical Society (2) 23 (1981), no. 2, 207–214. DOI: 10.1112/jlms/s2-23.2.207. URL: https://doi.org/10.1112/jlms/s2-23.2.207.
4. V. Chvátal and E. Szemerédi, Notes on the Erdős–Stone theorem, Annals of Discrete Mathematics 17 (1983), 183–190. DOI: 10.1016/S0304-0208(08)73386-3. URL: https://doi.org/10.1016/S0304-0208(08)73386-3.
5. B. Bollobás and Y. Kohayakawa, An extension of the Erdős–Stone theorem, Combinatorica 14 (1994), no. 3, 279–286. DOI: 10.1007/BF01212976. URL: https://doi.org/10.1007/BF01212976.
6. Y. Ishigami, Proof of a conjecture of Bollobás and Kohayakawa on the Erdős–Stone theorem, Journal of Combinatorial Theory, Series B 85 (2002), no. 2, 222–254. DOI: 10.1006/jctb.2001.2097. URL: https://doi.org/10.1006/jctb.2001.2097.
7. V. Nikiforov, Graphs with many r-cliques have large complete r-partite subgraphs, Bulletin of the London Mathematical Society 40 (2008), no. 1, 23–25. DOI: 10.1112/blms/bdm093. URL: https://doi.org/10.1112/blms/bdm093. arXiv: https://arxiv.org/abs/math/0703554.
8. A. Girão, Z. Hunter, and Y. Wigderson, Blowups of triangle-free graphs, Advances in Combinatorics (2025), Paper No. 10, 23 pp. DOI: 10.19086/aic.2025.10. URL: https://doi.org/10.19086/aic.2025.10. arXiv: https://arxiv.org/abs/2408.12913.
9. J. Fox, Y. Wigderson, and Y. Zhou, Finding blowups one vertex at a time, preprint (2026). arXiv:2605.23301. URL: https://arxiv.org/abs/2605.23301.
10. A. Shapira and R. Yuster, A Tight Erdős–Stone Bound for All Graph Densities, preprint (2026). arXiv:2609.01498. URL: https://arxiv.org/abs/2609.01498.
11. P. Erdős and A. H. Stone, On the structure of linear graphs, Bulletin of the American Mathematical Society 52 (1946), no. 12, 1087–1091. DOI: 10.1090/S0002-9904-1946-08715-7. URL: https://doi.org/10.1090/S0002-9904-1946-08715-7.
12. T. Kővári, V. T. Sós, and P. Turán, On a problem of K. Zarankiewicz, Colloquium Mathematicum 3 (1954), no. 1, 50–57. DOI: 10.4064/cm-3-1-50-57. URL: https://doi.org/10.4064/cm-3-1-50-57.