Rayleigh Matroids

Y. -B. Choe, D. G. Wagner

Published 2003-07-08, updated 2003-09-05Version 3

Motivated by a property of linear resistive electrical networks, we introduce the class of Rayleigh matroids. This is a subclass of the balanced matroids introduced by Feder and Mihail [FM] in 1992. We prove a variety of results relating Rayleigh matroids to other well-known classes -- in particular, we show that a binary matroid is Rayleigh if and only if it does not contain S_8 as a minor. This has the consequence that a binary matroid is balanced if and only if it is Rayleigh, and provides the first complete proof in print that S_8 is the only minor-minimal binary non-balanced matroid, as claimed in [FM]. We also give an example of a balanced matroid which is not Rayleigh.