Electronic Thesis/Dissertation
Large Families of Matroids with the Same Tutte Polynomial Open Access
One of the most important invariants of a matroid is the Tutte polynomial, which is defined as follows:t(M;x,y)= (x−1)r(E)−r(X)(y−1)|X|−r(X). X⊆EIn essence, it is a polynomial in two variables, x and y, that records the number of subsets X of the ground set E of the matroid M having given cardinality and rank. From its Tutte polynomial, one can deduce a great deal of information about a matroid; indeed in some cases the Tutte polynomial determines the matroid itself. In this thesis we are interested in the extreme opposite, i.e., we are interested in cases where the Tutte polynomial is the common Tutte polynomial of a very large collection of nonisomorphic matroids. Here we construct large families of matroids (superexponential in the cardinality of the ground set) having the same Tutte polynomial.The families of matroids we construct also share another important matroid invariant, the (abstract) lattice of cyclic flats. The collection of cyclic flats of a matroid forms a lattice when ordered by inclusion. An axiom scheme for a matroid by its collection of cyclic flats and their ranks was given by Bonin and de Mier [3] (and earlier by Sims [15]), who also showed that for any lattice L, there exists a (fundamental transversal) matroid whose lattice of cyclic flats is isomorphic to L. In the theme of matching large families of matroids to a matroid invariant (where possible), we determine the possible rank functions of the fundamental transversal matroids having a given abstract lattice as its lattice of cyclic flat (Theorem 4.3.3).Our families of matroids having the same Tutte polynomial and lattice of cyclic flats all generalize a construction of Gim ́enez [10], who showed that all matroids in his family have the same lattice of cyclic flats, though he did not realize that they have the same Tutteivpolynomial as well. Our generalizations produce yet larger families of matroids than the families of Gim ́enez.In the proofs of the main results of this thesis, we make extensive use of a tool that we have developed: rank sublattices of the lattice of cyclic flats. We define rank sublattices and explore some of their properties in an early chapter. To each subset X of the ground set of the matroid M, we associate a subset R(X) of the collection of cyclic flats of M. The subset R(X) is always a sublattice of the lattice of cyclic flats, and it determines the rank of X. Thus we may think of R(X) as a refinement of the rank r(X). We hope that the notion of rank sublattices will continue to serve as a useful tool in other problems in matroid theory.
- License
Notice to Authors
If you are the author of this work and you have any questions about the information on this page, please use the Contact form to get in touch with us.
Relationships
Items
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
Shoda_gwu_0075A_11529.pdf | 2018-01-16 | Open Access |
|