Matroid polytop

Inom matematik är en matroidpolytop , även kallad en matroidbaspolytop (eller basismatroidpolytop ) för att skilja den från andra polytoper som härrör från en matroid, en polytop som konstrueras via baserna av en matroid . Givet en matroid $M$ , är matroidpolytopen $P_{M}$ det konvexa skrovet för indikatorvektorerna för baserna i $\displaystyle M}$ .

Definition

Låt $M$ vara en matroid på $n$ element. Givet en bas $B\subseteq \{1,\dots ,n\}$ av M $\displaystyle M}$ är indikatorvektorn för $B$

$\mathbf {e} _{B}:=\sum _{i\in B}\mathbf {e} _{i},$

där $\mathbf {e} _{i}$ är standard ${\displaystyle i}:$ e enhetsvektorn i $\mathbb {R} ^{n}$ . Den matroida polytopen $\displaystyle P_{M}}$ är uppsättningens konvexa skrov

$\{\mathbf {e} _{B}\mid B{\text{ är en grund för }}M\}\subseteq \mathbb {R} ^{n}.$

Exempel

Fyrkantig pyramid

Oktaeder

• Låt $M$ vara rank 2 matroid på 4 element med baser

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

Det vill säga alla 2-elements delmängder av $\{1,2,3,4\}$ utom ${\ displaystil \{3,4\}}$ . Motsvarande indikatorvektorer för ${\mathcal {B}}(M)$

$\{\{1,1,0,0\},\{1,0,1,0\},\{1,0,0,1\},\{0,1,1,0 \},\{0,1,0,1\}\}.$

{

$P_{M}={\text{conv}}\{\{1,1,0,0\},\{1,0,1,0\},\{1,0,0,1 \},\{0,1,1,0\},\{0,1,0,1\}\}.$

för $M$ är

Dessa punkter bildar fyra liksidiga trianglar vid punkten $\{ 1,1,0,0\}$ , därför är dess konvexa skrov den fyrkantiga pyramiden per definition.

• Låt $N$ vara rank 2 matroiden på 4 element med baser som alla är 2-elements delmängder av $\{1,2,3,4\}$ . Den motsvarande matroidpolytopen $\displaystyle P_{N}}$ är oktaedern . Observera att polytopen $P_{M}$ föregående exempel finns i $P_{N$ .
• Om $M$ är den enhetliga matroiden av rang $r$ på ${\displaystyle n} element, då$ är matroidpolytopen $P_{M}$ hypersimplex $\ displaystyle \Delta _{n}^{r}}$ .

Egenskaper

• En matroidpolytop finns i hypersimplexet Δ $\displaystyle \Delta _{n}^{r}}$ , där $r$ är rangen för den associerade matroiden och $n$ är storleken av jorduppsättningen för den tillhörande matroiden. Dessutom är hörnen för $P_{M}$ delmängd av hörnen för $\Delta _{n}^{r}$ .
• Varje kant av en matroidpolytop $}}$ är en parallell översättning av $e_{i}-e_{j}$ för vissa $i ,j\in E$ , jorduppsättningen för den associerade matroiden. Med andra ord, kanterna på $}}$ motsvarar exakt de par av baser $B,B'$ som uppfyller basutbytesegenskapen : $B'=B\setminus {i\cup j}$ för vissa $i,j\in E.$ På grund av denna egenskap är varje kantlängd kvadratroten ur två . Mer allmänt är familjerna av uppsättningar för vilka det konvexa skrovet av indikatorvektorer har kantlängder en eller kvadratroten ur två exakt delta-matroiderna .
• Matroidpolytoper är medlemmar av familjen av generaliserade permutoedrar .
• Låt $r:2^{E}\rightarrow \mathbb {Z}$ vara rangfunktionen för en matroid $M$ . Matroidpolytopen $P_{M}$ kan skrivas unikt som en signerad summa av förenklingar :

$P_{M}=\summa _{A\subseteq E}{\tilde {\beta }}(M/A)\Delta _{EA}$

där $E$ är grundmängden för matroiden $M$ och $\beta (M)$ är den förtecknade beta-invarianten av $M$ :

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

${\displaystyle \beta (M)=(-1)^{r(M)}\sum _{X\subseteq E}(-1)^{|X|}r(X).} P$

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

Besläktade polytoper

Självständighet matroid polytop

Den matroid oberoende polytopen eller independence matroid polytopen är det konvexa skrovet på setet

$\{\,\mathbf {e} _{I}\mid I{\text{ är en oberoende uppsättning av }}M\,\}\subseteq \mathbb {R} ^{n}.$

(Basis) matroidpolytopen är ett ansikte av den oberoende matroidpolytopen. Givet rangordningen $\psi$ för en matroid $M$ , är självständighetsmatroidpolytopen lika med polymatroiden som bestäms av $\psi$ .

Flagga matroid polytop

Flaggamatroidpolytopen är en annan polytop konstruerad från baserna av matroider. En flagga ${\mathcal {F}}$ är en strikt ökande sekvens

$F^{1}\subset F^{2}\subset \cdots \subset F^{m}\,$

av ändliga mängder. Låt $k_{i}$ vara kardinaliteten för mängden $F_{i}$ . Två matroider $M$ och $N$ sägs vara överensstämmande om deras rangfunktioner uppfyller

$r_{M}(Y)-r_{M}(X)\leq r_{N}(Y)-r_{N}(X){\text{ för alla }}X\subset Y\subseteq E .\,$

Givet parvisa konkordanta matroider $M_{1},\dots ,M_{m}$ på marken set $E$ med rangorden $r_ {1}<\cdots <r_{m}$ , betrakta samlingen av flaggor $(B_{1},\dots ,B_{m})$ där ${\ displaystyle B_{i}}$ är en bas för matroiden $M_{i}$ och $B_{1}\subset \cdots \subset B_{m}$ . En sådan samling av flaggor är en flagga matroid ${\mathcal {F}}$ . Matroiderna $M_{1},\dots ,M_{m}$ kallas beståndsdelarna av F $\displaystyle {\mathcal {F}}}$ . För varje flagga $B=(B_{1},\dots ,B_{m})$ i en flaggmatroid ${\mathcal {F}}$ , låt $v_{B}$ vara summan av indikatorvektorerna för varje bas i $B$

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

Givet en flaggmatroid $}} är$ } flaggmatroidpolytopen $P_{\mathcal {F}}$ det konvexa skrovet i uppsättningen

$\{v_{B}\mid B{\text{ är en flagga i }}{\mathcal {F}}\}.$

En flagga matroid polytop kan skrivas som en Minkowski summa av (bas) matroid polytoper av de ingående matroiderna:

$P_{\mathcal {F}}=P_{M_{1}}+\cdots +P_{M_{k}}.\,$