Abstract:
One way to define an integer polymatroid \$\rho\$ is via its independent set polytope, whose faces are parallel translations of the independent set polytopes of the minors of \$\rho\$. 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 \$\rho\$. 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 \$\mathcal{C}\$, we can define another class: the class of \$k\$-polymatroids whose \$k\$-natural matroids are in \$\mathcal{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 \geq 3\$.
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 \$\rho\$ completely determine the bounds on \$\rho\$. 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.
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.
Note: This talk begins with a pre-seminar (aimed at graduate students) at 3:30–4:00. The main talk starts at 4:10.
Join Zoom Meeting: https://washington.zoom.us/j/
Meeting ID: 915 4733 5974