词条 | Matroid polytope |
释义 |
In mathematics, a matroid polytope, also called a matroid basis polytope (or basis matroid polytope) to distinguish it from other polytopes derived from a matroid, is a polytope constructed via the bases of a matroid. Given a matroid , the matroid polytope is the convex hull of the indicator vectors of the bases of . DefinitionLet be a matroid on elements. Given a basis of , the indicator vector of is where is the standard th unit vector in . The matroid polytope is the convex hull of the set Examples
That is, all 2-element subsets of except . The corresponding indicator vectors of are The matroid polytope of is These points form four equilateral triangles at point , therefore its convex hull is the square pyramid by definition.
Properties
where is the ground set of the matroid and is the signed beta invariant of : Related polytopesIndependence matroid polytopeThe matroid independence polytope or independence matroid polytope is the convex hull of the set The (basis) matroid polytope is a face of the independence matroid polytope. Given the rank of a matroid , the independence matroid polytope is equal to the polymatroid determined by . Flag matroid polytopeThe flag matroid polytope is another polytope constructed from the bases of matroids. A flag is a strictly increasing sequence of finite sets.[4] Let be the cardinality of the set . Two matroids and are said to be concordant if their rank functions satisfy Given pairwise concordant matroids on the ground set with ranks , consider the collection of flags where is a basis of the matroid and . Such a collection of flags is a flag matroid . The matroids are called the constituents of . For each flag in a flag matroid , let be the sum of the indicator vectors of each basis in Given a flag matroid , the flag matroid polytope is the convex hull of the set A flag matroid polytope can be written as a Minkowski sum of the (basis) matroid polytopes of the constituent matroids:[4] References1. ^{{citation | last = Grötschel | first = Martin | authorlink = Martin Grötschel | contribution = Cardinality homogeneous set systems, cycles in matroids, and associated polytopes | mr = 2077557 | pages = 99–120 | publisher = SIAM, Philadelphia, PA | series = MPS/SIAM Ser. Optim. | title = The Sharpest Cut: The Impact of Manfred Padberg and His Work | year = 2004}}. See in particular the remarks following Prop. 8.20 on [https://books.google.com/books?id=iXJxerJLyTEC&oi=fnd&pg=PA114 p. 114]. 2. ^1 {{cite journal|last1=Gelfand |first1=I.M.|last2=Goresky |first2=R.M. |last3=MacPherson |first3=R.D. |last4=Serganova |first4=V.V.|author4-link= Vera Serganova |year=1987|title=Combinatorial geometries, convex polyhedra, and Schubert cells|journal=Advances in Mathematics|volume=63|issue=3|pages=301–316|doi=10.1016/0001-8708(87)90059-4 }} 3. ^1 {{cite journal |first1=Federico |last1=Ardila |first2=Carolina|last2=Benedetti|first3=Jeffrey|last3=Doker |title=Matroid polytopes and their volumes |journal=Discrete and Computational Geometry |volume=43 |issue=4 |pages=841–854 |year=2010 |arxiv=0810.3947 |doi=10.1007/s00454-009-9232-9}} 4. ^1 {{cite journal|last1=Borovik |first1=Alexandre V.|last2= Gelfand |first2=I.M. |last3=White |first3=Neil |title=Coxeter Matroids|journal=Progress in Mathematics|volume=216 |year=2013 |doi=10.1007/978-1-4612-2066-4 }} 2 : Matroid theory|Polytopes |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。