The positive graph conjecture
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 1
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).
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.