The positive graph conjecture

About 2 years old · traced to

Let HH be a graph. Its homomorphism density in a bounded measurable symmetric kernel W:[0,1]2→RW:[0,1]^2\to\mathbb{R} is

tH(W)=∫[0,1]V(H)∏ij∈E(H)W(xi,xj) dμV(H),t_H(W)=\int_{[0,1]^{V(H)}}\prod_{ij\in E(H)}W(x_i,x_j)\,d\mu^{V(H)},

where bcbc is Lebesgue measure. An automorphism ϕ\phi of HH is a stable involution if it is an involution for which there is a partition L∪R∪FL\cup R\cup F of V(H)V(H), with FF a vertex cut separating LL and RR, such that ϕ\phi exchanges LL and RR, fixes FF, and FF is an independent set. A graph is positive if tH(W)≥0t_H(W)\geq 0 for every such kernel WW.

The positive graph conjecture. A graph HH is positive if and only if it has a stable involution.

The forward implication would characterize all graphs whose homomorphism densities are non-negative on arbitrary kernels; the reverse implication follows from the Cauchy--Schwarz inequality. The conjecture is also viewed as an analogue of Hilbert's seventeenth problem, with stable-involution graphs playing the role of squares. No resolution is supplied in the source.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. The positive graph conjecture

    Let HH be a bipartite graph, let tH(f)t_H(f) be its homomorphism density functional, and let a stable involution of HH mean the graph-theoretic object specified by the source. Positive graph conjecture. The quantity tH(f)t_H(f) is non-negative for every function f:[0,1]2→Rf:[0,1]^2\rightarrow\mathbb{R} if and only if HH has a stable involution. The source attributes this conjecture to CCHLL12 and mentions it as a related open problem concerning the characterization of graphs with non-negative homomorphism densities.

    source: David Conlon and Joonkyung Lee, “Finite reflection groups and graph norms”, arXiv:1611.05784 (2017).

References

Primary source

David Conlon, Joonkyung Lee and Leo Versteegen, “Around the positive graph conjecture”, arXiv:2404.17467 (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.