Negatively correlated random variables and Mason's conjecture

2006/02/28 by David G. Wagner, Wagner, David G. · 3 citations
Mathematics · #05A20 #05B35 #60C05 #82B20 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.math/0602648

openalex publication_date 2006/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Mason's Conjecture asserts that for an m--element rank r matroid \M the sequence (I_k/\binommk: 0≤ k≤ r) is logarithmically concave, in which I_k is the number of independent k--sets of \M. A related conjecture in probability theory implies these inequalities provided that the set of independent sets of \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 \Q that satisfies the Rayleigh condition then \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--sum of uniform matroids satisfies the Rayleigh condition. Numerous conjectures and auxiliary results are included.

Cited by

• Normalized matching property for competing urn models
• Ported Tutte Functions of Extensors and Oriented Matroids
• Correlations in random cluster model at q=1

Related

• Log-concavity for independent sets of valuated matroids
• Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids
• Strictness of the log-concavity of generating polynomials of matroids
• Log-concavity in Combinatorics
• Log-Concave Polynomials I: Entropy and a Deterministic Approximation\n Algorithm for Counting Bases of Matroids