Dissecting an integer polymatroid
One way to define an integer polymatroid ρ is via its independent set polytope, whose faces are parallel translates 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, dual-closed class of matroids C, we can define another class: the class of k-polymatroids whose k-natural matroids are in C. 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 U_{2,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. Next, we generalize this problem to the class of k-polymatroids whose k-natural matroids lack both U_{2,b}- and U_{b-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 bound 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 U_{2,b}- and U_{b-2,b}-minors. Finally, we investigate a further generalization to the class of k-polymatroids whose k-natural matroids lack both U_{a,b}- and U_{b-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.