Weighted enumeration of spanning subgraphs with degree constraints
Weighted enumeration of spanning subgraphs with degree constraints
复制标题
具有度约束的跨越子图的加权枚举
DOI：
10.1016/j.jctb.2008.07.007
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
D. Wagner
中科院分区：
文献类型：
--
作者：
D. Wagner
关于（单变量）匹配多项式的Heilmann-Lieb定理指出，多项式∑ kk（G）yk只有真实的非正零点，其中k（G）是图G的k-边匹配数.这个定理有一个更强的多元版本。我们提供了一个一般的方法，通过它可以证明“Heilmann-Lieb型定理”的各种多项式连接到图G。这些多项式是多变量生成函数G的生成子图与一定的权重和约束，定理指定这些多项式是非零的区域。这样的定理的后果，在某些概率模型的生成子图G的相变的情况下。
The Heilmann–Lieb Theorem on (univariate) matching polynomials states that the polynomial ∑kmk(G)ykhas only real nonpositive zeros, in which mk(G) is the number of k-edge matchings of a graph G. There is a stronger multivariate version of this theorem. We provide a general method by which “theorems of Heilmann–Lieb type” can be proved for a wide variety of polynomials attached to the graph G. These polynomials are multivariate generating functions for spanning subgraphs of G with certain weights and constraints imposed, and the theorems specify regions in which these polynomials are nonvanishing. Such theorems have consequences for the absence of phase transitions in certain probabilistic models for spanning subgraphs of G.