← All problems

Erdős Problem #113 — Bipartite graphs with an n3/2n^{3/2} Turán bound

42 years old · traced to

For a finite graph HH, let ex⁡(n,H)\operatorname{ex}(n,H) be the maximum number of edges in an nn-vertex graph containing no subgraph isomorphic to HH. A graph is 22-degenerate if every nonempty subgraph has a vertex of degree at most 22. The question is whether, for every finite bipartite graph HH, the following equivalence holds, where the implicit constant may depend on HH:

ex⁡(n,H)=O(n3/2)⟺every nonempty subgraph of H has a vertex of degree at most 2.\operatorname{ex}(n,H)=O(n^{3/2}) \quad\Longleftrightarrow\quad \text{every nonempty subgraph of }H\text{ has a vertex of degree at most }2.

Janzer (2023)

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 HH has maximum degree at most rr, then ex⁡(n,H)=O(n2−1/r)\operatorname{ex}(n,H)=O(n^{2-1/r}). Erdős proposed extending this upper bound to all rr-degenerate bipartite graphs. Alon, Krivelevich and Sudakov proved the weaker general estimate O(n2−1/(4r))O(n^{2-1/(4r)}) for such graphs. The case r=2r=2 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.

Source: 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

Never refreshed

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.