Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell University Graduate School
  3. Cornell Theses and Dissertations
  4. Dissecting an integer polymatroid

Dissecting an integer polymatroid

File(s)
Young_cornellgrad_0058F_14298.pdf (1.11 MB)
Permanent Link(s)
https://doi.org/10.7298/c0fy-8g57
https://hdl.handle.net/1813/116042
Collections
Cornell Theses and Dissertations
Author
Young, Fiona
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.

Description
118 pages
Date Issued
2024-05
Keywords
combinatorics
•
discrete geometry
•
excluded minors
•
generalized permutohedra
•
matroid
•
polymatroid
Committee Chair
Swartz, Edward
Committee Member
Meszaros, Karola
Aguiar, Marcelo
Degree Discipline
Mathematics
Degree Name
Ph. D., Mathematics
Degree Level
Doctor of Philosophy
Rights
Attribution 4.0 International
Rights URI
https://creativecommons.org/licenses/by/4.0/
Type
dissertation or thesis
Link(s) to Catalog Record
https://newcatalog.library.cornell.edu/catalog/16575522

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance