Kohayakawa–Nagle–Rödl–Schacht forcing conjecture

About 2 years old · traced to

A graph GG is (p,δ)(p,\delta)-locally dense if every set S⊆V(G)S\subseteq V(G) with ∣S∣≥δ∣V(G)∣|S|\geq\delta|V(G)| satisfies e(S)≥p∣S∣2/2e(S)\geq p|S|^2/2. A graph HH is KNRS-forcing if, for every p,α∈(0,1)p,\alpha\in(0,1), there exist δ,ε>0\delta,\varepsilon>0 such that every (p,δ)(p,\delta)-locally dense graph GG satisfies t(H,G)>pe(H)+εt(H,G)>p^{e(H)}+\varepsilon, unless GG is (p,α)(p,\alpha)-quasirandom.

Kohayakawa–Nagle–Rödl–Schacht forcing conjecture. If HH is not a forest, then HH is KNRS-forcing.

This strengthens the Kohayakawa–Nagle–Rödl–Schacht conjecture by asserting that the only locally dense graphs asymptotically attaining the lower bound are quasirandom. The source does not state its resolution status.

References

Primary source

Domagoj Bradač, Benny Sudakov and Yuval Wigderson, “Counting subgraphs in locally dense graphs”, arXiv:2406.12418 (2024).

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.