Problem 1158

Let $K_{t}(r)$ be the complete $t$ -partite $t$ -uniform hypergraph with $r$ vertices in each class.

Is it true that

\mathrm{ex}_t(n,K_t(r)) \geq n^{t-r^{1-t}-o(1)}

for all $t,r$ ?

Second statement

Let $K_{t}(r)$ be the complete $t$ -partite $t$ -uniform hypergraph with $r$ vertices in each class.

Is it true that

\mathrm{ex}_t(n,K_t(r)) \geq n^{t-r^{1-t}-o(1)}

for all $t,r$ with $r>1$ ?

Source: erdosproblems.com/1158

Hypergraphs
Turán numbers

Wiki page

Status

Open

No claim settles this problem.

Open. The site records the exponent as known only for $t=2$ and $2\le r\le3$ , which agrees with every source on this page: for graphs ( $t=2$ ) the Kővári--Sós--Turán exponent $2-1/r$ is attained for $r=2$ and $r=3$ , the subject of Problem 714. These settle the instances $(t,r)=(2,2)$ and $(2,3)$ of the statement in the affirmative, through the refereed results recorded as accepted partial claims of Problem 714: Brown 1966 for $r=3$ and $r=2$ , and Erdős, Rényi and Sós 1966 and Kővári, Sós and Turán 1954 for $r=2$ . They have no claim page here because the site routes the case $t=2$ to Problem 714 and credits no source for it on this page; as partial results they leave this problem open. For $t\ge3$ no pair $(t,r)$ is known to attain the exponent $t-r^{1-t}$ . The best general lower bounds recorded here are for the box problem $r=2$ : Corollary 1 of [CPZ21] (result page), $\mathrm{ex}_t(n,K_t(2))=\Omega(n^{t-1/\lceil(2^t-1)/t\rceil})$ for every $t\ge2$ , from random multilinear maps, against the asked exponent $t-1/2^{t-1}$ (the two agree only for $t=2$ ; for $t=3$ the bound is $n^{8/3}$ against the asked $n^{11/4}$ ), and Theorem 3.2 of [Go23] (result page), an explicit construction with $\mathrm{ex}_t(n,K_t(2))=\Omega(n^{t-1/t})$ , matching the Conlon--Pohoata--Zakharov exponent for $t\le4$ . For unbalanced parts the exponent $t-1/(s_1\cdots s_{t-1})$ is attained once the last part is large (leads below), which does not cover the balanced $K_t(r)$ . No construction reaching $n^{t-r^{1-t}-o(1)}$ for any $t\ge3$ , no disproof, and no proof claim was found in the search whose scope the Current assessment records. This is a bounded negative finding, not a certificate of openness.

Notes

The site's wording quantifies over every $t$ and $r$ and fails at $r=1$ : the forbidden graph $K_t(1)$ is a single edge, so $\mathrm{ex}_t(n,K_t(1))=0$ , while the right side $n^{t-1-o(1)}$ is positive for every $t$ . For each $t$ the failure lies at the smallest value of $r$ , and the site's wording gives $r$ no range, so it is a boundary failure. The change inserts the words "with $r>1$ " after "for all $t,r$ "; nothing else changes. The evidence is the poser's own statement of the bound the question asks about: Theorem 1 of [Er64f] (p. 185), "Let $n>n_0(r,l)$ , $l>1$ ", with $r$ the uniformity and $l$ the class size, so its $l>1$ is the site's $r>1$ , and the question asks whether the exponent of that theorem is sharp. The booklet item [Va99] 3.65 that the site cites asks about "the 1962 bound $t-\frac1{r^{t-1}}$ of Erdős" without a range, so the defect is the site's and the booklet's, not Erdős's. The site's commentary, which calls the exponent known for $t=2$ and $2\le r\le3$ , and the formal-conjectures statement, which asks the question for $t,r\ge2$ and counts with the site, agree with the change. The change leaves $t$ unrestricted; for $t=1$ and $r>1$ the inequality holds trivially, since $\mathrm{ex}_1(n,K_1(r))=r-1\ge1$ . The form rests on these sources alone. No result concerns the site's wording at $r=1$ , and the corrected Statement is open.

Er64f: Erdős, P., On extremal problems of graphs and generalized graphs. Israel J. Math. 2 (1964), no. 3, 183--190; Theorem 1, p. 185; the definitions, pp. 183--184; the closing remarks, p. 189. Library home: Erdős 1964 (the Rényi archive scan); paged at Erdős 1964, Theorem 1.
Va99: Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erdős and his mathematics", Budapest, July 1999; item 3.65 in Section 3.5, Set-systems. Library home: Various 1999 (Kovač's public image-only scan of paired pages; the item is on the left leaf of its PDF p. 7).
CPZ21: Conlon, D., Pohoata, C. and Zakharov, D., Random multilinear maps and the Erdős box problem. Discrete Analysis 2021:17, 8 pp., doi:10.19086/da.28336 (published 28 September 2021; the journal typesetting is posted to arXiv as arXiv:2011.09024v2); Theorem 2 and Corollary 1, p. 3. Not cited by the site. Library home: Conlon and Zakharov 2021.
Go23: Gordeev, A., Combinatorial Nullstellensatz and Turán numbers of complete $r$ -partite $r$ -uniform hypergraphs. arXiv:2307.04447v1 (10 July 2023); Discrete Math. 347 (2024), no. 7, 114037, doi:10.1016/j.disc.2024.114037, with a corrigendum, Discrete Math. 348 (2025), no. 4, 114417, doi:10.1016/j.disc.2025.114417 (Crossref records accessed); Theorem 3.2, p. 2. Not cited by the site. Library home: Gordeev 2023.
KKM02: Katz, N. H., Krop, E. and Maggioni, M., Remarks on the box problem. Math. Res. Lett. 9 (2002), 515--519. Quoted from [CPZ21] (p. 2) and [Go23] (p. 3) for $\mathrm{ex}_3(n,K_3(2))=\Omega(n^{8/3})$ .
PoZa21: Pohoata, C. and Zakharov, D., Norm hypergraphs. arXiv:2101.00715 (3 January 2021; abstract accessed); [Mu26] Mubayi, D., Hypergraphs without complete partite subgraphs. arXiv:2507.06390 (v2 14 July 2025); Combin. Probab. Comput. 35 (2026), 290--293, doi:10.1017/S0963548325100321 (arXiv record accessed); [CLY25] Chen, Q., Liu, H. and Ye, K., Extremal constructions for apex partite hypergraphs. arXiv:2510.07997 (9 October 2025); [CXY26] Chen, Q., Xu, Z. and Ye, K., Turán problems for multilinear maps. arXiv:2603.00715 (v2 23 July 2026); [DM26] Dash, S. and Majumder, K., An analytic counting framework for the generalised Erdős box problem. arXiv:2607.16694 (v2 7 August 2026). Leads by abstract, recorded below.

Problem 1158

Second statement

Status

Notes

Proof claims

Discussion