Return to search

The search for an excluded minor characterization of ternary Rayleigh matroids

Rayleigh matroids are a class of matroids with sets of bases that satisfy
a strong negative correlation property. Interesting characteristics include
the existence of an efficient algorithm for sampling the bases of a Rayleigh
matroid [7]. It has been conjectured that the class of Rayleigh matroids
satisfies Mason’s conjecture [14]. Though many elementary properties of
Rayleigh matroids have been established, it is not known if this class has a
finite set of minimal excluded minors. At this time, it seems unlikely that this
is the case. It has been shown that there is a single minimal excluded minor
for the smaller class of binary Rayleigh matroids [5]. The aim of this thesis
is to detail our search for the set of minimal excluded minors for ternary
Rayleigh matroids. We have found several minimal excluded minors for the
above class of matroids. However, our search is incomplete. It is unclear
whether 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. For
our method to answer this question definitively will require a new computer
program. This program would automate a step in our process that we have
done by hand: writing polynomials in at least ten indeterminates as a sum
with many terms, squared.

Identiferoai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/3531
Date January 2008
CreatorsPhillips, Stephanie
Source SetsUniversity of Waterloo Electronic Theses Repository
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation

Page generated in 0.0024 seconds