TOPICS
Search

Rayleigh Matroid


A Rayleigh matroid is a matroid with set of matroid bases B(M) whose basis generating polynomial B_M(x)=sum_(B in B(M))product_(e in B)x_e satisfies the Rayleigh inequalities

 (partial_eB_M)(partial_fB_M)-B_Mpartial_epartial_fB_M>=0

for every pair of distinct ground set elements e,f and all positive weights x (Choe and Wagner 2006). Here partial_e denotes partial differentiation with respect to x_e. The condition expresses pairwise negative correlation in the probability measure on matroid bases proportional to product_(e in B)x_e.

The stronger Z-Rayleigh property uses

 Z_M(q,x)=sum_(A subset= E)q^(-r(A))product_(e in A)x_e,

where r(A) is the matroid rank, and requires the same derivative inequality for every 0<q<=1. Zhao and Zhou (2026) proved that every finite matroid of rank or corank at most 3 is Z-Rayleigh. Such matroids also satisfy the Rayleigh inequalities for the generating polynomials of independent sets and spanning sets. This strengthens the previously known rank-three basis-Rayleigh theorem. The rank restriction cannot be discarded: the rank-four matroid S_8 already fails the basis-Rayleigh property (Choe and Wagner 2006).


See also

Matroid, Matroid Basis, Matroid Rank

Explore with Wolfram|Alpha

References

Choe, Y.-B. and Wagner, D. G. "Rayleigh Matroids." Combin. Probab. Comput. 15, 765-781, 2006. https://doi.org/10.1017/S0963548306007541.Zhao, Q. and Zhou, X. "Every Rank-Three Matroid Is Z-Rayleigh." 11 Nov 2026. https://arxiv.org/abs/2611.15512v1.

Cite this as:

Weisstein, Eric W. "Rayleigh Matroid." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RayleighMatroid.html

Subject classifications