The locally dense graph homomorphism conjecture

For a graph HH, call it (ε,d)(\varepsilon,d)-dense if every subset XV(H)X\subseteq V(H) with XεV(H)|X|\geq\varepsilon|V(H)| spans at least d2X2\frac d2|X|^2 edges. For a graph GG, write e(G)=E(G)\mathrm{e}(G)=|E(G)| and v(G)=V(G)\mathrm{v}(G)=|V(G)|.

Locally dense graph homomorphism conjecture. For every graph GG and every δ,d(0,1)\delta,d\in(0,1), there exists ε=ε(δ,d,G)\varepsilon=\varepsilon(\delta,d,G) such that every sufficiently large (ε,d)(\varepsilon,d)-dense graph HH admits at least

(de(G)δ),v(H)v(G)(d^{\mathrm{e}(G)}-\delta)\\,\mathrm{v}(H)^{\mathrm{v}(G)}

homomorphisms from GG into HH.

This is a dense-graph counting assertion: local density should force approximately the expected number of homomorphisms at edge density dd. Its general validity is presented as a conjecture and remains open in the source.

Sources & referencesView supporting material

Primary source

Alexander Sidorenko, “Inequalities for doubly nonnegative functions”, arXiv:1905.08210 (2021).

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.