The rank of connection matrices and the dimension of graph algebras

2004/08/18 by László Lovász, Laszlo Lovasz, Lovasz, Laszlo · 2 citations
Computer Science · Mathematics · #05C99 #Advanced Graph Theory Research #Advanced Topics in Algebra #Combinatorics (math.CO) #FOS: Mathematics #Matrix Theory and Algorithms #math.CO #msc:05C99

paper · pdf · doi:10.48550/arxiv.math/0408232

12 pages

arxiv created 2004/08/18 · openalex publication_date 2004/08/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Connection matrices were introduced by Freedman, Lovasz and Schrijver [1], who used them to characterize graph homomorphism functions. The goal of this note is to determine the exact rank of these matrices. The result can be rephrased in terms of graph algebras (also introduced in [1]. Yet another version proves that if two k-tuples of nodes behave the same way from the point of view of graph homomorphisms, then they are equivalent under the automorphism group.

Cited by

• Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem
• Using dense graph limit theory to count cocycles of random simplicial complexes

Related

• Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Contractors and connectors of graph algebras
• Finiteness conditions for graph algebras over tropical semirings
• On a Theorem of Lovász that \hom(⋅, H) Determines the Isomorphism Type of H