Negatively Correlated Random Variables and Mason’s Conjecture for Independent Sets in Matroids

By David G. Wagner. 2006

60 citations recorded by the source corpus.

Abstract.Mason’s Conjecture asserts that for an m-element rank r matroid $${\mathcal{M}}$$ the sequence$$ (I_k /\left(_k^m\right): 0 \leq k \leq r) $$ is logarithmically concave, in which Ik is the number of independent k-sets of $${\mathcal{M}}$$ . A related conjecture in probability theory implies these inequalities provided that the set of independent sets of $${\mathcal{M}}$$ satisfies a strong negative correlation property we call the Rayleigh condition. This condition is known to hold for the set of bases of a regular matroid. We show that if ω is a weight function on a set system $${\mathcal{Q}}$$ that satisfies the Rayleigh condition then $${\mathcal{Q}}$$ is a convex delta-matroid and ω is logarithmically submodular. Thus, the hypothesis of the probabilistic conjecture leads inevitably to matroid theory. We also show that two-sums of matroids preserve the Rayleigh condition in four distinct senses, and hence that the Potts model of an iterated two-sums of uniform matroids satisfies the Rayleigh condition. Numerous conjectures and auxiliary results are included.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/f8e87f78c6aae1170285b937b3d631f7c840d98c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Statistics and Probability

Citations in the corpus

Multivariate stable polynomials: theory and applications (2009, unknown): “10 (Section 4 of [15]).”
Polynomials with the half-plane property and matroid theory (2006, background): “ne if it has degree at most one in each variable. The study of the relationship between polynomials with the half-plane property and matroid theory has since then been continued in a series of papers [5, 7, 12, 29, 30] where several interesting open questions have been raised. In this paper we prove”
h-Vectors of matroids and logarithmic concavity (2012, background): “These shellable simplicial complexes led to suspect that various log-concavity conjectures on matroids might not be true in general [29,31].”
Hyperbolicity and stable polynomials in combinatorics and probability (2012, result): “This was later shown to be equivalent to Wagner’s Rayleigh condition [Wag08], which will discuss further in Section 6.”
Hyperdeterminantal relations among symmetric principal minors (2006, background): “Wagner [ 14 ] asks how to characterize all functions ! satisfying these conditions and arising from some matrix A, i.e., such that !(I) = AI is the minor of A with columns and rows indexed by the subset I [n].”