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