서브메뉴
검색
Dissecting an Integer Polymatroid
Dissecting an Integer Polymatroid
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20250211151922
- ISBN
- 9798382842264
- DDC
- 510
- 저자명
- Young, Fiona.
- 서명/저자
- Dissecting an Integer Polymatroid
- 발행사항
- [Sl] : Cornell University, 2024
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2024
- 형태사항
- 119 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 85-12, Section: B.
- 주기사항
- Advisor: Swartz, Edward B.
- 학위논문주기
- Thesis (Ph.D.)--Cornell University, 2024.
- 초록/해제
- 요약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 U2,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 U2,b- and Ub−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 U2,b- and Ub−2,b-minors.Finally, we investigate a further generalization to the class of k-polymatroids whose k-natural matroids lack both Ua,b- and Ub−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.
- 일반주제명
- Mathematics
- 일반주제명
- Applied mathematics
- 키워드
- Combinatorics
- 키워드
- Excluded minors
- 키워드
- Matroid
- 키워드
- Polymatroid
- 기타저자
- Cornell University Mathematics
- 기본자료저록
- Dissertations Abstracts International. 85-12B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008250123s2024 us c eng d■001000017162127
■00520250211151922
■006m o d
■007cr#unu||||||||
■020 ▼a9798382842264
■035 ▼a(MiAaPQ)AAI31243352
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a510
■1001 ▼aYoung, Fiona.▼0(orcid)0000-0001-7166-585X
■24510▼aDissecting an Integer Polymatroid
■260 ▼a[Sl]▼bCornell University▼c2024
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2024
■300 ▼a119 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 85-12, Section: B.
■500 ▼aAdvisor: Swartz, Edward B.
■5021 ▼aThesis (Ph.D.)--Cornell University, 2024.
■520 ▼aOne 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 U2,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 U2,b- and Ub−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 U2,b- and Ub−2,b-minors.Finally, we investigate a further generalization to the class of k-polymatroids whose k-natural matroids lack both Ua,b- and Ub−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.
■590 ▼aSchool code: 0058.
■650 4▼aMathematics
■650 4▼aApplied mathematics
■653 ▼aCombinatorics
■653 ▼aDiscrete geometry
■653 ▼aExcluded minors
■653 ▼aGeneralized permutohedra
■653 ▼aMatroid
■653 ▼aPolymatroid
■690 ▼a0405
■690 ▼a0364
■71020▼aCornell University▼bMathematics.
■7730 ▼tDissertations Abstracts International▼g85-12B.
■790 ▼a0058
■791 ▼aPh.D.
■792 ▼a2024
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17162127▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
