Matroide dual

Matroide con conjuntos de bases complementados

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]} ${\displaystyle M}$ ${\displaystyle M^{\ast }}$ ${\displaystyle M}$ ${\displaystyle 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 .

Propiedades básicas

La dualidad es una involución : para todos , . ^{[1] [3] [4]} ${\displaystyle 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)}$

Menores de edad

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 }}$

Matroides autoduales

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]

Familias de matroides

Muchas familias de matroides importantes 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]

Referencias

1. Schrijver, Alexander (2003), Optimización combinatoria: poliedros y eficiencia. Vol. B: Matroides, árboles, conjuntos estables, algoritmos y combinatoria, vol. 24, Berlín: Springer-Verlag, p. 652, ISBN 3-540-44389-4, Sr.  1956925.
2. Welsh, DJA (2010), Teoría matroide, Publicaciones Courier Dover, p. 34, ISBN 9780486474397.
3. Oxley, James G. (2006), Teoría de matroides, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, págs. 69-70, ISBN 9780199202508.
4. Whitney, Hassler (1935), "Sobre las propiedades abstractas de la dependencia lineal", American Journal of Mathematics , 57 (3), The Johns Hopkins University Press: 509–533, doi :10.2307/2371182, hdl : 10338.dmlcz/100694 , JSTOR  2371182, MR  1507091. Reimpreso en Kung (1986), págs. 55-79. Véase en particular la sección 11, "Matroides duales", págs. 521-524.
5. Schrijver (2003), pág. 653.
6. Jensen, Per M.; Korte, Bernhard (1982), "Complejidad de los algoritmos de propiedades de matroides", SIAM Journal on Computing , 11 (1): 184–190, doi :10.1137/0211014, MR  0646772.
7. Whitney (1935), Sección 13, "Hiperplanos ortogonales y matroides duales".
8. Schrijver (2003), págs. 659–661; Galés (2010), págs. 222-223.
9. Oxley (2006), págs. 77 y 111.
10. Tutte, WT (1965), "Conferencias sobre matroides", Revista de investigación de la Oficina Nacional de Normas , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR  0179781.
11. Welsh, DJA (1969), "Matroides de Euler y bipartitos", Journal of Combinatorial Theory , 6 (4): 375–377, doi : 10.1016/s0021-9800(69)80033-5 , MR  0237368.
12. Harary, Frank ; Welsh, Dominic (1969), "Matroides versus grafos", The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) , Lecture Notes in Mathematics, vol. 110, Berlín: Springer, págs. 155–170, doi :10.1007/BFb0060114, ISBN 978-3-540-04629-5, Sr.  0263666.
13. Federico, Ardila (2012). "Conferencia 9 sobre matroides". YouTube .

Obras citadas

• 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.