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.