Sums of squares and negative correlation for spanning forests of series parallel graphs

MaRDI QIDQ3166100zbMATH OpenFDO

Authors Alejandro Erickson

Publication date 21 October 2012

Full work available at URL https://arxiv.org/abs/1008.3660

zbMATH Keywords

sums of squaresspanning forestsRayleigh difference

Mathematics Subject Classification ID

Trees (05C05) Combinatorial aspects of matroids and geometric lattices (05B35) Structure and representation theory of distributive lattices (06D05)

Abstract: We provide new evidence that spanning forests of graphs satisfy the same negative correlation properties as spanning trees, derived from Lord Rayleigh's monotonicity property for electrical networks. The main result of this paper is that the Rayleigh difference for the spanning forest generating polynomial of a series parallel graph can be expressed as a certain positive sum of monomials times squares of polynomials. We also show that every regular matroid is independent-set-Rayleigh if and only if every basis-Rayleigh binary matroid is also independent-set-Rayleigh.

Recommendations

• Negative Correlation in Graphs and Matroids
• Correlated Matroids
• Negatively correlated random variables and Mason's conjecture for independent sets in matroids
• A combinatorial proof of the Rayleigh formula for graphs
• Correlation bounds for fields and matroids

Cited in

(2)

• A combinatorial proof of the Rayleigh formula for graphs
• Correlated Matroids

This page was built for publication: Sums of squares and negative correlation for spanning forests of series parallel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3166100)