Kohayakawa–Nagle–Rödl–Schacht forcing conjecture

A graph GG is (p,δ)(p,\delta)-locally dense if every set SV(G)S\subseteq V(G) with SδV(G)|S|\geq\delta|V(G)| satisfies e(S)pS2/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.

Sources & referencesView supporting material

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.