- Matroid invariants and counting graph homomorphisms
- Linear Algebra and its Applications
- Pages (from-to)
- Document type
- Faculty of Science (FNWI)
- Korteweg-de Vries Institute for Mathematics (KdVI)
The number of homomorphisms from a finite graph F to the complete graph Kn is the evaluation of the chromatic polynomial of F at n. Suitably scaled, this is the Tutte polynomial evaluation T(F;1−n,0) and an invariant of the cycle matroid of F. De la Harpe and Jaeger  asked more generally when is it the case that a graph parameter obtained from counting homomorphisms from F to a fixed graph G depends only on the cycle matroid of F. They showed that this is true when G has a generously transitive automorphism group (examples include Cayley graphs on an abelian group, and Kneser graphs).
Using tools from multilinear algebra, we prove the converse statement, thus characterizing finite graphs G for which counting homomorphisms to G yields a matroid invariant. We also extend this result to finite weighted graphs G (where to count homomorphisms from F to G includes such problems as counting nowhere-zero flows of F and evaluating the partition function of an interaction model on F).
- go to publisher's site
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.