matroide binaria

Abstracción de la independencia del vector mod-2

En 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 sólo si las columnas correspondientes son linealmente independientes en GF(2) .

Caracterizaciones alternativas

Una matroide es binaria si y sólo si ${\displaystyle M}$

• Es la matroide definida a partir de una matriz simétrica (0,1). ^[2]
• Para cada conjunto de circuitos de la matroide, la diferencia simétrica de los circuitos se puede representar como una unión disjunta de circuitos. ^{[3] [4]} ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {S}}}$
• Por cada par de circuitos de la matroide, su diferencia simétrica contiene otro circuito. ^[4]
• Para cada par donde es un circuito de y es un circuito de la 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 inducida 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}$
• Ninguna matroide menor es la matroide uniforme , la línea de cuatro puntos. ^{[6] [7] [8]} ${\displaystyle M}$ ${\displaystyle U{}_{4}^{2}}$
• En la red geométrica asociada a la matroide, cada intervalo de altura dos tiene como máximo cinco elementos. ^[8]

matroides relacionadas

Cada matroide normal y cada matroide gráfica es binaria. ^[5] Una matroide binaria es regular si y sólo si no contiene el plano de Fano (una matroide binaria no regular de siete elementos) o su dual como menor . ^[9] Una matroide binaria es gráfica si y sólo 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, se puede representar como la matroide gráfica de un gráfico de cactus . ^[5] ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$

Propiedades adicionales

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

Harary y Welsh (1969) definen una matroide bipartita como una matroide en la que cada circuito tiene cardinalidad par, y una matroide euleriana como una matroide en la que los elementos pueden dividirse en circuitos disjuntos. Dentro de la clase de matroides gráficas, estas dos propiedades describen las matroides de gráficos bipartitos y gráficos eulerianos (gráficos no necesariamente conectados en los que todos los vértices tienen grados pares), respectivamente. Para gráficos planos (y por lo tanto también para las matroides gráficas de gráficos planos) estas dos propiedades son duales: un gráfico plano o su matroide es bipartito si y sólo si su dual es eulerian. Lo mismo ocurre con las matroides binarias. Sin embargo, existen matroides no binarias en las que esta dualidad se rompe. ^{[5] [11]}

Cualquier algoritmo que pruebe si una matroide determinada es binaria, con acceso a la 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 polinómico. ^[12]

Referencias

1. Welsh, DJA (2010) [1976], "10. Matroides binarias", Teoría de matroides , Publicaciones Courier Dover, págs. 161-182, ISBN 9780486474397.
2. Jaeger, F. (1983), "Representaciones simétricas de matroides binarias", Matemáticas combinatorias (Marsella-Luminy, 1981) , Matemáticas de Holanda Septentrional. Stud., vol. 75, Ámsterdam: Holanda Septentrional, págs. 371–376, SEÑOR  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, SEÑOR  1507091.
4. Welsh (2010), Teorema 10.1.3, p. 162.
5. Harary, Frank ; Welsh, Dominic (1969), "Matroides versus gráficos", The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Michigan, 1968) , Lecture Notes in Mathematics, vol. 110, Berlín: Springer, págs. 155-170, doi :10.1007/BFb0060114, MR  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 Estándares , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR  0179781.
8. Welsh (2010), Sección 10.2, "Un criterio menor excluido para que una matroide sea binaria", págs.
9. Galés (2010), Teorema 10.4.1, p. 175.
10. Galés (2010), Teorema 10.5.1, p. 176.
11. Welsh, DJA (1969), "Euler y las matroides bipartitas", 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áficas", Combinatorica , 1 (1): 75–78, doi :10.1007/BF02579179, MR  0602418, S2CID  35579707.