Problem 576

Let $Q_k$ be the $k$ -dimensional hypercube graph (so that $Q_k$ has $2^k$ vertices and $k2^{k-1}$ edges). Determine the behaviour of

\mathrm{ex}(n;Q_k).

Source: erdosproblems.com/576

Graph theory
Turán numbers

Wiki page

Status

Open

No claim settles this problem.

Open. For the cube, $(\tfrac12+o(1))n^{3/2}\le\mathrm{ex}(n;Q_3)\le O(n^{8/5})$ , the upper bound being display (5) of Erdős and Simonovits (1970) and unimproved since, the lower bound the 4-cycle bound; Erdős's original guess that $n^{5/3}$ is the order is refuted by the upper bound. For $k\ge3$ in general, $\mathrm{ex}(n;Q_k)=O_k(n^{2-\frac1{k-1}+\frac1{(k-1)2^{k-1}}})$ (Janzer and Sudakov, Theorem 1.4; Forum of Mathematics, Sigma 2024, refereed), the first power improvement over the dependent-random-choice bound $O(n^{2-1/k})$ and over the $o(n^{2-1/k})$ they attribute to Sudakov and Tomon, against the lower bound $\Omega(n^{2-\frac{2^k-2}{k2^{k-1}-1}})\ge\Omega(n^{2-2/k})$ from the deletion method (their p. 17); for $k=3$ their exponent $13/8$ exceeds $8/5$ , so the 1970 bound stands for the cube. No source cited here determines the exponent for any $k\ge3$ , and none was found in the search whose scope the Current assessment records. This is a bounded negative finding, not a certificate of openness.

ErSi70: Erdős, P. and Simonovits, M., Some extremal problems in graph theory. Combinatorial theory and its applications, I (Proc. Colloq., Balatonfüred, 1969), North-Holland (1970), 377--390; displays (4) and (5), p. 378; (10), p. 379. Library home: Erdős and Simonovits 1970; paged at Erdős and Simonovits 1970, Display (5) (p. 378) and Erdős and Simonovits 1970, Display (4) (p. 378).
JaSu22: Janzer, O. and Sudakov, B., On the Turán number of the hypercube. arXiv:2211.02015v3 (22 January 2024); Forum of Mathematics, Sigma 12 (2024), doi:10.1017/fms.2024.27 (published online 15 March 2024; the journal text was not consulted). Theorems 1.2, 1.4 and 1.5 and the lower bound are cited from arXiv v3, p. 2 and p. 17. Library home: Janzer and Sudakov 2022; paged at Janzer and Sudakov 2022, Theorem 1.4 and Janzer and Sudakov 2022, Theorem 1.2 (attributed to Sudakov and Tomon).
SuTo22: Sudakov, Benny and Tomon, István, The extremal number of tight cycles. Int. Math. Res. Not. IMRN 2022, no. 13, 9663--9684; doi:10.1093/imrn/rnaa396 (published online 8 February 2021). Its arXiv:2009.00528v1 (1 September 2020) contains no statement about the Turán number $\mathrm{ex}(n;Q_k)$ of the hypercube or about $K_{d,d}$ -free bipartite graphs (the hypercube appears only as a host graph in its concluding remarks, p. 15, after Conjecture 7.1, with reference [3]); the bound the site attributes to this paper is cited here only as Theorem 1.2 of [JaSu22]. Library home: Sudakov and Tomon 2022.
Er74c: Erdős, Paul, Extremal problems on graphs and hypergraphs. Hypergraph Seminar, Lecture Notes in Math. 411 (1974), 75--84; display (7), p. 78. Library home: Erdős 1974; paged at Erdős 1974, Display (7) (p. 78).
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25--42; Part III, item 2, displays (1)--(3). Library home: Erdős 1981. The version cited is a retyped one without the journal's pagination; the passage is on its pp. 6--7.
Er64c: Erdős, P., Extremal problems in graph theory. Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Prague (1964), 29--36; p. 35. Library home: Erdős 1964; paged at Erdős 1964, Problem (p. 35).
Er75: Erdős, P., Some recent progress on extremal problems in graph theory. Congr. Numer. XIV (1975), 3--14; Chapter 2, display (1), printed p. 8. Library home: Erdős 1975; paged at Erdős 1975, Problem (Chapter 2, printed p. 8 = PDF p. 6).
Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; the site cites p. 334. Chapter I, display (3), $T(n;G)<cn^{8/5}$ for the cube, with the conjecture that the exponent is sharp, printed p. 334 (the passage is quoted under Erdős's statements). Library home: Erdős 1993.
Ch97: Chung, F. R. K., Open problems of Paul Erdős in graph theory. J. Graph Theory 25 (1997), 3--36; Problem (36), p. 9 of the author's preprint version. Not cited by the site. Library home: Chung 1997; paged at Chung 1997, Problem (36).

Problem 576

Status

Proof claims

Discussion