Semidefinite functions on categories

MaRDI QIDQ1028868zbMATH OpenFDO

Authors László Lovász, Alexander Schrijver

Publication date 8 July 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/117532, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i2r14.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

connection matrices

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Categories of sets, characterizations (18B05)

Review text

Summary: Freedman, Lovász and Schrijver characterized graph parameters that can be represented as the (weighted) number of homomorphisms into a fixed graph. Several extensions of this result have been proved. We use the framework of categories to prove a general theorem of this kind. Similarly as previous resuts, the characterization uses certain infinite matrices, called connection matrices, which are required to be positive semidefinite.

Recommendations

• Graph parameters and semigroup functions
• Dual graph homomorphism functions
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Counting graph homomorphisms
• Contractors and connectors of graph algebras

Cited in

(5)

• Graph parameters and semigroup functions
• Logical equivalences, homomorphism indistinguishability, and forbidden minors
• The complexity of homomorphism reconstructibility
• The complexity of homomorphism reconstructibility
• Dual graph homomorphism functions

This page was built for publication: Semidefinite functions on categories

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