Matroide dual

En la teoría de matroides , el dual de un matroide es otro matroide que tiene los mismos elementos que , y en el que un conjunto es independiente si y solo si tiene un conjunto base disjunto de él. ^{[1] [2] [3]}${\estilo de visualización M}$${\displaystyle M^{\ast}}$${\estilo de visualización M}$${\estilo de visualización M}$

Los duales matroides se remontan al artículo original de Hassler Whitney que define los matroides. ^[4] Ellos generalizan a los matroides las nociones de dualidad de grafos planos .

La dualidad es una involución : para todos , . ^{[1] [3] [4]}${\estilo de visualización M}$${\displaystyle (M^{\ast })^{\ast }=M}$

Una definición alternativa del matroide dual es que sus conjuntos base son los complementos de los conjuntos base de . El axioma de intercambio de bases, utilizado para definir matroides a partir de sus bases, es autocomplementario, por lo que el dual de un matroide es necesariamente un matroide. ^[3]${\displaystyle M}$

Los planos de son complementarios a los conjuntos cíclicos (uniones de circuitos) de , y viceversa. ^[3]${\displaystyle M}$${\displaystyle M^{\ast }}$

Si es la función de rango de un matroide en el conjunto base , entonces la función de rango del matroide dual es . ^{[1] [3] [4]}${\displaystyle r}$${\displaystyle M}$${\displaystyle E}$${\displaystyle r^{\ast }(S)=r(E\setminus S)+|S|-r(E)}$

Un matroide menor se forma a partir de un matroide mayor mediante dos operaciones: la restricción elimina un elemento de sin cambiar la independencia o el rango de los conjuntos restantes, y la contracción elimina de después de restar uno del rango de cada conjunto al que pertenece. Estas dos operaciones son duales: y . Por lo tanto, un menor de un dual es lo mismo que un dual de un menor. ^[5]${\displaystyle M}$${\displaystyle M\setminus x}$${\displaystyle x}$${\displaystyle M}$${\displaystyle M/x}$${\displaystyle x}$${\displaystyle M}$${\displaystyle M\setminus x=(M^{\ast }/x)^{\ast }}$${\displaystyle M/x=(M^{\ast }\setminus x)^{\ast }}$

Un matroide individual es autodual (generalizando, por ejemplo, los poliedros autoduales para los matroides gráficos) si es isomorfo a su propio dual. El isomorfismo puede, pero no es obligatorio, dejar fijos los elementos del matroide. Cualquier algoritmo que pruebe si un matroide dado es autodual, dado acceso al matroide a través de un oráculo de independencia , debe realizar un número exponencial de consultas al oráculo y, por lo tanto, no puede tomar un tiempo polinomial. ^[6]

Muchas familias importantes de matroides son autoduales, lo que significa que un matroide pertenece a la familia si y solo si su dual lo hace. Muchas otras familias de matroides se presentan en pares duales. Algunos ejemplos de este fenómeno incluyen:

• Las matroides binarias (matroides representables sobre GF(2) ), las matroides representables sobre cualquier otro campo y las matroides regulares son todas familias autoduales. ^[7]
• Los gamoides forman una familia autodual. Los gamoides estrictos son duales con respecto a los matroides transversales . ^[8]
• Los matroides uniformes y los matroides de partición son autoduales. El dual de un matroide uniforme es el matroide uniforme . ^[9]${\displaystyle U{}_{n}^{r}}$${\displaystyle U{}_{n}^{n-r}}$
• El dual de un matroide gráfico es en sí mismo gráfico si y sólo si el grafo subyacente es plano; el matroide del dual de un grafo plano es el mismo que el dual del matroide del grafo. Por lo tanto, la familia de matroides gráficas de grafos planos es autodual. ^[10]
• Entre las matroides gráficas, y más generalmente entre las matroides binarias, las matroides bipartitas (matroides en las que cada circuito es par) son duales con las matroides eulerianas (matroides que pueden dividirse en circuitos disjuntos). ^{[11] [12]}

Es un problema abierto si la familia de matroides algebraicas es auto-dual.

Si V es un espacio vectorial y V * es su complemento ortogonal , entonces el matroide lineal de V y el matroide lineal de V * son duales. Como corolario, el dual de cualquier matroide lineal es un matroide lineal. ^[13]

• Kung, Joseph PSv, ed. (1986), Un libro de consulta sobre teoría de matroides, Boston: Birkhäuser, doi :10.1007/978-1-4684-9199-9, ISBN 978-0-8176-3173-4, Sr.  0890330.