The positive graph conjecture

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

tH(W)=[0,1]V(H)ijE(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 LRFL\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 1

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]2Rf:[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).

Sources & referencesView supporting material

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.