Erdős Problem #147 — Minimum degree and bipartite Turán exponents
Let be a fixed finite bipartite graph, and write for its minimum degree. For a positive integer , let be the maximum number of edges in an -vertex graph containing no subgraph isomorphic to . The question asks whether, for every such with an integer at least , there is a constant such that, as ,
Equivalently, must there exist and such that
for every integer ? Erdős Problem #147 Janzer (2023)
Background
Erdős and Simonovits proposed this improvement to the general lower bound for graphs of prescribed minimum degree; the present question is its bipartite case. For nonbipartite forbidden graphs, the Erdős–Stone–Simonovits theorem gives the leading asymptotic for the Turán number. The bipartite setting is much less settled: even the order of magnitude is unknown for familiar examples such as , , and the cube . Erdős Problem #147 Janzer (2023) Erdős and Simonovits (1984)
A useful general benchmark comes from the probabilistic deletion method: for a fixed graph with minimum degree at least , it yields some , depending on , such that . This exponent is weaker than the one asked for here, so the method alone does not establish the proposed improvement. Janzer (2023) Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles
References
O. Janzer, Disproof of a conjecture of Erdős and Simonovits on the Turán number of graphs with minimum degree 3, Combinatorica 43 (2023), 105–130.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.