Combinatorics, Probability and Computing



Paper

Rayleigh Matroids


YOUNGBIN CHOE a1 1 and DAVID G. WAGNER a1 1
a1 Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 (e-mail: ybchoe@math.uwaterloo.ca, dgwagner@math.uwaterloo.ca)

Article author query
choe y   [Google Scholar] 
wagner dg   [Google Scholar] 
 

Abstract

Motivated by a property of linear resistive electrical networks, we introduce the class of Rayleigh matroids. These form a subclass of the balanced matroids defined by Feder and Mihail [9] 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 $\mathcal{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 $\mathcal{S}_{8}$ is the only minor-minimal binary non-balanced matroid, as claimed in [9]. We also give an example of a balanced matroid which is not Rayleigh.

(Published Online July 31 2006)
(Received September 5 2003)
(Revised September 24 2004)



Footnotes

1 Research supported by the Natural Sciences and Engineering Research Council of Canada under operating grant OGP0105392.