The locally dense graph homomorphism conjecture

About 7 years old · traced to

For a graph HH, call it (ε,d)(\varepsilon,d)-dense if every subset X⊆V(H)X\subseteq V(H) with ∣X∣≥ε∣V(H)∣|X|\geq\varepsilon|V(H)| spans at least d2∣X∣2\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.

References

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.