← All problems

Erdős Problem #147 — Minimum degree and bipartite Turán exponents

42 years old · traced to

Let HH be a fixed finite bipartite graph, and write δ(H)\delta(H) for its minimum degree. For a positive integer nn, 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. The question asks whether, for every such HH with δ(H)=r\delta(H)=r an integer at least 33, there is a constant ε(H)>0\varepsilon(H)>0 such that, as n→∞n\to\infty,

ex⁡(n,H)=Ω ⁣(n2−1/(r−1)+ε(H)).\operatorname{ex}(n,H)=\Omega\!\left(n^{2-1/(r-1)+\varepsilon(H)}\right).

Equivalently, must there exist c(H)>0c(H)>0 and n0(H)n_0(H) such that

ex⁡(n,H)≥c(H)n2−1/(r−1)+ε(H)\operatorname{ex}(n,H)\ge c(H)n^{2-1/(r-1)+\varepsilon(H)}

for every integer n≥n0(H)n\ge n_0(H)? 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 C8C_8, K4,4K_{4,4}, and the cube Q3Q_3. 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 HH with minimum degree at least rr, it yields some δ>0\delta>0, depending on HH, such that ex⁡(n,H)=Ω(n2−2/r+δ)\operatorname{ex}(n,H)=\Omega(n^{2-2/r+\delta}). 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.

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.