Problem 766

Let $f(n;k,l)=\min \mathrm{ex}(n;G)$ , where $G$ ranges over all graphs with $k$ vertices and $l$ edges.

Give good estimates for $f(n;k,l)$ in the range $k<l\leq k^2/4$ . For fixed $k$ and large $n$ is $f(n;k,l)$ a strictly monotone function of $l$ ?

Source: erdosproblems.com/766

Graph theory
Turán numbers

Wiki page

Status

Open

No claim settles this problem.

Open. The site labels the problem OPEN. No source estimating $f(n;k,l)$ for general $(k,l)$ in the range $k<l\le k^2/4$ , beyond the pairs recorded below, or deciding strict monotonicity in $l$ in either reading, was found in the search whose scope the Current assessment records; this is a bounded negative finding, not a certificate of openness. What the origin records in the range: the Kővári--Sós--Turán bound, by which $[c_kn^{2-1/k}]$ edges force a $K(k,k)$ , so $f(n;2k,k^2)\le c_kn^{2-1/k}$ at the top of the range; the conjecture $f_1(n;2k,k^2)>\alpha_kn^{2-1/k}$ , which the paper reports as proved only for $k=2$ ; the admission that even $\lim f(n;6,9)/n^{3/2}=\infty$ was out of reach (p. 33); the p. 34 estimates (9)--(11) for $l$ linear in $k$ and $k$ large, quoted in the Current assessment; and, at the pair $(5,6)$ inside the range, Cavallius's upper bound for $f_1(n;5,6)=f_2(n;5,6)$ , the least edge count forcing a $K(2,3)$ , and the value $f_3(n;5,6)=[n^2/4]+1$ (p. 32). Later results at these pairs, recorded in the Current assessment: Brown's $K_{3,3}$ -free construction of 1966 gives $f(n;6,9)\gg n^{5/3}$ , which proves the 1964 conjecture for $k=3$ and settles $\lim f(n;6,9)/n^{3/2}=\infty$ , and Füredi's bounds of 1996 give $f(n;6,9)\sim\tfrac12n^{5/3}$ and $f(n;5,6)=\mathrm{ex}(n;K_{2,3})\sim n^{3/2}/\sqrt2$ in the site's normalization. General $(k,l)$ in the range and strict monotonicity remain unresolved. The site's commentary sentence on $l=\lfloor k^2/4\rfloor+1$ is the paper's p. 34 statement (below), just above the range; its Dirac half is Theorem 1 of [Di63] at $k=3$ ; inside the range that paper's only statements come from the cases $\alpha\le0$ of its Theorems 1 and 2, upper bounds of order $n^2$ on $f_1$ where the Kővári--Sós--Turán theorem gives $o(n^2)$ , and it says nothing about monotonicity in $l$ . The neighboring question of Chung and Erdős (1983), which graph with $e$ edges minimizes $\mathrm{ex}(n;H)$ with $e$ tied to the host, is settled by Bucić, Draganić and Sudakov (Combin. Probab. Comput. 30 (2021); refereed), and does not transfer to a fixed $k$ and $l$ .

Er64c: Erdős, P., Extremal problems in graph theory. Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Publ. House Czech. Acad. Sci., Prague (1964), 29--36; the definitions, pp. 29--30; the Dirac--Erdős statements, pp. 31, 32 and 34; the range $k<l\le k^2/4$ , p. 33; the references, p. 36. Library home: Erdős 1964; paged at Erdős 1964, Conjecture and question (p. 33), Erdős 1964, Statements (p. 31) and Erdős 1964, Statements (p. 34).
Di63: Dirac, G., Extensions of Turán's theorem on graphs. Acta Math. Acad. Sci. Hungar. 14 (1963), 417--422; [Er64c]'s reference [7], cited on p. 31 for the theorem that Turán's threshold $m(n,k)$ forces $K_{k+1}$ minus at most one edge, and its only Dirac reference. Theorem 1, p. 417; Theorem 3 with its footnote, p. 419. Library home: Dirac 1963; paged at Dirac 1963, Theorem 1 and Dirac 1963, Theorem 3.
Er55: Erdős, P., Some theorems on graphs (in Hebrew). Riveon Lematematika 9 (1955), 13--17; the paper's reference [6], cited on p. 31 for $f(n;4,5)=[n^2/4]+1$ .
Er63: Erdős, P., On the structure of linear graphs. Israel J. Math. 1 (1963), 156--160; the paper's reference [13], cited on p. 34 for the $K(k,k)$ -plus-an-edge theorem.
KST54: Kővári, T., Sós, V. T. and Turán, P., On a problem of K. Zarankiewicz. Coll. Math. 3 (1954), 50--57; the paper's reference [9].
Ca58: Cavallius, H., On a combinatorial problem. Colloq. Math. 6 (1958), 59--65; the paper's reference [8], cited on p. 32 for the upper bound on $f_1(n;5,6)=f_2(n;5,6)$ .
Br66: Brown, W. G., On graphs that do not contain a Thomsen graph. Canad. Math. Bull. 9 (1966), no. 3, 281--285; Section 2, the $K_{3,3}$ -free construction. Not cited by the site. Library home: Brown 1966; paged at Brown 1966, Section 2, inequality (2.8).
Fu96a: Füredi, Z., New asymptotics for bipartite Turán numbers. J. Combin. Theory Ser. A 75 (1996), no. 1, 141--144, doi:10.1006/jcta.1996.0067. Not cited by the site; its $K(2,t+1)$ asymptotic is recorded second-hand.
Fu96b: Füredi, Z., An upper bound on Zarankiewicz' problem. Combin. Probab. Comput. 5 (1996), no. 1, 29--33, doi:10.1017/S0963548300001814. Not cited by the site.
BDS21: Bucić, M., Draganić, N. and Sudakov, B., Universal and unavoidable graphs. Combin. Probab. Comput. 30 (2021), no. 6, 942--955, doi:10.1017/S0963548321000110; arXiv:1912.04889v2 (21 December 2020). Theorem 1.1, p. 2. Not cited by the site. Library home: Bucic, Draganic and Sudakov 2019; paged at Bucic, Draganic and Sudakov 2019, Theorem 1.1.
ChEr83: Chung, F. R. K. and Erdős, P., On unavoidable graphs (1983), reference [10] of [BDS21]; it is cited here only as the question [BDS21] answers.

Problem 766

Status

Proof claims

Discussion