Matroid invariants and counting graph homomorphisms

详细信息    查看全文

• 作者：Andrew Goodall^a ; ¹ ; ^{andrew@iuuk.mff.cuni.cz" class="auth_mail" title="E-mail the corresponding author} ; Guus Regts^b ; ² ; ^{guusregts@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Lluí ; s Vena^a ; ¹ ; ^{lluis.vena@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：primary ; 05C15 ; 05C60 ; 15A72 ; secondary ; 52C40 ; 05C30 ; 05C31
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：1 April 2016
• 年：2016
• 卷：494
• 期：Complete
• 页码：263-273
• 全文大小：329 K

文摘

The number of homomorphisms from a finite graph F   to the complete graph 16000252&_mathId=si1.gif&_user=111111111&_pii=S0024379516000252&_rdoc=1&_issn=00243795&md5=87925b350243cd0324fd636aa5592a7c" title="Click to view the MathML source">K_n$K_n$ is the evaluation of the chromatic polynomial of F at n  . Suitably scaled, this is the Tutte polynomial evaluation 16000252&_mathId=si2.gif&_user=111111111&_pii=S0024379516000252&_rdoc=1&_issn=00243795&md5=3effcc12bd6151fbe00cd476ad8b5832" title="Click to view the MathML source">T(F;1−n,0)$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).