Perfect matchings, rank of connection tensors and graph homomorphisms

DOI10.1017/S0963548321000286OpenAlexW3186782809WikidataQ114116553 ScholiaQ114116553MaRDI QIDQ5886319

Jin-Yi Cai, Artem Govorov

Publication date: 31 March 2023

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548321000286

zbMATH Keywords

graph homomorphismsperfect matchingsgraph parametersgraph algebrastensor and tensor rank

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tensor invariants for certain subgroups of the orthogonal group
• Characterizing partition functions of the vertex model
• Characterizing partition functions of the edge-coloring model by rank growth
• Characterizing partition functions of the spin model by rank growth
• Limits of dense graph sequences
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Graph invariants in the spin model
• The six and eight-vertex models revisited
• Graph parameters and semigroup functions
• Generalized quasirandom graphs
• The rank of connection matrices and the dimension of graph algebras
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• The statistics of dimers on a lattice
• On recognizing graphs by numbers of homomorphisms
• Theorems on the Partition Functions of the Heisenberg Ferromagnets
• Corrigendum: The complexity of counting graph homomorphisms
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Holographic Algorithms
• Edge coloring models and reflection positivity
• Contractors and connectors of graph algebras
• Complexity Dichotomies for Counting Problems
• Complexity of Counting CSP with Complex Weights
• Quantum Groups in Two-Dimensional Physics
• Lov\'asz Meets Weisfeiler and Leman
• On a Theorem of Lovász that (&sdot, H ) Determines the Isomorphism Type of H
• Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
• A New Holant Dichotomy Inspired by Quantum Computation
• Holant problems and counting CSP
• Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms
• Symmetric Tensors and Symmetric Tensor Rank
• Dimer problem in statistical mechanics-an exact result
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The complexity of the counting constraint satisfaction problem
• Automata, Languages and Programming
• Operations with structures
• Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
• The Complexity of Symmetric Boolean Parity Holant Problems
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem