Some Problems on Matroids and Integer Polymatroids
Open AccessA \\emph{matroid} is a combinatorial object that satisfies axiomsabstracting linear independence, and a \\emph{$k$-polymatroid} is ageneralization of a matroid in which the rank of an element may begreater than one but cannot exceed $k$. We discuss a few problemsinvolving matroids and $k$-polymatroids.We develop a theory of single-element extensions of $k$-polymatroidsanalogous to that of matroids. As for matroids, we may restrict ourattention to the flats of the original polymatroid. To see this, wefix a $k$-polymatroid $(\\rho, S)$. For each single-element extension$(\\bar{\\rho}, S \\cup e)$, we define a function $\\mu$ as follows: foreach flat $F$ of $\\rho$, let $\\mu(F) = \\bar{\\rho}(F \\cup e) -\\rho(F)$. We describe properties that $\\mu$ necessarily satisfies,and we show that these are sufficient as well. Therefore, given apolymatroid $\\rho$ and a function $\\mu$ satisfying these properties,we may define a single-element extension $\\bar{\\rho}$. In this case,we give a convenient description of the flats of $\\bar{\\rho}$. Wealso describe single-element coextensions and cyclic flats of$k$-polymatroids.Using the theory of single-element extensions of $k$-polymatroids, wedescribe a canonical deletion algorithm that generates all$k$-polymatroids on a given ground set. We implemented this algorithmon a desktop computer and produced a catalog of all $2$-polymatroidson seven elements or fewer, up to isomorphism. We made the surprisingdiscovery that, in contrast to what is conjectured for matroids on $n$elements, the number of $2$-polymatroids on seven elements fails to beunimodal in rank. This also stands in contrast to many well-knownunimodality results in combinatorics. By interpreting integerpolymatroids as solutions to integer programs, we were able to confirmthe enumeration results using the integer programming software suiteSCIP.The bases of \\emph{base-orderable} and \\emph{strongly base-orderable}matroids satisfy special exchange properties and have receivedconsiderable interest. The classes of base-orderable and strongbase-orderable matroids are examples of \\emph{complete} classes. Suchclasses are closed under many common matroid operations such asminors, direct sum, principal extension, duality, and induction bybipartite graphs. We define a condition, which has heretoforereceived almost no attention, called \\emph{$k$-base-orderable} thatlies between base-orderability and strong base-orderability. Bygeneralizing an example of Ingleton, we describe matroids that are$k$-base-orderable but not $(k+1)$-base orderable for every $k$. Wealso describe an infinite family of excluded minors for the class ofstrongly base-orderable matroids that are themselves base-orderable aswell as an infinite collection of excluded minors for the class ofgammoids each of which has precisely six cyclic flats. We also provethat a paving matroid is base-orderable if and only if it does nothave a minor isomorphic to $M(K_4)$. We discuss at length aconjecture of Ingleton on excluded minors for base-orderable matroids.
- 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.
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
Savitsky_gwu_0075A_12539.pdf | 2018-01-16 | Open Access |
|