Rayleigh matroids

被引:19
作者
Choe, Youngbin [1 ]
Wagner, David G. [1 ]
机构
[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada
关键词
D O I
10.1017/S0963548306007541
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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 L8 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 L8 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.
引用
收藏
页码:765 / 781
页数:17
相关论文
共 25 条
[1]  
[Anonymous], 2003, PUBLICATIONS MATHEMA, DOI DOI 10.1007/S10240-003-0016-0
[2]  
Balabanian N., 1969, ELECT NETWORK THEORY
[3]  
Brooks RL., 1940, Duke Math. J., V7, P312, DOI 10.1215/S0012-7094-40-00718-9
[4]  
BRUTER CP, 1971, CR ACAD SCI PARI A B, V273, pA9
[5]   Homogeneous multivariate polynomials with the half-plane property [J].
Choe, YB ;
Oxley, JG ;
Sokal, AD ;
Wagner, DG .
ADVANCES IN APPLIED MATHEMATICS, 2004, 32 (1-2) :88-187
[6]  
CHOE YB, 2003, THESIS U WATERLOO
[7]  
CHOE YB, UNPUB RAYLEIGH MONOT
[8]  
Corp J, 2001, ARS COMBINATORIA, V58, P111
[9]  
FEDER T, 1992, P 24 ANN ACM STOC VI
[10]   NEW RESULTS ON STABLE MULTIDIMENSIONAL POLYNOMIALS .1. CONTINUOUS CASE [J].
FETTWEIS, A ;
BASU, S .
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS, 1987, 34 (10) :1221-1232