Problem 714

Is it true that

\mathrm{ex}(n; K_{r,r}) \gg n^{2-1/r}?

Source: erdosproblems.com/714

Graph theory
Turán numbers

Wiki page

Status

Open

No claim settles this problem.

Open. The site labels the problem OPEN. The answer is yes for $r=2$ (Kővári, Sós and Turán 1954; Erdős, Rényi and Sós 1966; Brown 1966) and for $r=3$ (Brown 1966), recorded as accepted partial claims on the pages Kővári, Sós and Turán, Erdős, Rényi and Sós and Brown. For every $r\ge4$ no proof or disproof was found in the search whose scope the Current assessment records: for the smallest open case $K_{4,4}$ the best lower bound located is $(\tfrac12-o(1))n^{5/3}$ , which Brown's $K_{3,3}$ -free graphs give by monotonicity; for $K_{5,5}$ it is Ball and Pepe's $n^{7/4}$ (2012), which monotonicity passes to every $K_{r,r}$ with $r\ge5$ ; the best lower bound valid uniformly in $r$ is the probabilistic $n^{2-2/(r+1)}$ ; and the exponent $2-1/r$ is known to be attained only for unbalanced $K_{r,s}$ , with $s\ge(r-1)!+1$ (Kollár, Rónyai and Szabó 1996; Alon, Rónyai and Szabó 1999) and with $s\ge C^r$ for an absolute constant $C$ (Bukh 2024). This is a bounded negative finding, not a certificate of openness; no full claim is recorded, and the frontmatter standing derives from the partial claims.

KST54: Kövari, T. and Sós, V. T. and Turán, P., On a problem of K. Zarankiewicz. Colloq. Math. 3 (1954), 50--57. Inequality (1.5), p. 50; (3.1), p. 52; (6.1), p. 56. Library home: Kövari, Sós and Turán 1954; claim page Kővári, Sós and Turán.
Br66: Brown, W. G., On graphs that do not contain a Thomsen graph. Canad. Math. Bull. 9 (1966), no. 3, 281--285; doi:10.4153/CMB-1966-036-2. Inequality (2.8), p. 284, and Section 3, pp. 284--285. Library home: Brown 1966; claim page Brown.
ERS66: Erdős, P. and Rényi, A. and Sós, V. T., On a problem of graph theory. Studia Sci. Math. Hungar. 1 (1966), 215--235. Theorem 1, p. 217; Corollary 2, p. 219. Library home: Erdős and Sós 1966; claim page Erdős, Rényi and Sós.
ARS99: Alon, N., Rónyai, L. and Szabó, T., Norm-graphs: variations and applications. J. Combin. Theory Ser. B 76 (1999), 280--290; doi:10.1006/jctb.1999.1906. Corollary 6 (p. 7 of the author manuscript on Alon's publication page, the edition the card names). Library home: Alon 1999. Not cited by the site.
KRS96: Kollár, J., Rónyai, L. and Szabó, T., Norm-graphs and bipartite Turán numbers. Combinatorica 16 (1996), 399--406. Not held; cited through [ARS99]. Not cited by the site.
BaPe12: Ball, S. and Pepe, V., Asymptotic improvements to the lower bound of certain bipartite Turán numbers. Combin. Probab. Comput. 21 (2012), no. 3, 323--329; doi:10.1017/S0963548311000423 (published online 3 October 2011). Not held; its abstract is known as deposited in the Crossref record: graphs on $n$ vertices with no $K_{5,5}$ and about a constant times $n^{7/4}$ edges, so $\mathrm{ex}(n,K_{5,5})\gg n^{7/4}$ . Not cited by the site.
Bu24: Bukh, B., Extremal graphs without exponentially small bicliques. Duke Math. J. 173 (2024), no. 11; doi:10.1215/00127094-2023-0043 (issued 15 August 2024). Preprint arXiv:2107.04167 (9 July 2021; v3 of 6 August 2023, titled "Extremal graphs without exponentially-small bicliques"). Not held; its abstract is known from the arXiv record: $K_{s,t}$ -free graphs with $\Omega(n^{2-1/s})$ edges for $t=C^s$ . Not cited by the site.
Er64c: Erdős, P., Extremal problems in graph theory. Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963) (1964), 29--36. Library home: Erdős 1964; its p. 33 conjecture $f_1(n;2k,k^2)>\alpha_kn^{2-1/k}$ , which implies the problem's bound and which the paper reports proved only for $k=2$ , is paged at Erdős 1964, Conjecture and question (p. 33).
Er67b: A 1967 source key of the site; its bibliographic entry is not in the site's reference export and is unresolved.
Er69: Erdős, Paul, Some applications of graph theory to number theory. The Many Facets of Graph Theory (Proc. Conf., Kalamazoo, 1968) (1969), 77--82. Library home: Erdős 1969; its passage on this problem is not compiled.
Er71: Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97--109; the site cites p. 103. Library home: Erdős 1971; its item 15 (printed p. 103), paged at item 15, records the Kővári--Sós--Turán bound as display (1) and the wished-for lower bound $f(n;K_2(r,r))>c_r'n^{2-1/r}$ as display (2), "known for $r=2$ and $r=3$ but no good lower bound is known for $r\geqslant4$ ", a 1971 confirmation of the status.
Er74c: Erdős, Paul, Extremal problems on graphs and hypergraphs. Hypergraph Seminar, Lecture Notes in Math. 411 (1974), 75--84; the site cites p. 77. Library home: Erdős 1974; its passage on this problem is not compiled; the card's digest records its display (2), the Kővári--Sós--Turán bound, as conjectured sharp and proved only for $t=2,3$ .
Er75: Erdős, P., Some recent progress on extremal problems in graph theory. Congr. Numer. XIV (1975), 3--14. Library home: Erdős 1975; its Chapter 2 records the Kővári--Sós--Turán bound per the card; its passage is not compiled.
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, display (3). Library home: Erdős 1981; the Rényi archive's copy (https://users.renyi.hu/~p_erdos/1981-16.pdf) is a retyped text without the journal's pagination, with the display on its 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 (4), printed p. 334: Erdős writes that "Kövári, V.T. Sós, Turán [6] and I proved" the bound (4), $T(n;K(r,r))<cn^{2-1/r}$ , for the complete bipartite graph $K(r,r)$ with $r$ vertices on each side, and continues: "The exponent $2-\tfrac1r$ is almost certainly best possible but this is known only for $r=2$ and $r=3$ ", citing Erdős, Rényi and Sós and, independently, Brown, and "As far as I know $T(n;K(4,4))/n^{5/3}\to\infty$ is not even known"; the "and I" attaches Erdős to the Kővári--Sós--Turán bound, as printed. Library home: Erdős 1993.

Problem 714

Status

Proof claims

Discussion