Матроидный многогранник

В математике многогранник матроида , также называемый многогранником базиса матроида (или многогранником базиса матроида ), чтобы отличить его от других многогранников, производных от матроида, представляет собой многогранник, построенный через основания матроида . Учитывая матроид $M$, матроидный многогранник $P_{M}$ – выпуклая оболочка индикаторных векторов оснований $M$.

Определение

Позволять $M$ быть матроидом на $n$ элементы. Учитывая основу $B\subseteq \{1,\dots ,n\}$ из $M$, индикаторный вектор $B$ является

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

где $\mathbf {e} _{i}$ это стандарт $i$-й единичный вектор в $\mathbb {R} ^{n}$. Матроидный многогранник $P_{M}$ является выпуклой оболочкой множества

$\{\mathbf {e} _{B}\mid B{\text{ is a basis of }}M\}\subseteq \mathbb {R} ^{n}.$

Примеры

Квадратная пирамида

Октаэдр

• Позволять $M$ быть матроидом 2 ранга на 4 элементах с базами

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

То есть все двухэлементные подмножества $\{1,2,3,4\}$ кроме $\{3,4\}$. Соответствующие индикаторные векторы ${\mathcal {B}}(M)$ являются

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

Матроидный многогранник $M$ является

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

Эти точки образуют четыре равносторонних треугольника в точке $\{1,1,0,0\}$, поэтому ее выпуклая оболочка по определению является квадратной пирамидой .

• Позволять $N$ — матроид ранга 2 на 4 элементах с базами, которые все являются 2-элементными подмножествами $\{1,2,3,4\}$. Соответствующий матроидный многогранник $P_{N}$ это октаэдр . Заметим, что многогранник $P_{M}$ из предыдущего примера содержится в $P_{N}$.
• Если $M$ – это однородный матроид ранга $r$ на $n$ элементы, то матроидный многогранник $P_{M}$ это гиперсимплекс $\Delta _{n}^{r}$.

Характеристики

• Матроидный многогранник содержится в гиперсимплексе $\Delta _{n}^{r}$, где $r$ - ранг соответствующего матроида и $n$ - размер основного набора соответствующего матроида. Более того, вершины $P_{M}$ являются подмножеством вершин $\Delta _{n}^{r}$.
• Каждое ребро матроидного многогранника $P_{M}$ это параллельный перевод $e_{i}-e_{j}$ для некоторых $i,j\in E$, основной набор соответствующего матроида. Другими словами, края $P_{M}$ точно соответствуют парам оснований $B,B'$ которые удовлетворяют базовому свойству обмена : $B'=B\setminus {i\cup j}$ для некоторых $i,j\in E.$ Благодаря этому свойству каждая длина ребра равна квадратному корню из двух . В более общем смысле, семейства множеств, для которых выпуклая оболочка индикаторных векторов имеет длину ребра один или квадратный корень из двух, являются в точности дельта-матроидами .
• Матроидные многогранники являются членами семейства обобщенных пермутоэдров .
• Позволять $r:2^{E}\rightarrow \mathbb {Z}$ быть ранговой функцией матроида $M$. Матроидный многогранник $P_{M}$ однозначно записать в виде Минковского суммы симплексов можно со знаком :

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

где $E$ это основной набор матроида $M$ и $\beta (M)$ является знаковым бета-инвариантом $M$:

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

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

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

Связанные многогранники

Матроидный многогранник независимости

или Многогранник независимости матроида многогранник матроида независимости - это выпуклая оболочка множества.

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

(Базисный) матроидный многогранник является гранью матроидного многогранника независимости. Учитывая ранг $\psi$ матроида $M$многогранник матроида независимости равен полиматроиду, определяемому формулой $\psi$.

Пометить матроидный многогранник

Флаговый многогранник матроида — это еще один многогранник, построенный из оснований матроидов. Флаг ​ ${\mathcal {F}}$ является строго возрастающей последовательностью

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

конечных множеств. Позволять $k_{i}$ быть мощность множества $F_{i}$. Два матроида $M$ и $N$ называются согласованными, если их ранговые функции удовлетворяют

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

Даны попарно согласованные матроиды. $M_{1},\dots ,M_{m}$ на земле установлен $E$ со званиями $r_{1}<\cdots <r_{m}$, рассмотрим коллекцию флагов $(B_{1},\dots ,B_{m})$ где $B_{i}$ это основа матроида $M_{i}$ и $B_{1}\subset \cdots \subset B_{m}$. Такая коллекция флагов и есть флаговый матроид. ${\mathcal {F}}$. Матроиды $M_{1},\dots ,M_{m}$ называются составляющими ​ ${\mathcal {F}}$.Для каждого флага $B=(B_{1},\dots ,B_{m})$ во флаговом матроиде ${\mathcal {F}}$, позволять $v_{B}$ — сумма индикаторных векторов каждого базиса в $B$

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

Учитывая флаг матроида ${\mathcal {F}}$, флаговый многогранник матроида $P_{\mathcal {F}}$ является выпуклой оболочкой множества

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

Многогранник флагового матроида можно записать как сумму Минковского (базисных) матроидных многогранников составляющих матроидов:

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