کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6416145 | 1631101 | 2016 | 11 صفحه PDF | دانلود رایگان |
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 [8] 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).
Journal: Linear Algebra and its Applications - Volume 494, 1 April 2016, Pages 263-273