Base de un matroide

Conjunto independiente máximo del matroide

En matemáticas, una base de un matroide es un conjunto independiente máximo del matroide, es decir, un conjunto independiente que no está contenido en ningún otro conjunto independiente.

Ejemplos

A modo de ejemplo, considere el matroide sobre el conjunto base R ² (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 un matroide gráfico , donde los conjuntos independientes son los bosques, las bases se denominan bosques de expansión del gráfico.
• En un matroide transversal , donde los conjuntos independientes son puntos finales de las correspondencias en un gráfico bipartito dado , las bases se denominan transversales .
• En un matroide lineal , donde los conjuntos independientes son los conjuntos linealmente independientes de vectores en un espacio vectorial dado, las bases se denominan simplemente bases del espacio vectorial. Por lo tanto, el concepto de base de un matroide generaliza el concepto de base del álgebra lineal .
• En un matroide uniforme , donde los conjuntos independientes son todos conjuntos con cardinalidad como máximo k (para algún entero k ), las bases son todos conjuntos con cardinalidad exactamente k .
• En un matroide de partición , donde los elementos se dividen en categorías y los conjuntos independientes son todos los conjuntos que contienen como máximo k _c elementos de cada categoría c, las bases son todos los conjuntos que contienen exactamente k _c elementos de la categoría c .
• En un matroide libre , donde todos los subconjuntos del conjunto base E son independientes, la base única es E.

Propiedades

Intercambio

Todos los matroides satisfacen las siguientes propiedades, para dos bases distintas y : ^{[2] [3]} ${\displaystyle A}$ ${\displaystyle B}$

• Propiedad de intercambio de base : si , entonces existe un elemento tal que es una base. ${\displaystyle a\in A\setminus B}$ ${\displaystyle b\in B\setminus A}$ ${\displaystyle (A\setminus \{a\})\cup \{b\}}$
• Propiedad simétrica de intercambio de bases : si , entonces existe un elemento tal que tanto como son bases. Brualdi ^[4] demostró que, de hecho, es equivalente a la propiedad de intercambio de bases. ${\displaystyle a\in A\setminus B}$ ${\displaystyle b\in B\setminus A}$ ${\displaystyle (A\setminus \{a\})\cup \{b\}}$ ${\displaystyle (B\setminus \{b\})\cup \{a\}}$
• Propiedad de intercambio de bases simétrica múltiple : si , entonces existe un subconjunto tal que tanto como son bases. Brylawski, Greene y Woodall demostraron (independientemente) que, de hecho, es equivalente a la propiedad de intercambio de bases. ${\displaystyle X\subseteq A\setminus B}$ ${\displaystyle Y\subseteq B\setminus A}$ ${\displaystyle (A\setminus X)\cup Y}$ ${\displaystyle (B\setminus Y)\cup X}$
• Propiedad biyectiva de intercambio de bases : Existe una biyección de a , tal que para cada , es una base. Brualdi ^[4] demostró que es equivalente a la propiedad de intercambio de bases. ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle a\in A\setminus B}$ ${\displaystyle (A\setminus \{a\})\cup \{f(a)\}}$
• Propiedad de intercambio de base de partición : Para cada partición de en m partes, existe una partición de en m partes, tal que para cada , es una base. ^[5] ${\displaystyle (A_{1},A_{2},\ldots ,A_{m})}$ ${\displaystyle A}$ ${\displaystyle (B_{1},B_{2},\ldots ,B_{m})}$ ${\displaystyle B}$ ${\displaystyle i\in [m]}$ ${\displaystyle (A\setminus A_{i})\cup B_{i}}$

Sin embargo, una propiedad de intercambio de base que sea a la vez simétrica y biyectiva no es satisfecha por todos los matroides: es satisfecha únicamente por los matroides ordenables por base .

En general, en la propiedad de intercambio de base simétrica, el elemento no necesita ser único. Los matroides regulares tienen la propiedad de intercambio único , lo que significa que para algún , el b correspondiente es único. ^[6] ${\displaystyle b\in B\setminus A}$ ${\displaystyle a\in A\setminus B}$

Cardinalidad

De la propiedad básica de intercambio se desprende que ningún miembro de puede ser un subconjunto propio de otro. ${\displaystyle {\mathcal {B}}}$

Además, todas las bases de un matroide dado tienen la misma cardinalidad. En un matroide lineal, la cardinalidad de todas las bases se denomina dimensión del espacio vectorial.

La conjetura de Neil White

Se conjetura que todos los 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 múltiples conjuntos, entonces existe una secuencia de intercambios simétricos que transforma B en B' .

Caracterización

Las bases de un matroide caracterizan al matroide por completo: un conjunto es independiente si y solo si es un subconjunto de una base. Además, se puede definir un matroide como un par , donde es el conjunto base y es una colección de subconjuntos de , llamados "bases", con las siguientes propiedades: ^{[7] [8]} ${\displaystyle M}$ ${\displaystyle (E,{\mathcal {B}})}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle E}$

(B1) Hay al menos una base: no está vacía; ${\displaystyle {\mathcal {B}}}$

