UW Combinatorics and Geometry Seminar: Fiona Young

One way to define an integer polymatroid ρ is via its independent set polytope, whose faces are parallel translations of the independent set polytopes of the minors of ρ. To better understand the interior of this polytope, we endow a structure on this polytope which relates to the polymatroid operation of compression and the k-natural matroid of ρ. The latter can be intuited as follows: if we think of a polymatroid as a subspace arrangement, then to obtain its k-natural matroid, freely place k points on each subspace and then delete the original subspaces.

For a given minor-closed class of matroids , we can define another class: the class of k-polymatroids whose k-natural matroids are in . This new class is (polymatroid) minor-closed as well as closed under a generalization of matroid duality known as k-duality. For the case k=2, Bonin and Long determined the set of excluded minors for the class of k-polymatroids whose k-natural matroids are binary (i.e. lacking a U2,4-minor); they found an infinite sequence of excluded minors, along with eight other excluded minors that do not belong to this sequence. We extend their result to larger k and find that the set of excluded minors becomes finite for k≥3.

We generalize this problem to the class of k-polymatroids whose k-natural matroids lack both U2,b- and Ub−2,b- minors. As b grows, the original method becomes increasingly unwieldy and that is where the polytopal perspective comes into play. We define a notion of boundedness for polymatroids and show that, under optimal conditions, the bounds on the singleton and doubleton minors of ρ completely determine the bounds on ρ. This holds the key to showing that when k is sufficiently large, there are finitely many excluded minors for the class of k-polymatroids whose k-natural matroids lack both U2,b- and Ub−2,b- minors.

We investigate a further generalization to the class of k-polymatroids whose k-natural matroids lack both Ua,b- and Ub−a,b- minors. Curiously, here we find many infinite sequences of excluded minors having a similar flavor to the infinite sequence found by Bonin and Long.