マトロイド多面体

数学において、マトロイド多面体 は、マトロイドから派生した他の多面体と区別するためにマトロイド基底多面体(または基底マトロイド多面体) とも呼ばれ、マトロイドの基底を介して構築される多面体です。マトロイド が与えられた場合、マトロイド多面体はの基底の指示ベクトルの凸包です。 ${\displaystyle M}$${\displaystyle P_{M}}$${\displaystyle M}$

を要素上のマトロイドとする。の基底が与えられたとき、 の指示ベクトルは ${\displaystyle M}$${\displaystyle n}$${\displaystyle B\subseteq \{1,\dots ,n\}}$${\displaystyle M}$${\displaystyle B}$

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

ここでは の標準番目の単位ベクトルです。マトロイド多面体は集合の 凸包です。${\displaystyle \mathbf {e} _{i}}$${\displaystyle i}$${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle P_{M}}$

${\displaystyle \{\mathbf {e} _{B}\mid B{\text{ は }}M\}\subseteq \mathbb {R} ^{n} の基底です。}$

• を4つの要素を持つ2階のマトロイドとし、基底は${\displaystyle M}$

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

つまり、 を除くのすべての2要素部分集合である 。 の対応する指示ベクトルは${\displaystyle \{1,2,3,4\}}$${\displaystyle \{3,4\}}$${\displaystyle {\mathcal {B}}(M)}$

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

のマトロイド多面体は${\displaystyle M}$

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

これらの点は点で4 つの正三角形を形成するため、定義によりその凸包は四角錐になります。${\displaystyle \{1,1,0,0\}}$

• を の 2 要素部分集合である基底を持つ 4 要素上の階数 2 のマトロイドとします。対応するマトロイド多面体は八面体です。前の例の多面体は に含まれていることに注意してください。${\displaystyle N}$${\displaystyle \{1,2,3,4\}}$${\displaystyle P_{N}}$${\displaystyle P_{M}}$${\displaystyle P_{N}}$
• が元上の階数の均一マトロイドである場合、マトロイド多面体は超単体である。^[1]${\displaystyle M}$${\displaystyle r}$${\displaystyle n}$${\displaystyle P_{M}}$ ${\displaystyle \Delta _{n}^{r}}$

• マトロイド多面体は超単体 に含まれ、ここで は関連するマトロイドの階数、 は関連するマトロイドの基底集合のサイズです。^[2] さらに、 の頂点はの頂点のサブセットです。${\displaystyle \Delta _{n}^{r}}$${\displaystyle r}$${\displaystyle n}$${\displaystyle P_{M}}$${\displaystyle \Delta _{n}^{r}}$
• マトロイド多面体のすべての辺は、関連するマトロイドの基底集合である に対して、の平行移動です。言い換えると、 の辺は、基底交換特性 を満たす基底のペアに正確に対応します。に対して、^[2]この特性により、すべての辺の長さは2 の平方根です。より一般的には、指示ベクトルの凸包の辺の長さが 1 または 2 の平方根である集合の族は、まさにデルタマトロイドです。${\displaystyle P_{M}}$${\displaystyle e_{i}-e_{j}}$${\displaystyle i,j\in E}$${\displaystyle P_{M}}$${\displaystyle B,B'}$${\displaystyle B'=B\setminus {i\cup j}}$${\displaystyle i,j\in E.}$
• マトロイド多面体は一般化されたパームトヘドラファミリーのメンバーである。^[3]
• をマトロイドのランク関数とする 。マトロイド多面体は単体の符号付きミンコフスキー和として一意に表すことができる：^[3]${\displaystyle r:2^{E}\rightarrow \mathbb {Z} }$${\displaystyle M}$${\displaystyle P_{M}}$

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

ここで はマトロイドの基底集合であり、は の符号付きベータ不変量です。 ${\displaystyle E}$${\displaystyle M}$${\displaystyle \beta (M)}$${\displaystyle M}$

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

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

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

マトロイド独立多面体または独立マトロイド多面体は、集合の凸包である。

${\displaystyle \{\,\mathbf {e} _{I}\mid I{\text{ is an independent set of }}M\,\}\subseteq \mathbb {R} ^{n}.}$

(基底)マトロイド多面体は、独立マトロイド多面体の面です。マトロイドの階数 が与えられると、独立マトロイド多面体は、によって決定される多マトロイドに等しくなります。 ${\displaystyle \psi }$${\displaystyle M}$${\displaystyle \psi }$

旗マトロイド多面体は、マトロイドの基底から構成される別の多面体である。旗は 、厳密に増加するシーケンスである。 ${\displaystyle {\mathcal {F}}}$

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

有限集合の集合である。^{[4] を}集合の濃度とする。2つのマトロイドとが一致するとは、それらのランク関数が ${\displaystyle k_{i}}$${\displaystyle F_{i}}$${\displaystyle M}$${\displaystyle N}$

${\displaystyle r_{M}(Y)-r_{M}(X)\leq r_{N}(Y)-r_{N}(X){\text{ for all }}X\subset Y\subseteq E.\,}$

階数 の基底集合上の2 対の一致するマトロイドが与えられたとき、 がマトロイドの基底であり である旗の集合を考えます。 このような旗の集合は旗マトロイドです。マトロイドはの構成要素と呼ばれます。旗マトロイド の各旗について、の各基底の指示ベクトルの合計を とします。${\displaystyle M_{1},\dots ,M_{m}}$${\displaystyle E}$${\displaystyle r_{1}<\cdots <r_{m}}$${\displaystyle (B_{1},\dots ,B_{m})}$${\displaystyle B_{i}}$${\displaystyle M_{i}}$${\displaystyle B_{1}\subset \cdots \subset B_{m}}$ ${\displaystyle {\mathcal {F}}}$${\displaystyle M_{1},\dots ,M_{m}}$${\displaystyle {\mathcal {F}}}$${\displaystyle B=(B_{1},\dots ,B_{m})}$${\displaystyle {\mathcal {F}}}$${\displaystyle v_{B}}$${\displaystyle B}$

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

旗マトロイドが与えられたとき、旗マトロイド多面体は集合の凸包である。 ${\displaystyle {\mathcal {F}}}$ ${\displaystyle P_{\mathcal {F}}}$

${\displaystyle \{v_{B}\mid B{\text{ is a flag in }}{\mathcal {F}}\}.}$

旗マトロイド多面体は、構成マトロイドの（基底）マトロイド多面体のミンコフスキー和として表される：^[4]

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