Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-17T21:25:46.240Z Has data issue: false hasContentIssue false

Rayleigh Matroids

Published online by Cambridge University Press:  31 July 2006

YOUNGBIN CHOE
Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 (e-mail: [email protected], [email protected])
DAVID G. WAGNER
Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 (e-mail: [email protected], [email protected])

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.

Type
Paper
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)