Negative correlations in combinatorics and statistical mechanics

在1847年，基尔霍夫推导出了一个公式，表示一个电网络的有效电导是其每个分支元件电导的函数。 该公式是两个多项式的商，其中分子和分母编码关于网络的最小连通子图的信息。 因此，电网络的物理性质可以理解为关于这些最小连通子图或生成树的定量陈述。 例如，如果某个分支的电导增加，则整个网络的有效电导不会减少。 这被称为“Rayleigh单调性”。 它转化为这样的陈述，对于任何两个不同的分支，如果随机选择一个生成树，那么这些分支是“负相关的”-其中一个在树中的存在使得另一个不太可能。 这一现象的一个类似物已经被证明适用于比电网络更一般的抽象组合几何。最近，人们证实网络可能具有更强的负相关性质。 我们不是随机选择一棵生成树，而是选择一个生成森林（一个无环但可能不连通的子网）。在这种情况下，不同分支的负相关性也是成立的。这意味着瑞利单调性属性。 如果这是真的，那么这种负相关特性就有可能解释20世纪60年代末对网络的数值观测。 这将从根本上更深入地理解网络的定量结构特性。

In 1847, Kirchhoff derived a formula for the effective conductance of an electrical network as a function of the conductances of each of its branch elements.  This formula is a quotient of two polynomials, in which the numerator and denominator encode information about the minimally connected subgraphs of the network.  The physical properties of electrical networks can thus be interepreted as quantitative statements about these minimally connected subgraphs, or spanning trees.  For example, if the conductance of some branch is increased then the effective conductance of the whole network does not decrease.  This is known as ``Rayleigh monotonicity''.  It translates into the statement that, for any two distinct branches, if one chooses a spanning tree at random then these branches are ``negatively correlated'' -- the presence of one of them in the tree makes the other one less likely.  An analogue of this phenomenon has been shown to hold for abstract combinatorial geometries much more general than electrical networks.Recently, it has been conjectured that an even stronger negative correlation property might hold for networks.  Instead of choosing a spanning tree at random we choose a spanning forest (an acyclic but perhaps not connected subnetwork) instead. Negative correlation of distinct branches is conjectured to hold in this case as well. This implies the Rayleigh monotonicity property.  If true, this negative correlation property has the potential to explain numerical observations about networks that go back to the late 1960s.  This would constitute a fundamentally deeper understanding of the quantitative structural properties of networks in general.