Negative correlations in combinatorics and statistical mechanics

组合数学和统计力学中的负相关

• 批准号: 105392-2007
• 负责人: Wagner, David
• 金额: $ 1.24万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=362437
• 关键词: Negative; correlations; combinatorics; 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.

1847年，Kirchhoff导出了一个网络有效电导公式，它是每个支路元素的电导的函数。这个公式是两个多项式的商，其中分子和分母编码关于网络的最小连通子图的信息。因此，电网络的物理性质可以解释为关于这些最小连通子图或生成树的定量陈述。例如，如果某个支路的电导增加，则整个网络的有效电导不会减少。这就是我们所知的‘Rayleigh单调性’。对于任何两个不同的支路，它可以翻译成这样的陈述如果随机地选择一棵生成树，那么这些分支是“负相关的”--在树中出现其中一棵使得另一棵不太可能出现。与此类似的现象已被证明适用于比电网络更一般的抽象组合几何。最近，有人猜测网络可能具有更强的负相关性。*我们不是随机选择一棵生成树，而是选择一个生成林(一个无环但可能不连通的子网络)。在这种情况下，不同分支的负相关也被推测为成立。这意味着瑞利单调性性质。如果为真，这种负相关性性质有可能解释追溯到20世纪60年代末关于网络的数值观察。这将构成对一般网络数量结构属性的根本更深层次的理解。