(B2) Si y son bases distintas, y , entonces existe un elemento tal que es una base (esta es la propiedad de intercambio de bases). ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle a\in A\setminus B}$ ${\displaystyle b\in B\setminus A}$ ${\displaystyle (A\setminus \{a\})\cup \{b\}}$

(B2) implica que, dadas dos bases cualesquiera A y B , podemos transformar A en B mediante una secuencia de intercambios de un único elemento. En particular, esto implica que todas las bases deben tener la misma cardinalidad.

Dualidad

Si es un matroide finito, podemos definir el matroide ortogonal o dual llamando a un conjunto una base en si y solo si su complemento está en . Se puede verificar que es efectivamente un matroide. La definición implica inmediatamente que el dual de es . ^{[9] : 32  [10]} ${\displaystyle (E,{\mathcal {B}})}$ ${\displaystyle (E,{\mathcal {B}}^{*})}$ ${\displaystyle {\mathcal {B}}^{*}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle (E,{\mathcal {B}}^{*})}$ ${\displaystyle (E,{\mathcal {B}}^{*})}$ ${\displaystyle (E,{\mathcal {B}})}$

Utilizando la dualidad, se puede demostrar que la propiedad (B2) puede ser reemplazada por la siguiente:

(B2*) Si y son bases distintas, y , entonces existe un elemento tal que es una base. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle b\in B\setminus A}$ ${\displaystyle a\in A\setminus B}$ ${\displaystyle (A\setminus \{a\})\cup \{b\}}$

Circuitos

Una noción dual de base es circuito . Un circuito en un 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 los matroides gráficos son ciclos en los grafos correspondientes.

Se puede definir un matroide como un par , donde es el conjunto base y es una colección de subconjuntos de , llamados "circuitos", con las siguientes propiedades: ^[8] ${\displaystyle M}$ ${\displaystyle (E,{\mathcal {C}})}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle E}$

(C1) El conjunto vacío no es un circuito;

(C2) Un subconjunto propio de un circuito no es un circuito;

(C3) Si C ₁ y C ₂ son circuitos distintos y x es un elemento en su intersección, entonces contiene un circuito. ${\displaystyle C_{1}\cup C_{2}\setminus \{x\}}$

Otra propiedad de los circuitos es que, si un conjunto es independiente y el conjunto es dependiente (es decir, la suma de los elementos lo hace dependiente), entonces contiene un circuito único , y contiene . Este circuito se llama circuito fundamental con respecto a . Es análogo al hecho del álgebra lineal de que si la suma de un vector a un conjunto de vectores independiente lo hace dependiente, entonces existe una combinación lineal única de elementos de que es igual a . ^[10] ${\displaystyle J}$ ${\displaystyle J\cup \{x\}}$ ${\displaystyle x}$ ${\displaystyle J\cup \{x\}}$ ${\displaystyle C(x,J)}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle J}$ ${\displaystyle x}$ ${\displaystyle J}$ ${\displaystyle J}$ ${\displaystyle x}$

Véase también

• Politopo matroide : un politopo en R ⁿ (donde n es el número de elementos del matroide), cuyos vértices son vectores indicadores de las bases del matroide.

Referencias

1. Ardila, Federico (2007). "Matroides, lección 3". youtube . Archivado desde el original el 14 de febrero de 2020.
2. Bonin, Joseph E.; Savitsky, Thomas J. (1 de enero de 2016). "Una familia infinita de menores excluidos para una fuerte ordenabilidad de bases". Álgebra lineal y sus aplicaciones . 488 : 396–429. arXiv : 1507.05521 . doi :10.1016/j.laa.2015.09.055. ISSN  0024-3795. S2CID  119161534.
   • Joseph E. Bonin; Thomas J. Savitsky (abril de 2016). "Menores excluidos para matroides de ordenación de base (fuerte)" (PDF) .
3. "Matroids Clase 2: Bases". YouTube .
4. Brualdi, Richard A. (1969-08-01). "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.
5. Greene, Curtis; Magnanti, Thomas L. (1975-11-01). "Algunos algoritmos de pivote abstractos". Revista SIAM de Matemáticas Aplicadas . 29 (3): 530–539. doi :10.1137/0129045. hdl : 1721.1/5113 . ISSN  0036-1399.
6. McGuinness, Sean (1 de julio de 2014). "Una propiedad de intercambio de bases para matroides regulares". Journal of Combinatorial Theory, Serie B. 107 : 42–77. doi : 10.1016/j.jctb.2014.02.004 . ISSN  0095-8956.
7. Welsh, DJA (1976), Teoría de matroides , Monografías LMS, vol. 8, Academic Press, ISBN 978-0-12-744050-7, Zbl0343.05002 ​. Sección 1.2, "Sistemas axiomáticos para un matroide", págs. 7–9.
8. Federico, Ardila (2012). "Matroides: Conferencia 6". YouTube .
9. White, Neil, ed. (1986), Teoría de matroides , Enciclopedia de matemáticas y sus aplicaciones, vol. 26, Cambridge: Cambridge University Press, ISBN 978-0-521-30937-0, Zbl  0579.00001
10. Ardila, Federico (2012). "Conferencia 7 sobre matroides". YouTube .