Edge-reflection positivity and weighted graph homomorphisms

DOI10.1016/J.JCTA.2014.09.006MaRDI QIDQ472167zbMATH OpenOpenAlexFDO

Authors Guus Regts

Publication date 19 November 2014

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.6497

zbMATH Keywords

edge-coloring modeledge-reflection positivitygraph homomorphismgraph invariantpartition functionvertex model

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: B. Szegedy [Edge coloring models and reflection positivity, {sl Journal of the American Mathematical Society} {�f 20} (2007) 969--988] showed that the number of homomorphisms into a weighted graph is equal to the partition function of a complex edge-coloring model. Using some results in geometric invariant theory, we characterize for which weighted graphs the edge-coloring model can be taken to be real valued that is, we characterize for which weighted graphs the number of homomorphisms into them are edge-reflection positive. In particular, we determine explicitly for which simple graphs the number of homomorphisms into them is equal to the partition function of a real edge-coloring model. This answers a question posed by Szegedy.

Recommendations

• A characterization of edge-reflection positive partition functions of vertex-coloring models
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Computing the partition function for graph homomorphisms
• Edge coloring models and reflection positivity
• Counting homomorphisms and partition functions

Cites work

• Characterizing partition functions of the vertex model
• Edge coloring models and reflection positivity
• Edge coloring models as singular vertex coloring models
• Graph invariants related to statistical mechanical models: Examples and problems
• scientific article; zbMATH DE number 3908560 (Why is no real title available?)
• scientific article; zbMATH DE number 3508744 (Why is no real title available?)
• scientific article; zbMATH DE number 3632801 (Why is no real title available?)
• Large networks and graph limits
• Limits of dense graph sequences
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Symmetry, Representations, and Invariants
• Tensor invariants for certain subgroups of the orthogonal group

Cited in

(6)

• Some applications of Wagner's weighted subgraph counting polynomial
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Edge coloring models and reflection positivity
• A characterization of edge-reflection positive partition functions of vertex-coloring models
• Positive graphs
• Positive graphs

This page was built for publication: Edge-reflection positivity and weighted graph homomorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q472167)