Matroide binario

Abstracción de la independencia vectorial mod-2

En teoría de matroides , un matroide binario es un matroide que se puede representar sobre el cuerpo finito GF(2) . ^[1] Es decir, hasta isomorfismo, son los matroides cuyos elementos son las columnas de una matriz (0,1) y cuyos conjuntos de elementos son independientes si y solo si las columnas correspondientes son linealmente independientes en GF(2).

Caracterizaciones alternativas

Un matroide es binario si y sólo si ${\displaystyle M}$

• Es el matroide definido a partir de una matriz simétrica (0,1). ^[2]
• Para cada conjunto de circuitos del matroide, la diferencia simétrica de los circuitos en puede representarse como una unión disjunta de circuitos. ^{[3] [4]} ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {S}}}$
• Para cada par de circuitos del matroide, su diferencia simétrica contiene otro circuito. ^[4]
• Para cada par donde es un circuito de y es un circuito del matroide dual de , es un número par. ^{[4] [5]} ${\displaystyle C,D}$ ${\displaystyle C}$ ${\displaystyle M}$ ${\displaystyle D}$ ${\displaystyle M}$ ${\displaystyle |C\cap D|}$
• Para cada par donde es una base de y es un circuito de , es la diferencia simétrica de los circuitos fundamentales inducidos en por los elementos de . ^{[4] [5]} ${\displaystyle B,C}$ ${\displaystyle B}$ ${\displaystyle M}$ ${\displaystyle C}$ ${\displaystyle M}$ ${\displaystyle C}$ ${\displaystyle B}$ ${\displaystyle C\setminus B}$
• Ningún matroide menor de es el matroide uniforme , la línea de cuatro puntos. ^{[6] [7] [8]} ${\displaystyle M}$ ${\displaystyle U{}_{4}^{2}}$
• En la red geométrica asociada al matroide, cada intervalo de altura dos tiene como máximo cinco elementos. ^[8]

Matroides relacionados

Todo matroide regular y todo matroide gráfico son binarios. ^[5] Un matroide binario es regular si y solo si no contiene el plano de Fano (un matroide binario no regular de siete elementos) o su dual como menor . ^[9] Un matroide binario es gráfico si y solo si sus menores no incluyen el dual del matroide gráfico de ni de . ^[10] Si cada circuito de un matroide binario tiene cardinalidad impar, entonces sus circuitos deben ser todos disjuntos entre sí; en este caso, puede representarse como el matroide gráfico de un grafo de cactus . ^[5] ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$

Propiedades adicionales

Si es un matroide binario, entonces también lo es su dual, y también lo es cada menor de . ^[5] Además, la suma directa de los matroides binarios es binaria. ${\displaystyle M}$ ${\displaystyle M}$

Harary y Welsh (1969) definen un matroide bipartito como un matroide en el que cada circuito tiene cardinalidad par, y un matroide euleriano como un matroide en el que los elementos pueden dividirse en circuitos disjuntos. Dentro de la clase de matroides gráficas, estas dos propiedades describen las matroides de grafos bipartitos y grafos eulerianos (grafos no necesariamente conexos en los que todos los vértices tienen grado par), respectivamente. Para grafos planares (y por lo tanto también para los matroides gráficos de grafos planares) estas dos propiedades son duales: un grafo planar o su matroide es bipartito si y solo si su dual es euleriano. Lo mismo es cierto para los matroides binarios. Sin embargo, existen matroides no binarios para los que esta dualidad se rompe. ^{[5] [11]}

Cualquier algoritmo que pruebe si un matroide dado es binario, dado acceso al matroide a través de un oráculo de independencia , debe realizar un número exponencial de consultas de oráculo y, por lo tanto, no puede tomar un tiempo polinomial. ^[12]

Referencias

1. Welsh, DJA (2010) [1976], "10. Matroides binarios", Matroid Theory , Courier Dover Publications, págs. 161-182, ISBN 9780486474397.
2. Jaeger, F. (1983), "Representaciones simétricas de matroides binarios", Combinatorial mathematics (Marseille-Luminy, 1981) , North-Holland Math. Stud., vol. 75, Ámsterdam: North-Holland, págs. 371–376, MR  0841317.
3. 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.
4. Welsh (2010), Teorema 10.1.3, pág. 162.
5. 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.
6. Tutte, WT (1958), "Un teorema de homotopía para matroides. I, II", Transactions of the American Mathematical Society , 88 (1): 144–174, doi :10.2307/1993244, JSTOR  1993244, MR  0101526.
7. 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.
8. Welsh (2010), Sección 10.2, "Un criterio menor excluido para que un matroide sea binario", págs. 167-169.
9. Welsh (2010), Teorema 10.4.1, pág. 175.
10. Welsh (2010), Teorema 10.5.1, pág. 176.
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. Seymour, PD (1981), "Reconocimiento de matroides gráficos", Combinatorica , 1 (1): 75–78, doi :10.1007/BF02579179, MR  0602418, S2CID  35579707.