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

В математике матроидный многогранник , также называемый матроидным базисным многогранником (или базисным матроидным многогранником ), чтобы отличать его от других многогранников, полученных из матроида, — это многогранник, построенный с помощью базисов матроида . Для данного матроида матроидный многогранник является выпуклой оболочкой индикаторных векторов баз .${\displaystyle М}$${\displaystyle P_{M}}$${\displaystyle М}$

Пусть будет матроидом на элементах. При наличии базиса , вектор - индикатор равен${\displaystyle М}$${\displaystyle n}$${\displaystyle B\subseteq \{1,\dots ,n\}}$${\displaystyle М}$${\displaystyle Б}$

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

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

${\displaystyle \{\mathbf {e} _{B}\mid B{\text{ является базисом }}M\}\subseteq \mathbb {R} ^{n}.}$

• Пусть будет матроидом ранга 2 на 4 элементах с базами${\displaystyle М}$

${\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\}\}.}$

Эти точки образуют четыре равносторонних треугольника в точке , поэтому ее выпуклая оболочка по определению является квадратной пирамидой .${\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] Из-за этого свойства длина каждого ребра равна квадратному корню из двух . В более общем смысле, семейства множеств, для которых выпуклая оболочка векторов-индикаторов имеет длины ребер один или квадратный корень из двух, являются в точности дельта-матроидами .${\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] Пусть будет мощностью множества . Два матроида и называются согласованными, если их ранговые функции удовлетворяют${\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.\,}$

Для заданных попарно согласованных матроидов на основании множества с рангами рассмотрим набор флагов , где — базис матроида и . Такой набор флагов — флаговый матроид . Матроиды называются составляющими . Для каждого флага в флаговом матроиде пусть будет суммой индикаторных векторов каждого базиса в${\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}}.\,}$