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

Выпуклая оболочка индикаторных векторов базисов

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

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

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

Примеры

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

Октаэдр

• Пусть будет матроидом ранга 2 на 4 элементах с базами ${\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\}\}.}$

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

Ссылки

1. Грётшель, Мартин (2004), «Мощностные однородные системы множеств, циклы в матроидах и связанные многогранники», The Sharpest Cut: The Impact of Manfred Padberg and His Work , MPS/SIAM Ser. Optim., SIAM, Филадельфия, Пенсильвания, стр. 99–120, MR  2077557. См., в частности, замечания после Предложения 8.20 на стр. 114.
2. Гельфанд, ИМ; Горески, РМ; Макферсон, РД; Серганова, ВВ (1987). «Комбинаторные геометрии, выпуклые многогранники и клетки Шуберта». Успехи математики . 63 (3): 301–316. doi : 10.1016/0001-8708(87)90059-4 .
3. Ardila, Federico; Benedetti, Carolina; Doker, Jeffrey (2010). «Матроидные многогранники и их объемы». Дискретная и вычислительная геометрия . 43 (4): 841–854. arXiv : 0810.3947 . doi :10.1007/s00454-009-9232-9.
4. Боровик, Александр В.; Гельфанд, И. М.; Уайт, Нил (2013). «Матроиды Коксетера». Прогресс в математике . 216. doi :10.1007/978-1-4612-2066-4. ISBN 978-1-4612-7400-1.