MARC

 008250224s2024        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[S.l.]▼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이  자료의  원문은  한국교육학술정보원에서  제공합니다.

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서