Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$17,000.00

Negative correlations in combinatorics and statistical mechanics

EF 2008-09

Résumé
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.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
105392-2007
Name nom
Wagner, David
Department département
Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2008
Competition year année de concours
2007
Award amount
17000
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
337
Committee name en
Pure & Applied Maths - B
Committee name fr
Maths pures et appliquées - B
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
2
Nb partie
5
Application title
Negative correlations in combinatorics and statistical mechanics
Keyword
NA
Application summary
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.