Negative correlations in combinatorics and statistical mechanics

点击翻译按钮获取中文摘要

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.