The doubly nonnegative function and good graph conjecture

Let G+\mathcal{G}_+ be the set of bounded measurable nonnegative symmetric functions on [0,1]2[0,1]^2, and let H\mathcal{H} be the space of bounded measurable real functions on [0,1]2[0,1]^2. A function gG+g\in\mathcal{G}_+ is doubly nonnegative if there is an hHh\in\mathcal{H} such that

g(x,y)=[0,1]h(x,z)h(y,z),dμ(z),g(x,y)=\int_{[0,1]}h(x,z)h(y,z)\\,d\mu(z),

equivalently, if it is nonnegative, symmetric, and has nonnegative spectrum. A function gg is nice if t(G,g)ge(G)t(G,g)\geq\lVert g\rVert^{{\rm e}(G)} for every simple graph GG, and a simple graph GG is good if this inequality holds for every doubly nonnegative gg.

The doubly nonnegative function and good graph conjecture. All doubly nonnegative functions are nice, and all simple graphs are good.

These two assertions concern the inequality relating graph homomorphism integrals to the mean of the function. The paper establishes that all graphs with at most five vertices are good and proves several further families, but the assertions in full remain open.

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.