KNRS conjecture on locally dense graphs

Let GG be an nn-vertex graph. Call GG (ε,d)(\varepsilon,d)-dense if, for every UV(G)U\subseteq V(G) with Uεn|U|\geq \varepsilon n,

e(G[U])d(U2).e(G[U])\geq d\binom{|U|}{2}.

For a graph HH, let tH(G)t_H(G) denote its homomorphism density and let e(H)e(H) denote its number of edges.

KNRS conjecture. Let HH be a graph. For every d,η(0,1)d,\eta\in(0,1), there exists ε=ε(d,η,H)\varepsilon=\varepsilon(d,\eta,H) such that if GG is (ε,d)(\varepsilon,d)-dense, then

tH(G)(1η)de(H).t_H(G)\geq (1-\eta)d^{e(H)}.

This conjecture asks whether one-sided local density guarantees the expected lower bound for homomorphism densities, including for nonbipartite graphs. It is attributed here to Kohayakawa, Nagle, Rödl, and Schacht; the paper notes that the general conjecture remains open, while a weaker regular version is known in some cases.

Sources & referencesView supporting material

Primary source

Seonghyuk Im, Ruonan Li and Hong Liu, “Sidorenko's conjecture for subdivisions and theta substitutions”, arXiv:2408.03491 (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.