Matroid politop - Matroid polytope

Matematikte bir matroid politop, ayrıca denir matroid temelli politop (veya temel matroid politop) bir matroidden türetilen diğer politoplardan ayırt etmek için, politop temelleri üzerinden inşa edilmiş matroid. Bir matroid verildiğinde ${ displaystyle M}$matroid politop ${ displaystyle P_ {M}}$ ... dışbükey örtü of gösterge vektörleri temellerinin ${ displaystyle M}$.

Tanım

İzin Vermek ${ displaystyle M}$ olmak matroid açık ${ displaystyle n}$ elementler. Bir temel verildiğinde ${ displaystyle B subseteq {1, noktalar, n }}$ nın-nin ${ displaystyle M}$, gösterge vektörü nın-nin ${ displaystyle B}$ dır-dir

${ displaystyle mathbf {e} _ {B}: = toplam _ {i B} mathbf {e} _ {i},}$

nerede ${ displaystyle mathbf {e} _ {i}}$ standarttır ${ displaystyle i}$inci birim vektör ${ displaystyle mathbb {R} ^ {n}}$. matroid politop ${ displaystyle P_ {M}}$ ... dışbükey örtü setin

${ displaystyle { mathbf {e} _ {B} mid B { text {}} M } subseteq mathbb {R} ^ {n} 'nin temelidir.}$

Örnekler

Kare piramit

Oktahedron

• İzin Vermek ${ displaystyle M}$ temelleri olan 4 elementte 2. sıra matroid olun

${ displaystyle { mathcal {B}} (M) = { {1,2 }, {1,3 }, {1,4 }, {2,3 }, { 2,4 } }.}$

Yani, tüm 2 öğeli alt kümeleri ${ displaystyle {1,2,3,4 }}$ dışında ${ displaystyle {3,4 }}$. Karşılık gelen gösterge vektörleri ${ displaystyle { mathcal {B}} (M)}$ vardır

${ displaystyle { {1,1,0,0 }, {1,0,1,0 }, {1,0,0,1 }, {0,1,1,0 }, {0,1,0,1 } }.}$

Matroid politopu ${ displaystyle M}$ dır-dir

${ displaystyle P_ {M} = { text {dönüşüm}} { {1,1,0,0 }, {1,0,1,0 }, {1,0,0,1 }, {0,1,1,0 }, {0,1,0,1 } }.}$

Bu noktalar dört eşkenar üçgenler noktada ${ displaystyle {1,1,0,0 }}$bu nedenle dışbükey gövdesi kare piramit tanım olarak.

• İzin Vermek ${ displaystyle N}$ 4 element üzerinde 2. sıra matroid olmak herşey 2 öğeli alt kümeleri ${ displaystyle {1,2,3,4 }}$. Karşılık gelen matroid politop ${ displaystyle P_ {N}}$ ... sekiz yüzlü. Politopun ${ displaystyle P_ {M}}$ önceki örnekte yer almaktadır ${ displaystyle P_ {N}}$.
• Eğer ${ displaystyle M}$ ... tek tip matroid rütbe ${ displaystyle r}$ açık ${ displaystyle n}$ öğeler, ardından matroid polytope ${ displaystyle P_ {M}}$ ... hipersimplex ${ displaystyle Delta _ {n} ^ {r}}$.^[1]

Özellikleri

• Bir matroid politopu, hipersimplex ${ displaystyle Delta _ {n} ^ {r}}$, nerede ${ displaystyle r}$ ilişkili matroidin sıralamasıdır ve ${ displaystyle n}$ ilişkili matroidin zemin setinin boyutudur.^[2] Dahası, köşeleri ${ displaystyle P_ {M}}$ köşelerinin bir alt kümesidir ${ displaystyle Delta _ {n} ^ {r}}$.
• Bir matroid politopun her kenarı ${ displaystyle P_ {M}}$ paralel bir çeviridir ${ displaystyle e_ {i} -e_ {j}}$ bazı ${ displaystyle i, j E’de}$, ilişkili matroidin zemin seti. Başka bir deyişle, kenarları ${ displaystyle P_ {M}}$ baz çiftlerine tam olarak karşılık gelir ${ displaystyle B, B '}$ tatmin eden temel değişim mülkü: ${ displaystyle B '= B setminus {i cup j}}$ bazı ${ displaystyle i, j , E.}$^[2] Bu özellik nedeniyle, her kenar uzunluğu ikinin karekökü. Daha genel olarak, gösterge vektörlerinin dışbükey gövdesinin kenar uzunluklarının bir veya ikinin kareköküne sahip olduğu kümelerin aileleri tam olarak delta-matroidler.
• Matroid politoplar şu ailenin üyeleridir: genelleştirilmiş permutohedra.^[3]
• İzin Vermek ${ displaystyle r: 2 ^ {E} rightarrow mathbb {Z}}$ bir matroidin rank fonksiyonu olmak ${ displaystyle M}$. Matroid politop ${ displaystyle P_ {M}}$ imzalı olarak benzersiz bir şekilde yazılabilir Minkowski toplamı nın-nin basitler:^[3]

${ displaystyle P_ {M} = sum _ {A subseteq E} { tilde { beta}} (M / A) Delta _ {E-A}}$

nerede ${ displaystyle E}$ matroidin temelidir ${ displaystyle M}$ ve ${ displaystyle beta (M)}$ imzalı beta değişmez ${ displaystyle M}$:

${ displaystyle { tilde { beta}} (M) = (- 1) ^ {r (M) +1} beta (M),}$

${ displaystyle beta (M) = (- 1) ^ {r (M)} toplamı _ {X subseteq E} (- 1) ^ {| X |} r (X).}$

${ displaystyle P_ {M}: = left {{ textbf {x}} in mathbb {R} _ {+} ^ {E} ~ | ~ sum _ {e U} { textbf {x}} (e) leq r (U), forall U subseteq E right }}$

İlgili politoplar

Bağımsızlık matroid politopu

matroid bağımsızlık politopu veya bağımsızlık matroid politopu setin dışbükey gövdesi

${ displaystyle {, mathbf {e} _ {I} mid I { text {bağımsız bir}} M , } subseteq mathbb {R} ^ {n} kümesidir.}$

(Temel) matroid politop, bağımsız matroid politopunun bir yüzüdür. Verilen sıra ${ displaystyle psi}$ bir matroidin ${ displaystyle M}$bağımsızlık matroid politopu eşittir polimatroid tarafından karar verildi ${ displaystyle psi}$.

Matroid polytope ile ilgili şikayetler

Bayrak matroid politopu, matroidlerin tabanlarından oluşturulmuş başka bir politoptur. Bir bayrak ${ displaystyle { mathcal {F}}}$ kesinlikle artan bir dizidir

${ displaystyle F ^ {1} alt küme F ^ {2} alt küme cdots alt küme F ^ {m} ,}$

sonlu kümeler.^[4] İzin Vermek ${ displaystyle k_ {i}}$ setin asli olmak ${ displaystyle F_ {i}}$. İki matroid ${ displaystyle M}$ ve ${ displaystyle N}$ Olduğu söyleniyor uyumlu rank işlevleri tatmin ederse

${ displaystyle r_ {M} (Y) -r_ {M} (X) leq r_ {N} (Y) -r_ {N} (X) { text {tümü için}} X subset Y subseteq E . ,}$

İkili uyumlu matroidler verilir ${ displaystyle M_ {1}, noktalar, M_ {m}}$ yer setinde ${ displaystyle E}$ saflarla ${ displaystyle r_ {1} < cdots$, bayrakların koleksiyonunu düşünün ${ displaystyle (B_ {1}, noktalar, B_ {m})}$ nerede ${ displaystyle B_ {i}}$ matroidin temelidir ${ displaystyle M_ {i}}$ ve ${ displaystyle B_ {1} alt küme cdots alt küme B_ {m}}$. Böyle bir bayrak koleksiyonu, bayrak matroid ${ displaystyle { mathcal {F}}}$. Matroidler ${ displaystyle M_ {1}, noktalar, M_ {m}}$ denir bileşenleri nın-nin ${ displaystyle { mathcal {F}}}$Her bayrak için ${ displaystyle B = (B_ {1}, noktalar, B_ {m})}$ bayrak matroidinde ${ displaystyle { mathcal {F}}}$, İzin Vermek ${ displaystyle v_ {B}}$ her bir temele ait gösterge vektörlerinin toplamı ${ displaystyle B}$

${ displaystyle v_ {B} = v_ {B_ {1}} + cdots + v_ {B_ {m}}. ,}$

Bir bayrak matroidi verildiğinde ${ displaystyle { mathcal {F}}}$, bayrak matroid polytope ${ displaystyle P _ { mathcal {F}}}$ setin dışbükey gövdesi

${ displaystyle {v_ {B} mid B { text {bir işarettir}} { mathcal {F}} }.}$

Bayrak matroid politopu, kurucu matroidlerin (temel) matroid politoplarının Minkowski toplamı olarak yazılabilir:^[4]

${ displaystyle P _ { mathcal {F}} = P_ {M_ {1}} + cdots + P_ {M_ {k}}. ,}$

Referanslar