Erdős Problem #113 — Bipartite graphs with an Turán bound
For a finite graph , let be the maximum number of edges in an -vertex graph containing no subgraph isomorphic to . A graph is -degenerate if every nonempty subgraph has a vertex of degree at most . The question is whether, for every finite bipartite graph , the following equivalence holds, where the implicit constant may depend on :
Background
The question belongs to the difficult theory of extremal numbers for bipartite forbidden graphs: unlike the non-bipartite case, general asymptotic estimates do not determine their order of growth. A useful benchmark is the theorem of Füredi and, independently by a different method, Alon, Krivelevich and Sudakov: if one side of a bipartition of has maximum degree at most , then . Erdős proposed extending this upper bound to all -degenerate bipartite graphs. Alon, Krivelevich and Sudakov proved the weaker general estimate for such graphs. The case is the upper-bound direction of the question here. Janzer (2023)
Erdős and Simonovits conjectured the stated equivalence, and Erdős repeatedly returned to the problem, offering a prize for its resolution. The conjecture was part of the broader question of whether high minimum degree in a bipartite forbidden graph forces an extremal number larger than the bound suggested by degeneracy. Janzer (2023) Erdős and Simonovits (1984)
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.