Base de un matroide

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

Como ejemplo, consideremos el matroide sobre el conjunto base R ² (los vectores en el plano euclidiano bidimensional), con los siguientes conjuntos independientes:

Tiene dos bases, que son los conjuntos {(0,1),(2,0)} y {(0,3),(2,0)}. Estos son los únicos conjuntos independientes que son maximales bajo la 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 generadores del grafo.
• En un matroide transversal , donde los conjuntos independientes son los extremos de los emparejamientos en un grafo bipartito dado , las bases se denominan transversales .
• En un matroide 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 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 particionan 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.

Las bases de un matroide caracterizan completamente al matroide: un conjunto es independiente si y solo si es un subconjunto de una base. Además, se puede definir un matroide.${\displaystyle M}$ser una pareja${\displaystyle (E,{\mathcal {B}})}$, dónde${\displaystyle E}$es el terreno establecido y${\displaystyle {\mathcal {B}}}$es una colección de subconjuntos de${\displaystyle E}$, llamadas "bases", con las siguientes propiedades: ^{[ 7 ] [ 8 ]}

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

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

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

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

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

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

Un concepto dual a base es el de circuito . Un circuito en un matroide es un conjunto dependiente mínimo; es decir, un conjunto dependiente cuyos subconjuntos propios son todos independientes. Esta terminología surge porque los circuitos de los matroides gráficos son ciclos en los grafos correspondientes.

Se puede definir un matroide.${\displaystyle M}$ser una pareja${\displaystyle (E,{\mathcal {C}})}$, dónde${\displaystyle E}$es el terreno establecido y${\displaystyle {\mathcal {C}}}$es una colección de subconjuntos de${\displaystyle E}$, denominados "circuitos", con las siguientes propiedades: ^{[ 8 ]}

(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${\displaystyle (C_{1}\cup C_{2})\setminus \{x\}}$contiene un circuito.

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

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