En la teoría matroide , una matroide binaria es una matroide que se puede representar sobre el campo finito GF (2) . [1] Es decir, hasta el isomorfismo, son las 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
Una matroide es binario si y solo si
- Es la matriz definida a partir de una matriz simétrica (0,1). [2]
- Para cada set de circuitos del matroide, la diferencia simétrica de los circuitos ense puede representar como una unión disjunta de circuitos. [3] [4]
- Por cada par de circuitos del matroide, su diferencia simétrica contiene otro circuito. [4]
- Por cada par dónde es un circuito de y es un circuito del matroide dual de, es un número par. [4] [5]
- Por cada par dónde 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]
- No matroide menor dees la matroide uniforme , la línea de cuatro puntos. [6] [7] [8]
- En la celosía geométrica asociada a la matroide, cada intervalo de altura dos tiene como máximo cinco elementos. [8]
Matroides relacionados
Cada matroide regular , y cada matroide gráfico , es binario. [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] Una matroide binaria es gráfica si y solo si sus menores no incluyen el dual de la matroide gráfica de ni de . [10] Si cada circuito de una matroide binaria tiene cardinalidad impar, entonces todos sus circuitos deben estar separados entre sí; en este caso, puede representarse como la matriz gráfica de un gráfico de cactus . [5]
Propiedades adicionales
Si es una matroide binaria, entonces también lo es su dual, y también lo es cada menor de. [5] Además, la suma directa de matroides binarios es binaria.
Harary y Welsh (1969) definen una matroide bipartita como una matroide en la que cada circuito tiene incluso cardinalidad, y una matroide euleriana como una matroide en la que los elementos pueden dividirse en circuitos disjuntos. Dentro de la clase de matroides gráficos, estas dos propiedades describen las matroides de grafos bipartitos y grafos eulerianos ( grafos no necesariamente conectados en los que todos los vértices tienen grados pares), respectivamente. Para gráficas planas (y por lo tanto también para las matroides gráficas de gráficas planas) estas dos propiedades son duales: una gráfica planar o su matroide es bipartita si y solo si su dual es euleriana. Lo mismo es cierto para las matroides binarias. 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 tiempo polinomial. [12]
Referencias
- ^ Galés, DJA (2010) [1976], "10. Binary Matroids", Teoría de Matroid , Publicaciones de Courier Dover, págs. 161-182, ISBN 9780486474397.
- ^ Jaeger, F. (1983), "Representaciones simétricas de matroides binarias", Matemática combinatoria (Marseille-Luminy, 1981) , North-Holland Math. Stud., 75 , Amsterdam: North-Holland, págs. 371–376, MR 0841317.
- ^ Whitney, Hassler (1935), "Sobre las propiedades abstractas de la dependencia lineal", American Journal of Mathematics , The Johns Hopkins University Press, 57 (3): 509–533, doi : 10.2307 / 2371182 , hdl : 10338.dmlcz / 100694 , JSTOR 2371182 , MR 1507091.
- ↑ a b c d Galés (2010) , Teorema 10.1.3, p. 162.
- ^ a b c d e f Harary, Frank ; Welsh, Dominic (1969), "Matroids versus graphs", The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) , Lecture Notes in Mathematics, 110 , Berlín: Springer, págs. 155-170, doi : 10.1007 / BFb0060114 , MR 0263666.
- ^ 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.
- ^ Tutte, WT (1965), "Lectures on matroids" , Journal of Research of the National Bureau of Standards , 69B : 1–47, doi : 10.6028 / jres.069b.001 , MR 0179781.
- ↑ a b Welsh (2010) , Sección 10.2, "Un criterio menor excluido para que un matroide sea binario", págs. 167-169.
- ^ Galés (2010) , Teorema 10.4.1, p. 175.
- ^ Galés (2010) , Teorema 10.5.1, p. 176.
- ^ Welsh, DJA (1969), "Euler and bipartite matroids", Journal of Combinatorial Theory , 6 (4): 375–377, doi : 10.1016 / s0021-9800 (69) 80033-5 , MR 0237368/
- ^ Seymour, PD (1981), "Recognizing graphic matroids", Combinatorica , 1 (1): 75–78, doi : 10.1007 / BF02579179 , MR 0602418 , S2CID 35579707.