The search for an excluded minor characterization of ternary Rayleigh matroids

matroids;excluded minor characterization;Combinatorics and Optimization

Phillips, Stephanie

University of Waterloo

关键词: matroids;    excluded minor characterization;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/3531/1/thesisrevised.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Rayleigh matroids are a class of matroids with sets of bases that satisfya strong negative correlation property. Interesting characteristics includethe existence of an efficient algorithm for sampling the bases of a Rayleighmatroid [7]. It has been conjectured that the class of Rayleigh matroidssatisfies Mason’s conjecture [14]. Though many elementary properties ofRayleigh matroids have been established, it is not known if this class has afinite set of minimal excluded minors. At this time, it seems unlikely that thisis the case. It has been shown that there is a single minimal excluded minorfor the smaller class of binary Rayleigh matroids [5]. The aim of this thesisis to detail our search for the set of minimal excluded minors for ternaryRayleigh matroids. We have found several minimal excluded minors for theabove class of matroids. However, our search is incomplete. It is unclearwhether the set of excluded minors for this set of matroids is finite or not,and, if finite, what the complete set of minimal excluded minors is. Forour method to answer this question definitively will require a new computerprogram. This program would automate a step in our process that we havedone by hand: writing polynomials in at least ten indeterminates as a sumwith many terms, squared.