Back to search

Cornell University

Dissecting an integer polymatroid

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Mathematics
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Mathematics
Grantor
Cornell University
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Young, Fiona
Chair dc:contributor.chair
  • Swartz, Edward
Committee members dc:contributor.committeemember
  • Meszaros, Karola
  • Aguiar, Marcelo

Subjects

dc:subject × 6

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16575522
Dc Identifier Other
ProQuest Submission ID: 14298
ProQuest Publication ID: 31243352

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Young, Fiona. Dissecting an integer polymatroid. Doctor of Philosophy thesis, Cornell University, 2024. https://hdl.handle.net/1813/116042