The positive graph conjecture
Let be a graph. Its homomorphism density in a bounded measurable symmetric kernel is
where is Lebesgue measure. An automorphism of is a stable involution if it is an involution for which there is a partition of , with a vertex cut separating and , such that exchanges and , fixes , and is an independent set. A graph is positive if for every such kernel .
The positive graph conjecture. A graph 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.
The positive graph conjecture
Let be a bipartite graph, let be its homomorphism density functional, and let a stable involution of mean the graph-theoretic object specified by the source. Positive graph conjecture. The quantity is non-negative for every function if and only if 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
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.