En matemáticas, la base de un matroide es un conjunto máximo independiente del matroide, es decir, un conjunto independiente que no está contenido en ningún otro conjunto independiente.
Ejemplos de
Como ejemplo, considere la matroide sobre el conjunto base R 2 (los vectores en el plano euclidiano bidimensional), con los siguientes conjuntos independientes:
{{}, {(0,1)}, {(2,0)}, {(0,1), (2,0)}, {(0,3)}, {(0,3), ( 2,0)}}.
Tiene dos bases, que son los conjuntos {(0,1), (2,0)}, {(0,3), (2,0)}. Estos son los únicos conjuntos independientes que son máximos bajo inclusión.
La base tiene un nombre especializado en varios tipos especializados de matroides: [1]
- En una matriz gráfica , donde los conjuntos independientes son los bosques, las bases se denominan bosques de expansión del gráfico.
- En una matriz transversal , donde los conjuntos independientes son puntos finales de emparejamientos en un gráfico bipartito dado, las bases se denominan transversales .
- En una matriz lineal , donde los conjuntos independientes son los conjuntos de vectores linealmente independientes en un espacio vectorial dado, las bases se denominan simplemente bases del espacio vectorial. Por tanto, el concepto de base de una matroide generaliza el concepto de base a partir del álgebra lineal .
- En una matriz uniforme , donde los conjuntos independientes son todos conjuntos con cardinalidad como máximo k (para algún número entero k ), las bases son todos conjuntos con cardinalidad exactamente k .
- En una matriz de partición , donde los elementos se dividen en categorías y los conjuntos independientes son todos conjuntos que contienen como máximo k c elementos de cada categoría c, las bases son todos conjuntos que contienen exactamente k c elementos de la categoría c .
- En una matroide libre , donde todos los subconjuntos del conjunto básico E son independientes, la base única es E.
Propiedades
Intercambio
Todos los matroides satisfacen las siguientes propiedades, para dos bases distintas y : [2]
- Propiedad de intercambio de base : si, entonces existe un elemento tal que es una base.
- Propiedad de intercambio de base simétrica : si, entonces existe un elemento tal que ambos y son bases. Brualdi [3] demostró que de hecho es equivalente a la propiedad de intercambio de base.
- Propiedad de intercambio de bases simétricas múltiples : si, entonces existe un subconjunto tal que ambos y son bases. Brylawski, Greene y Woodall demostraron (independientemente) que de hecho es equivalente a la propiedad de intercambio de base.
- Propiedad biyectiva de intercambio de bases : hay una biyección de a , de modo que para cada , es una base. Brualdi [3] demostró que es equivalente a la propiedad de intercambio de base.
- Propiedad de intercambio de base de partición : para cada partición deen m partes, existe una partición deen m partes, de modo que para cada, es una base. [4]
Sin embargo, una propiedad de intercambio de bases que es a la vez simétrica y biyectiva no es satisfecha por todas las matroides: sólo la satisfacen las matroides ordenables por bases .
Cardinalidad
De la propiedad de intercambio base se deduce que ningún miembro de puede ser un subconjunto adecuado de otro.
Además, todas las bases de un matroide dado tienen la misma cardinalidad. En una matroide lineal, la cardinalidad de todas las bases se llama dimensión del espacio vectorial.
Conjetura de White
Se conjetura que todas las matroides satisfacen la siguiente propiedad: [2] Para cada entero t ≥ 1 , si B y B ' son dos t -tuplas de bases con la misma unión de conjuntos múltiples, entonces hay una secuencia de intercambios simétricos que transforma B en B ' .
Caracterización
Las bases de una matroide caracterizan completamente a la matroide: un conjunto es independiente si y solo si es un subconjunto de una base. Además, se puede definir un matroide ser un par , dónde es la base y es una colección de subconjuntos de , llamadas "bases", con las siguientes propiedades: [5] [6]
- (B1) Hay al menos una base - no está vacío;
- (B2) Si y son bases distintas, y , entonces existe un elemento tal que es una base (esta es la propiedad de intercambio de base).
Dualidad
Si es una matroide finita, podemos definir la matroide ortogonal o dual llamando a un conjunto una base en si y solo si su complemento está en . Se puede verificar quees de hecho una matroide. La definición implica inmediatamente que el dual de es . [7] : 32 [8]
Usando la dualidad, se puede probar que la propiedad (B2) puede ser reemplazada por lo siguiente:
(B2 *) Si y son bases distintas, y , entonces existe un elemento tal que es una base.
Circuitos
Una noción dual de base es un circuito . Un circuito en una matroide es un conjunto dependiente mínimo, es decir, un conjunto dependiente cuyos subconjuntos propios son todos independientes. La terminología surge porque los circuitos de las matroides gráficas son ciclos en los gráficos correspondientes.
se puede definir una matroide ser un par , dónde es la base y es una colección de subconjuntos de , llamados "circuitos", con las siguientes propiedades: [6]
- (C1) El conjunto vacío no es un circuito;
- (C2) Un subconjunto de un circuito no es un circuito;
- (C3) Si C 1 y C 2 son circuitos, y x es un elemento en su intersección, entonces contiene un circuito.
Otra propiedad de los circuitos es que, si un conjunto J es independiente y el conjunto J u { x } es dependiente (es decir, la suma del elemento x lo hace dependiente), entonces J u { x } contiene un circuito único C ( x , J ) y contiene x . Este circuito se llama el circuito fundamental de x wrt J . Es análogo al hecho del álgebra lineal, que si agregar un vector x a un conjunto de vectores independientes J lo hace dependiente, entonces hay una combinación lineal única de elementos de J que es igual a x . [8]
Referencias
- ^ Ardila, Frederico (2007). "Matroides, conferencia 3" . youtube .
- ^ a b "Una familia infinita de menores excluidos para una fuerte ordenabilidad de base" . Álgebra lineal y sus aplicaciones . 488 : 396–429. 2016-01-01. arXiv : 1507.05521 . doi : 10.1016 / j.laa.2015.09.055 . ISSN 0024-3795 . Lay resumen (PDF) .
- ^ a b Brualdi, Richard A. (1 de agosto de 1969). "Comentarios sobre bases en estructuras de dependencia" . Boletín de la Sociedad Matemática Australiana . 1 (2): 161-167. doi : 10.1017 / S000497270004140X . ISSN 1755-1633 .
- ^ Greene, Curtis; Magnanti, Thomas L. (1 de noviembre de 1975). "Algunos algoritmos abstractos de pivote" . Revista SIAM de Matemática Aplicada . 29 (3): 530–539. doi : 10.1137 / 0129045 . hdl : 1721,1 / 5113 . ISSN 0036-1399 .
- ^ Galés, DJA (1976), Teoría Matroide , Monografías de LMS, 8 , Academic Press, ISBN 978-0-12-744050-7, Zbl 0343.05002. Sección 1.2, "Axiom Systems for a Matroid", págs. 7-9.
- ^ a b Federico, Ardila (2012). "Matroides: Clase 6" . Youtube .
- ^ White, Neil, ed. (1986), Teoría de las Matroides , Enciclopedia de las Matemáticas y sus Aplicaciones, 26 , Cambridge: Cambridge University Press, ISBN 978-0-521-30937-0, Zbl 0579.00001
- ^ a b Ardila, Federico (2012). "Conferencia Matroids 7" . Youtube .