Some Problems on Matroid Invariants and Integer Polymatroids
Open AccessA matroid is a combinatorial object that generalizes the notion of linear independence. Matroidtheory originates from both linear algebra and graph theory, yet cannot be fully captured by either. We are interested in the Tutte polynomial of a matroid and related matroid invariants, such as the G-invariant and configuration. In Chapter 2, we introduce a construction called the free m-cone of a matroid, which allows us to construct examples of pairs of matroids with the same G-invariant and different configurations. Additionally, we consider some variants of the free m-cone and prove similar results for these variants. We also prove that matroids with the same configuration may have arbitrarily large gaps in connectivity.We are also interested in integer polymatroids, which we refer to as just polymatroids, and whichgeneralize matroids by allowing elements to have rank greater than 1. We can study a polymatroid by looking at its natural matroid, a matroid that has the structure of the polymatroid. A subject of interest common to matroids and polymatroids is that of minor-closed classes. These are classes of polymatroids that are closed under two reduction operations, deletion and contraction. One can classify a minor-closed class by its excluded minors, the maximal polymatroids that do not belong to the class. In particular we focus on 2-polymatroids, for which an element can have rank at most 2. In Chapter 3, we determine the excluded minors for the class of 2-polymatroids whose natural matroids are binary, and for the class of 2-polymatroids whose natural matroids have no M(K4)-minor. By combining these two results, we obtain the excluded minors for the class of 2-polymatroids whose natural matroids are series-parallel.In Chapter 4, we introduce a new matroid invariant, called the broken circuit invariant, which isthe multiset of broken circuit complexes of a matroid, up to isomorphism. In particular, we consider rank-3 sparse paving matroids, for which this invariant can be understood in terms of graphs. We consider a special family of rank-3 sparse paving matroids, and prove that matroids in this family are distinguished by their broken circuit invariant. Furthermore, we show that we can identify when a matroid belongs to this class from the broken circuit invariant.
- All rights reserved
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.