Problem 1021

Is it true that, for every $k\geq 3$ , there is a constant $c_k>0$ such that

\mathrm{ex}(n,G_k) \ll n^{3/2-c_k},

where $G_k$ is the bipartite graph between $\{y_1,\ldots,y_k\}$ and $\{z_1,\ldots,z_{\binom{k}{2}}\}$ , with each $z_j$ joined to a unique pair of $y_i$ ?

Source: erdosproblems.com/1021

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The site credits Conlon and Lee [CoLe21], with $c_k=6^{-k}$ , and the improvement to $c_k=1/(4k-6)$ by Janzer [Ja19]; both are refereed publications, Conlon--Lee cited from the arXiv v2 manuscript and Janzer from the published six-page paper, and each has a claim page, Conlon and Lee and Janzer, accepted on the refereed venues and the site's credit. The site also credits the case $k=3$ to Erdős [Er64c] and to Bondy and Simonovits [BoSi74]; that case has its accepted partial claim page, Bondy and Simonovits. The proof-claim tab is empty and nothing is independently reviewed here.

BoSi74: Bondy, J. A. and Simonovits, M., Cycles of even length in graphs. J. Combinatorial Theory Ser. B 16 (1974), no. 2, 97-105, doi:10.1016/0095-8956(74)90052-5.
CoLe21: Conlon, David and Lee, Joonkyung, On the extremal number of subdivisions. Int. Math. Res. Not. IMRN (2021), 9122-9145.
Er64c: Erdős, P., Extremal problems in graph theory. Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963) (1964), 29-36.
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; p. 103 is one of the site's two source passages for the problem.
Er74c: Erdős, Paul, Extremal problems on graphs and hypergraphs. Hypergraph Seminar, Lecture Notes in Math. 411, Springer (1974), 75--84; p. 79 is one of the site's two source passages for the problem. Library home: Erdős 1974.
Ja19: Janzer, Oliver, Improved bounds for the extremal number of subdivisions. Electron. J. Combin. (2019), Paper No. 3.3, 6.

Problem 1021

Status

Proof claims

Discussion