Politopo matroide

En matemáticas, un politopo matroide , también llamado politopo base matroide (o politopo matroide base ) para distinguirlo de otros politopos derivados de un matroide, es un politopo construido a través de las bases de un matroide . Dado un matroide , el politopo matroide es la envoltura convexa de los vectores indicadores de las bases de . ${\estilo de visualización M}$$Estilo de visualización P_ {M}}$${\estilo de visualización M}$

Sea un matroide sobre elementos. Dada una base de , el vector indicador de es ${\estilo de visualización M}$${\estilo de visualización n}$${\displaystyle B\subseteq \{1,\puntos ,n\}}$${\estilo de visualización M}$${\estilo de visualización B}$

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

donde es el vector unitario estándar en . El politopo matroide es la envoltura convexa del conjunto ${\displaystyle \mathbf {e} _ {i}}$${\estilo de visualización i}$${\displaystyle \mathbb {R} ^{n}}$ $Estilo de visualización P_ {M}}$

${\displaystyle \{\mathbf {e} _{B}\mid B{\text{ es una base de }}M\}\subseteq \mathbb {R} ^{n}.}$

• Sea el matroide de rango 2 sobre 4 elementos con bases${\estilo de visualización M}$

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

Es decir, todos los subconjuntos de 2 elementos de excepto . Los vectores indicadores correspondientes de son ${\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\}\}.}$

El politopo matroide de es${\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\}\}.}$

Estos puntos forman cuatro triángulos equiláteros en el punto , por lo tanto su envoltura convexa es la pirámide cuadrada por definición.${\displaystyle \{1,1,0,0\}}$

• Sea el matroide de rango 2 sobre 4 elementos con bases que son todos subconjuntos de 2 elementos de . El politopo matroide correspondiente es el octaedro . Observe que el politopo del ejemplo anterior está contenido en .${\displaystyle N}$${\displaystyle \{1,2,3,4\}}$${\displaystyle P_{N}}$${\displaystyle P_{M}}$${\displaystyle P_{N}}$
• Si es el matroide uniforme de rango en elementos, entonces el politopo matroide es el hipersímplex . ^[1]${\displaystyle M}$${\displaystyle r}$${\displaystyle n}$${\displaystyle P_{M}}$ ${\displaystyle \Delta _{n}^{r}}$

• Un politopo matroide está contenido en el hipersímplex , donde es el rango del matroide asociado y es el tamaño del conjunto base del matroide asociado. ^[2] Además, los vértices de son un subconjunto de los vértices de .${\displaystyle \Delta _{n}^{r}}$${\displaystyle r}$${\displaystyle n}$${\displaystyle P_{M}}$${\displaystyle \Delta _{n}^{r}}$
• Cada arista de un politopo matroide es una traducción paralela de para algunos , el conjunto base del matroide asociado. En otras palabras, las aristas de corresponden exactamente a los pares de bases que satisfacen la propiedad de intercambio de bases : para algunos ^[2] Debido a esta propiedad, cada longitud de arista es la raíz cuadrada de dos . De manera más general, las familias de conjuntos para las cuales la envoltura convexa de vectores indicadores tiene longitudes de arista uno o la raíz cuadrada de dos son exactamente los delta-matroides .${\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.}$
• Los politopos matroides son miembros de la familia de permutohedros generalizados . ^[3]
• Sea la función de rango de un matroide . El politopo matroide se puede escribir de forma única como una suma de Minkowski con signo de simples : ^[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}}$

donde es el conjunto fundamental del matroide y es el invariante beta con signo de : ${\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\}}$

El politopo de independencia matroide o politopo matroide de independencia es la envoltura convexa del conjunto

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

El politopo matroide (base) es una cara del politopo matroide de independencia. Dado el rango de un matroide , el politopo matroide de independencia es igual al polimatroide determinado por . ${\displaystyle \psi }$${\displaystyle M}$${\displaystyle \psi }$

El politopo matroide bandera es otro politopo construido a partir de las bases de los matroides. Una bandera es una secuencia estrictamente creciente ${\displaystyle {\mathcal {F}}}$

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

de conjuntos finitos. ^[4] Sea la cardinalidad del conjunto . Se dice que dos matroides y son concordantes si sus funciones de rango satisfacen ${\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.\,}$

Dados matroides concordantes por pares en el conjunto base con rangos , considere la colección de banderas donde es una base del matroide y . Tal colección de banderas es un matroide de banderas . Los matroides se denominan constituyentes de . Para cada bandera en un matroide de banderas , sea la suma de los vectores indicadores de cada base en${\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}}.\,}$

Dado un matroide de bandera , el politopo del matroide de bandera es la envoltura convexa del conjunto ${\displaystyle {\mathcal {F}}}$ ${\displaystyle P_{\mathcal {F}}}$

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

Un politopo matroide de bandera se puede escribir como una suma de Minkowski de los politopos matroides (base) de los matroides constituyentes: ^[4]

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