Contractors and connectors of graph algebras

DOI10.1002/JGT.20343MaRDI QIDQ3605157zbMATH OpenOpenAlexFDO

Authors Balázs Szegedy, László Lovász

Publication date 20 February 2009

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

graph homomorphismTutte polynomialconnectorgraph algebracontractorcontraction-deletionhomomorphism functions

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph operations (line graphs, products, etc.) (05C76)

Abstract: We study generalizations of the "contraction-deletion" relation of the Tutte polynomial, and other similar simple operations, to other graph parameters. The question can be set in the framework of graph algebras introduced by Freedman, Lovasz and Schrijver, and it relates to their behavior under basic graph operations like contraction and subdivision. Graph algebras were introduced to study and characterize homomorphism functions. We prove that for homomorphism functions, these graph algebras have special elements called ``contractors and ``connectors. This gives a new characterization of homomorphism functions.

Recommendations

• Homomorphisms and polynomial invariants of graphs
• Contraction-deletion invariants for graphs
• Perfect matchings, rank of connection tensors and graph homomorphisms
• Homomorphisms and Polynomial Invariants of Graphs
• Weighted graph homomorphisms and the Tutte polynomial

Cites work

• Generalized quasirandom graphs
• Limits of dense graph sequences
• Moments of two-variable functions and the uniqueness of graph limits
• Reflection positivity, rank connectivity, and homomorphism of graphs
• The rank of connection matrices and the dimension of graph algebras

Cited in

(15)

• On recognizing graphs by numbers of homomorphisms
• Local WL invariance and hidden shades of regularity
• The contractum in algebraic graph rewriting
• Perfect matchings, rank of connection tensors and graph homomorphisms
• Connector algebras for C/E and P/T nets' interactions
• Graphon convergence of random cographs
• Estimating and understanding exponential random graph models
• Semidefinite functions on categories
• Graph parameters from symplectic group invariants
• Edge cut splitting formulas for Tutte-Grothendieck invariants
• The large deviation principle for the Erdős-Rényi random graph
• On the number of \(B\)-flows of a graph
• Contractors for flows
• Contractors for flows
• Finitely forcible graphons

This page was built for publication: Contractors and connectors of graph algebras

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