Matroid

En términos de independencia, un matroide finito${\displaystyle M}$es un par${\displaystyle (E,{\mathcal {I}})}$, dónde${\displaystyle E}$es un conjunto finito (llamado conjunto base ) y${\displaystyle {\mathcal {I}}}$es una familia de subconjuntos de${\displaystyle E}$(llamados conjuntos independientes ) con las siguientes propiedades: ^{[ 4 ]}

• (I1) El conjunto vacío es independiente, es decir,${\displaystyle \emptyset \in {\mathcal {I}}}$.

• (I2) Cada subconjunto de un conjunto independiente es independiente, es decir, para cada${\displaystyle A'\subsetae}$, si${\displaystyle A\in {\mathcal {I}}}$entonces${\displaystyle A'\in {\mathcal {I}}}$A esto se le llama a veces propiedad hereditaria o propiedad cerrada hacia abajo .

• (I3) Si${\displaystyle A}$y${\displaystyle B}$son dos conjuntos independientes (es decir, cada conjunto es independiente) y${\displaystyle A}$tiene más elementos que${\displaystyle B}$, entonces existe${\displaystyle x\in A\setminus B}$de tal manera que${\displaystyle B\cup \{x\}}$es independiente. Esto a veces se denomina propiedad de aumento o propiedad de intercambio de conjuntos independientes (cf. lema de intercambio de Steinitz ).

Las dos primeras propiedades definen una estructura combinatoria conocida como sistema de independencia (o complejo simplicial abstracto ). En realidad, asumiendo (I2), la propiedad (I1) es equivalente al hecho de que al menos un subconjunto de${\displaystyle E}$es independiente, es decir,${\displaystyle {\mathcal {I}}\neq \emptyset }$.

Un subconjunto del conjunto base${\displaystyle E}$Lo que no es independiente se llama dependiente .

Un conjunto independiente maximal – es decir, un conjunto independiente que se vuelve dependiente al agregar cualquier elemento de${\displaystyle E}$– se denomina base para el matroide.

Un circuito en un matroid${\displaystyle M}$es un subconjunto dependiente mínimo de${\displaystyle E}$—es decir, un conjunto dependiente cuyos subconjuntos propios son todos independientes. El término surge porque los circuitos de los matroides gráficos son ciclos en los grafos correspondientes. ^{[ 4 ]}

Los conjuntos dependientes, las bases o los circuitos de un matroide caracterizan completamente al matroide: un conjunto es independiente si y solo si no es dependiente, si y solo si es un subconjunto de una base, y si y solo si no contiene un circuito. Las colecciones de conjuntos dependientes, de bases y de circuitos tienen propiedades simples que pueden tomarse como axiomas para un matroide. Por ejemplo, se puede definir un matroide${\displaystyle M}$ser una pareja${\displaystyle (E,{\mathcal {B}})}$, dónde${\displaystyle E}$es un conjunto finito como antes y${\displaystyle {\mathcal {B}}}$es una colección de subconjuntos de${\displaystyle E}$, llamadas bases , con las siguientes propiedades: ^{[ 4 ]}

• (B1)${\displaystyle {\mathcal {B}}}$no está vacío.

• (B2) Si${\displaystyle A}$y${\displaystyle B}$son miembros distintos de${\displaystyle {\mathcal {B}}}$y${\displaystyle a\in A\smallsetminus B}$, entonces existe un elemento${\displaystyle b\in B\smallsetminus A}$de tal manera que${\displaystyle (A\smallsetminus \{a\})\cup \{b\}\in {\mathcal {B}}}$.

Esta propiedad (B2) se llama propiedad de intercambio de base . De esta propiedad se deduce que ningún miembro de${\displaystyle {\mathcal {B}}}$puede ser un subconjunto propio de cualquier otro.

Es un resultado básico de la teoría de matroides, directamente análogo a un teorema similar de bases en álgebra lineal , que cualesquiera dos bases de un matroide${\displaystyle M}$tienen el mismo número de elementos. Este número se llama rango de${\displaystyle M}$. Si${\displaystyle M}$es un matroide en${\displaystyle E}$, y${\displaystyle A}$es un subconjunto de${\displaystyle E}$, luego un matroide en${\displaystyle A}$se puede definir considerando un subconjunto de${\displaystyle A}$ser independiente si y solo si es independiente en${\displaystyle M}$. Esto nos permite hablar de submatroides y del rango de cualquier subconjunto de${\displaystyle E}$. El rango de un subconjunto${\displaystyle A}$viene dada por la función de rango${\displaystyle r(A)}$del matroide, que tiene las siguientes propiedades: ^{[ 4 ]}

• (R1) El valor de la función de rango es siempre un entero no negativo .

• (R2) Para cualquier subconjunto${\displaystyle A\subset E}$, tenemos${\displaystyle r(A)\leq |A|}$.

• (R3) Para cualesquiera dos subconjuntos${\displaystyle A,B\subset E}$, tenemos:${\displaystyle r(A\cup B)+r(A\cap B)\leq r(A)+r(B)}$. Es decir, el rango es una función submodular .

• (R4) Para cualquier conjunto${\displaystyle A}$y elemento${\displaystyle x}$, tenemos:${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1}$De la primera desigualdad se deduce de forma más general que, si${\displaystyle A\subseteq B\subseteq E}$, entonces${\displaystyle r(A)\leq r(B)\leq r(E)}$. Es decir, el rango es una función monótona .

Estas propiedades pueden utilizarse como una de las definiciones alternativas de un matroide finito: Si${\displaystyle (E,r)}$Si satisface estas propiedades, entonces los conjuntos independientes de un matroide sobre${\displaystyle E}$pueden definirse como esos subconjuntos${\displaystyle A}$de${\displaystyle E}$con${\displaystyle r(A)=|A|}$. En el lenguaje de conjuntos parcialmente ordenados , dicha estructura matroide es equivalente al retículo geométrico cuyos elementos son los subconjuntos${\displaystyle A\subset M}$, parcialmente ordenado por inclusión.

La diferencia${\displaystyle |A|-r(A)}$se denomina nulidad del subconjunto${\displaystyle A}$Es el número mínimo de elementos que deben eliminarse de${\displaystyle A}$para obtener un conjunto independiente. La nulidad de${\displaystyle E}$en${\displaystyle M}$se llama la nulidad de${\displaystyle M}$La diferencia${\displaystyle r(E)-r(A)}$a veces se le llama corango del subconjunto${\displaystyle A}$.

Dejar${\displaystyle M}$ser un matroide en un conjunto finito${\displaystyle E}$, con función de rango${\displaystyle r}$como se indicó anteriormente. El cierre o lapso${\displaystyle \operatorname {cl} (A)}$de un subconjunto${\displaystyle A}$de${\displaystyle E}$es el conjunto

${\displaystyle \operatorname {cl} (A)={\Bigl \{}\ x\in E\mid r(A)=r{\bigl (}A\cup \{x\}{\bigr )}{\Bigr \}}}$.

Esto define un operador de cierre.${\displaystyle \operatorname {cl}$ :{\mathcal {P}}(E)\mapsto {\mathcal {P}}(E)} donde${\displaystyle {\mathcal {P}}}$denota el conjunto potencia , con las siguientes propiedades:

• (C1) Para todos los subconjuntos${\displaystyle X}$de${\displaystyle E}$,${\displaystyle X\subseteq \operatorname {cl} (X).}$

• (C2) Para todos los subconjuntos${\displaystyle X}$de${\displaystyle E}$,${\displaystyle \operatorname {cl} (X)=\operatorname {cl} \left(\operatorname {cl} \left(X\right)\right).}$

• (C3) Para todos los subconjuntos${\displaystyle X}$y${\displaystyle Y}$de${\displaystyle E}$con${\displaystyle X\subsetequ Y}$,${\displaystyle \operatorname {cl} (X)\subseteq \operatorname {cl} (Y).}$

• (C4) Para todos los elementos${\displaystyle a}$y${\displaystyle b}$de${\displaystyle E}$y todos los subconjuntos${\displaystyle Y}$de${\displaystyle E}$, si${\displaystyle a\in \operatorname {cl} (Y\cup \{b\})\smallsetminus \operatorname {cl} (Y)}$entonces${\displaystyle b\in \operatorname {cl} (Y\cup \{a\})\smallsetminus \operatorname {cl} (Y).}$

Las tres primeras de estas propiedades son las propiedades definitorias de un operador de cierre. La cuarta a veces se denomina propiedad de intercambio de Mac Lane - Steinitz . Estas propiedades pueden tomarse como otra definición de matroide: toda función${\displaystyle \operatorname {cl}$ :{\mathcal {P}}(E)\to {\mathcal {P}}(E)} que obedece estas propiedades determina un matroide. ^{[ 4 ]}

Un conjunto cuya clausura es igual a sí mismo se denomina cerrado , o plano o subespacio del matroide. ^{[ 5 ]} Un conjunto es cerrado si es maximal para su rango, lo que significa que la adición de cualquier otro elemento al conjunto aumentaría su rango. Los conjuntos cerrados de un matroide se caracterizan por una propiedad de partición de recubrimiento:

• (F1) El conjunto completo de puntos${\displaystyle E}$Está cerrado.

• (F2) Si${\displaystyle S}$y${\displaystyle T}$son pisos, entonces${\displaystyle S\cap T}$es un piso.

• (F3) Si${\displaystyle S}$es un piso, entonces cada elemento de${\displaystyle E\smallsetminus S}$está precisamente en uno de los pisos${\displaystyle T}$que cubren${\displaystyle S}$(lo que significa que${\displaystyle T}$contiene adecuadamente${\displaystyle S}$pero no hay piso${\displaystyle U}$entre${\displaystyle S}$y${\displaystyle T}$).

La clase${\displaystyle {\mathcal {L}}(M)}$de todos los planos, parcialmente ordenados por inclusión de conjuntos, forman una red matroide . Recíprocamente, toda red matroide${\displaystyle L}$forma un matroide sobre su conjunto${\displaystyle E}$de átomos bajo el siguiente operador de cierre: para un conjunto${\displaystyle S}$de átomos con unión${\displaystyle \bigvee S}$,

${\displaystyle \operatorname {cl} (S)=\{x\in E\mid x\leq \bigvee S\}.}$

Las caras planas de este matroide se corresponden uno a uno con los elementos de la red; la cara plana corresponde al elemento de la red.${\displaystyle y}$es el conjunto

${\displaystyle \{x\in E\mid x\leq y\}.}$

Por lo tanto, la red de planos de este matroide es naturalmente isomorfa a${\displaystyle L}$.

En un matroide de rango${\displaystyle r}$, un piso de rango${\displaystyle r-1}$se denomina hiperplano , o coátomos o copuntos . Estos son los planos propios máximos; es decir, el único superconjunto de un hiperplano que también es un plano es el conjunto${\displaystyle E}$de todos los elementos del matroide. Una definición equivalente es que un coatoma es un subconjunto de E que no genera M , pero tal que al agregarle cualquier otro elemento se obtiene un conjunto generador. ^{[ 6 ]}

La familia${\displaystyle {\mathcal {H}}}$de hiperplanos de un matroide tiene las siguientes propiedades, que pueden tomarse como otra axiomatización de los matroides: ^{[ 6 ]}

• (H1) El conjunto del terreno${\displaystyle E}$En sí mismo no es un hiperplano.

• (H2) No existen conjuntos distintos${\displaystyle X}$y${\displaystyle Y}$en${\displaystyle {\mathcal {H}}}$con${\displaystyle X\subseteq Y}$. Es decir, los hiperplanos forman una familia de Sperner .

• (H3) Por cada${\displaystyle x\in E}$y distintos${\displaystyle Y,Z\in {\mathcal {H}}}$con${\displaystyle x\notin Y\cup Z}$, existe${\displaystyle X\in {\mathcal {H}}}$con${\displaystyle (Y\cap Z)\cup \{x\}\subseteq X}$.

Minty (1966) definió un grafoide como un triple${\displaystyle (L,C,D)}$en el cual${\displaystyle C}$y${\displaystyle D}$son clases de subconjuntos no vacíos de${\displaystyle L}$de tal manera que

• (G1) ningún elemento de${\displaystyle C}$(llamado "circuito") contiene otro,

• (G2) ningún elemento de${\displaystyle D}$(llamado "cocircuito") contiene otro,

• (G3) no hay conjunto en${\displaystyle C}$y situado en${\displaystyle D}$se intersecan en exactamente un elemento, y

• (G4) siempre${\displaystyle L}$se representa como la unión disjunta de subconjuntos${\displaystyle R,G,B}$con${\displaystyle G=\{g\}}$(un conjunto unitario ), entonces o bien un${\displaystyle X\in C}$existe tal que${\displaystyle g\in X\subseteq R\cup G}$o un${\displaystyle Y\in D}$existe tal que${\displaystyle g\in Y\subseteq B\cup G}$.

Demostró que existe un matroide para el cual${\displaystyle C}$es la clase de circuitos y${\displaystyle D}$es la clase de cocircuitos. Por el contrario, si${\displaystyle C}$y${\displaystyle D}$son las clases de circuito y cocircuito de un matroid${\displaystyle M}$con el suelo establecido${\displaystyle E}$, entonces${\displaystyle (E,C,D)}$es un grafoide. Por lo tanto, los grafoides proporcionan una axiomatización criptomórfica autodual de los matroides.

Dejar${\displaystyle E}$sea ​​un conjunto finito. El conjunto de todos los subconjuntos de${\displaystyle E}$define los conjuntos independientes de un matroide. Se denomina matroide libre sobre${\displaystyle E}$.

Dejar${\displaystyle E}$sea ​​un conjunto finito y${\displaystyle k}$un número natural . Se puede definir un matroide en${\displaystyle E}$tomando cada${\displaystyle k}$subconjunto de elementos de${\displaystyle E}$ser una base. Esto se conoce como el matroide uniforme de rango${\displaystyle k}$. Un matroide uniforme con rango${\displaystyle k}$y con${\displaystyle n}$Los elementos se denotan${\displaystyle U_{k,n}}$. Todos los matroides uniformes de rango al menos 2 son simples (ver §  Términos adicionales ). El matroide uniforme de rango  2 en${\displaystyle n}$los puntos se llaman el${\displaystyle n}$ Línea de punto . Un matroide es uniforme si y solo si no tiene circuitos de tamaño menor que uno más el rango del matroide. Las sumas directas de matroides uniformes se denominan matroides de partición .

En el matroide uniforme${\displaystyle U_{0,n}}$, cada elemento es un bucle (un elemento que no pertenece a ningún conjunto independiente), y en el matroide uniforme${\displaystyle U_{n,n}}$, cada elemento es un coloop (un elemento que pertenece a todas las bases). La suma directa de matroides de estos dos tipos es un matroide de partición en el que cada elemento es un bucle o un coloop; se denomina matroide discreto . Una definición equivalente de un matroide discreto es un matroide en el que cada subconjunto propio y no vacío del conjunto base${\displaystyle E}$es un separador.

La teoría de los matroides se desarrolló principalmente a partir de un examen profundo de las propiedades de independencia y dimensión en los espacios vectoriales. Hay dos maneras de presentar los matroides definidos de esta forma:

Si${\displaystyle E}$es cualquier subconjunto finito de un espacio vectorial${\displaystyle V}$, entonces podemos definir un matroid${\displaystyle M}$en${\displaystyle E}$tomando los conjuntos independientes de${\displaystyle M}$ser los subconjuntos linealmente independientes de${\displaystyle E}$.

La validez de los axiomas de conjuntos independientes para este matroide se deduce del lema de intercambio de Steinitz .

Si${\displaystyle M}$es un matroide que se puede definir de esta manera, decimos el conjunto${\displaystyle E}$representa${\displaystyle M}$.

Los matroides de este tipo se denominan matroides vectoriales .

Un ejemplo importante de un matroide definido de esta manera es el matroide de Fano, un  matroide de rango tres derivado del plano de Fano , una geometría finita con siete puntos (los siete elementos del matroide) y siete líneas (los planos no triviales propios del matroide). Es un matroide lineal cuyos elementos pueden describirse como los siete puntos no nulos en un  espacio vectorial tridimensional sobre el cuerpo finito GF(2) . Sin embargo, no es posible proporcionar una representación similar para el matroide de Fano utilizando números reales en lugar de GF(2).

Una matriz${\displaystyle A}$con entradas en un campo da lugar a un matroid${\displaystyle M}$en su conjunto de columnas. Los conjuntos de columnas dependientes en el matroide son aquellos que son linealmente dependientes como vectores.

Este matroide se llama matroide columna de${\displaystyle A}$, y${\displaystyle A}$Se dice que representa${\displaystyle M}$.

Por ejemplo, el matroide de Fano se puede representar de esta manera como una matriz de 3 × 7 (0,1) . Los matroides columna son simplemente matroides vectoriales con otro nombre, pero a menudo hay razones para preferir la representación matricial. ^{[ b ]}   

Un matroide que es equivalente a un matroide vectorial, aunque puede presentarse de manera diferente, se llama representable o lineal .${\displaystyle M}$es equivalente a un matroide vectorial sobre un campo${\displaystyle F}$, entonces decimos${\displaystyle M}$es representable sobre${\displaystyle F}$; En particular,${\displaystyle M}$Un elemento es representable si puede representarse sobre los números reales. Por ejemplo, aunque un matroide gráfico (véase más abajo) se representa mediante un grafo, también puede representarse mediante vectores sobre cualquier cuerpo.

Un problema fundamental en la teoría de matroides es caracterizar los matroides que pueden representarse sobre un campo dado.${\displaystyle F;}$La conjetura de Rota describe una posible caracterización para todo cuerpo finito . Los principales resultados hasta ahora son caracterizaciones de matroides binarios (representables sobre GF(2)) debidas a Tutte (década de 1950), de matroides ternarios (representables sobre el  cuerpo de 3 elementos) debidas a Reid y Bixby, y por separado a Seymour (década de 1970), y de matroides cuaternarios (representables sobre el cuerpo de 4  elementos) debidas a Geelen, Gerards y Kapoor (2000) . Geelen, Gerards y Whittle anunciaron una demostración de la conjetura de Rota en 2014, pero no la publicaron. ^{[ 7 ]}

Un matroide regular es un matroide que puede representarse sobre todos los campos posibles. El matroide Vámos es el ejemplo más simple de un matroide que no puede representarse sobre ningún campo.

Una segunda fuente original para la teoría de los matroides es la teoría de grafos .

Todo grafo finito (o multigrafo )${\displaystyle G}$da lugar a un matroide${\displaystyle M(G)}$de la siguiente manera: tome como${\displaystyle E}$el conjunto de todas las aristas en${\displaystyle G}$y consideremos un conjunto de aristas independiente si y solo si es un bosque ; es decir, si no contiene un ciclo simple . Entonces${\displaystyle M(G)}$se llama matroide cíclico . Los matroides derivados de esta manera son matroides gráficos . No todos los matroides son gráficos, pero todos los matroides de tres elementos son gráficos. ^{[ 8 ]} Todo matroide gráfico es regular.

Posteriormente se descubrieron otros matroides en grafos:

• El matroide bicircular de un grafo se define diciendo que un conjunto de aristas es independiente si cada subconjunto conectado contiene como máximo un ciclo, es decir, un conjunto de aristas es independiente si y solo si es un pseudobosque .

• En cualquier grafo dirigido o no dirigido${\displaystyle G}$dejar${\displaystyle E}$y${\displaystyle F}$sean dos conjuntos distintos de vértices. En el conjunto${\displaystyle E}$, definir un subconjunto${\displaystyle U}$ser independiente si hay${\displaystyle |U|}$caminos disjuntos en vértices desde${\displaystyle F}$sobre${\displaystyle U}$. Esto define un matroide en${\displaystyle E}$llamado gamoide : ^{[ 9 ]} un gamoide estricto es aquel para el cual el conjunto${\displaystyle E}$es el conjunto completo de vértices de${\displaystyle G}$. ^{[ 10 ]}

• En un grafo bipartito${\displaystyle G=(U,V,E)}$, se puede formar un matroide en el que los elementos son vértices en un lado${\displaystyle U}$de la bipartición, y los subconjuntos independientes son conjuntos de puntos finales de emparejamientos del grafo. Esto se denomina matroide transversal , ^{[ 11 ] [ 12 ]} y es un caso especial de gammoide. ^{[ 9 ]} Los matroides transversales son los matroides duales de los gammoides estrictos. ^{[ 10 ]}

• Los matroides gráficos se han generalizado a matroides a partir de grafos con signo , grafos de ganancia y grafos sesgados . Un grafo${\displaystyle G}$con una clase lineal distinguida${\displaystyle {\mathcal {B}}}$de ciclos, conocido como "grafo sesgado"${\displaystyle (G,{\mathcal {B}})}$, tiene dos matroides, conocidos como el matroide de marco y el matroide de elevación del grafo sesgado.

Si cada ciclo pertenece a la clase distinguida, estos matroides coinciden con el matroide de ciclo de${\displaystyle G}$. Si no se distingue ningún ciclo, la matroide marco es la matroide bicircular de${\displaystyle G}$Un grafo con signos, cuyas aristas están etiquetadas con signos, y un grafo de ganancia, que es un grafo cuyas aristas están etiquetadas de forma orientable a partir de un grupo, dan lugar cada uno a un grafo sesgado y, por lo tanto, tienen matroides de marco y de elevación.

• Los gráficos de Laman forman las bases del matroide de rigidez bidimensional , un matroide definido en la teoría de la rigidez estructural .

• Dejar${\displaystyle G}$ser un grafo conectado y${\displaystyle E}$sea ​​su conjunto de bordes. Deje${\displaystyle I}$ser la colección de subconjuntos${\displaystyle F}$de${\displaystyle E}$de tal manera que${\displaystyle G-F}$sigue conectado.${\displaystyle M^{*}(G)}$, cuyo conjunto de elementos es${\displaystyle E}$y con${\displaystyle I}$como su clase de conjuntos independientes, es un matroide llamado matroide de enlace de${\displaystyle G}$.

La función de rango${\displaystyle r(F)}$es el número ciclomático del subgrafo inducido en el subconjunto de aristas${\displaystyle F}$, que es igual al número de aristas fuera de un bosque máximo de ese subgrafo, y también al número de ciclos independientes en él.

Una tercera fuente original de la teoría de los matroides es la teoría de campos .

Una extensión de un campo da lugar a un matroide:

Suponer${\displaystyle F}$y${\displaystyle K}$son campos con${\displaystyle K}$que contiene${\displaystyle F}$. Dejar${\displaystyle E}$sea ​​cualquier subconjunto finito de${\displaystyle K}$.

Defina un subconjunto${\displaystyle S}$de${\displaystyle E}$ser algebraicamente independiente si el campo de extensión${\displaystyle F(S)}$tiene un grado de trascendencia igual a${\displaystyle |S|}$. ^{[ 13 ]}

Un matroide equivalente a un matroide de este tipo se denomina matroide algebraico . ^{[ 14 ]} El problema de caracterizar los matroides algebraicos es extremadamente difícil; se sabe poco al respecto. El matroide de Vámos proporciona un ejemplo de un matroide que no es algebraico.

Si${\displaystyle M}$Si se trata de un matroide finito, podemos definir el matroide ortogonal o dual.${\displaystyle M^{*}}$tomando el mismo conjunto subyacente y llamando a un conjunto una base en${\displaystyle M^{*}}$si y solo si su complemento es una base en${\displaystyle M}$No es difícil verificar que${\displaystyle M^{*}}$es un matroide y que el dual de${\displaystyle M^{*}}$es${\displaystyle M}$. ^{[ 15 ]}

El dual puede describirse igualmente bien en términos de otras formas de definir un matroide. Por ejemplo:

• Un conjunto es independiente en${\displaystyle M^{*}}$si y solo si su complemento abarca${\displaystyle M}$.

• Un conjunto es un circuito de${\displaystyle M^{*}}$si y solo si su complemento es un coatom en${\displaystyle M}$.

• La función de rango del dual es${\displaystyle r^{*}(S)=|S|-r(M)+r\left(E\smallsetminus S\right)}$.

Según una versión matroide del teorema de Kuratowski , el dual de una matroide gráfica${\displaystyle M}$es un matroide gráfico si y solo si${\displaystyle M}$es el matroide de un grafo planar . En este caso, el dual de${\displaystyle M}$es el matroide del grafo dual de${\displaystyle G}$. ^{[ 16 ]} El dual de un matroide vectorial representable sobre un campo particular${\displaystyle F}$También es representable sobre${\displaystyle F}$El dual de un matroide transversal es un gammoide estricto y viceversa.

Ejemplo

El matroide cíclico de un grafo es el matroide dual de su matroide de enlaces.

Si M es un matroide con conjunto de elementos E , y S es un subconjunto de E , la restricción de M a S , escrita M  | S , es el matroide sobre el conjunto S cuyos conjuntos independientes son los conjuntos independientes de M que están contenidos en S. Sus circuitos son los circuitos de M que están contenidos en S y su función de rango es la de M restringida a subconjuntos de S.

En álgebra lineal, esto corresponde a restringir al subespacio generado por los vectores en S. De forma equivalente, si T = M − S, esto puede denominarse eliminación de T , escrita M \ T o M − T. Los submatroides de M son precisamente el resultado de una secuencia de eliminaciones: el orden es irrelevante. ^{[ 17 ] [ 18 ]}

La operación dual de restricción es la contracción. ^{[ 19 ]} Si T es un subconjunto de E , la contracción de M por T , escrita M / T , es el matroide en el conjunto subyacente E − T cuya función de rango es  ${\displaystyle r'(A)=r(A\cup T)-r(T)}$. ^{[ 20 ]} En álgebra lineal, esto corresponde a observar el espacio cociente mediante el espacio lineal generado por los vectores en T , junto con las imágenes de los vectores en E  − T . 

Un matroide N que se obtiene de M mediante una secuencia de operaciones de restricción y contracción se llama menor de M. ^{[ 18 ] [ 21 ]} Decimos que M contiene a N como menor . Muchas familias importantes de matroides pueden caracterizarse por los matroides menores mínimos que no pertenecen a la familia; estos se denominan menores prohibidos o excluidos . ^{[ 22 ]}

Sea M un matroide con un conjunto subyacente de elementos E , y sea N otro matroide sobre un conjunto subyacente F. La suma directa de los matroides M y N es el matroide cuyo conjunto subyacente es la unión disjunta de E y F , y cuyos conjuntos independientes son las uniones disjuntas de un conjunto independiente de M con un conjunto independiente de N.

La unión de M y N es el matroide cuyo conjunto subyacente es la unión (no la unión disjunta) de E y F , y cuyos conjuntos independientes son aquellos subconjuntos que son la unión de un conjunto independiente en M y uno en N. Generalmente, el término "unión" se aplica cuando E = F , pero esta suposición no es esencial. Si E y F son disjuntos, la unión es la suma directa.

El polinomio característico de M – a veces llamado polinomio cromático , ^{[ 32 ]} aunque no cuenta coloraciones – se define como

${\displaystyle p_{M}(\lambda ):=\sum _{S\subseteq E}(-1)^{|S|}\lambda ^{r(E)-r(S)},}$

o equivalentemente (siempre que el conjunto vacío sea cerrado en M ) como

${\displaystyle p_{M}(\lambda ):=\sum _{A}\mu (\emptyset ,A)\lambda ^{r(E)-r(A)},}$

donde μ denota la función de Möbius de la red geométrica del matroide y la suma se toma sobre todos los planos A del matroide. ^{[ 33 ]}

• Cuando M es el matroide cíclico M ( G ) de un grafo G , el polinomio característico es una ligera transformación del polinomio cromático , que viene dado por χ _G  (λ) = λ ^c p _{M ( G )}  ( λ ), donde c es el número de componentes conexas de G .

• Cuando M es el matroide de enlace M *( G ) de un grafo G , el polinomio característico es igual al polinomio de flujo de G .

• Cuando M es el matroide M ( A ) de una disposición A de hiperplanos lineales en${\displaystyle \mathbb {R} ^{n}}$(o F ⁿ donde F es cualquier campo), el polinomio característico de la disposición viene dado por p _A  ( λ ) = λ ^{n − r ( M )} p _M  ( λ ).

Los números Whitney del primer tipo de${\displaystyle M}$son los coeficientes de las potencias de${\displaystyle \lambda }$en el polinomio característico. Específicamente, el${\displaystyle i}$número Whitney${\displaystyle w_{i}(M)}$es el coeficiente de${\displaystyle \lambda ^{r(M)-i}}$y es la suma de los valores de la función de Möbius:

${\displaystyle w_{i}(M)=\sum \{\mu (\emptyset ,A):r(A)=i\},}$

sumados sobre pisos del rango correcto. Estos números alternan en signo, de modo que${\displaystyle (-1)^{i}w_{i}(M)>0}$para${\displaystyle 0\leq i\leq r(M)}$.

Los números Whitney del segundo tipo de${\displaystyle M}$son los números de pisos de cada rango. Es decir,${\displaystyle W_{i}(M)}$es el número de rango ${\displaystyle i}$pisos.

Los números de Whitney de ambos tipos generalizan los números de Stirling de primer y segundo tipo, que son los números de Whitney del matroide cíclico del grafo completo y, equivalentemente, del retículo de partición . Gian-Carlo Rota les dio su nombre en honor a Hassler Whitney , cofundador de la teoría de matroides . El nombre se ha extendido a números similares para conjuntos parcialmente ordenados con rango finito .

El polinomio de Tutte de un matroide,${\displaystyle T_{M}(x,y)}$generaliza el polinomio característico a dos variables. Esto le otorga más interpretaciones combinatorias y también le confiere la propiedad de dualidad.

${\displaystyle T_{M^{*}}(x,y)=T_{M}(y,x),}$

lo que implica una serie de dualidades entre propiedades de${\displaystyle M}$y propiedades de${\displaystyle M^{*}}$Una definición del polinomio de Tutte es:

${\displaystyle T_{M}(x,y)=\sum _{S\subseteq E}(x-1)^{r(M)-r(S)}\ (y-1)^{|S|-r(S)}.}$

Esto expresa el polinomio de Tutte como una evaluación del polinomio generador de rango-nulidad de co- rango , ^{[ 36 ]}

${\displaystyle R_{M}(u,v)=\sum _{S\subseteq E}u^{r(M)-r(S)}v^{|S|-r(S)}.}$

A partir de esta definición es fácil ver que el polinomio característico es, salvo un factor simple, una evaluación de${\displaystyle T_{M}}$, específicamente,

${\displaystyle p_{M}(\lambda )=(-1)^{r(M)}T_{M}(1-\lambda ,0).}$

Otra definición se basa en actividades internas y externas y en una suma sobre bases, lo que refleja el hecho de que${\displaystyle T(1,1)}$es el número de bases. ^{[ 37 ]} Esta, que suma sobre menos subconjuntos pero tiene términos más complicados, fue la definición original de Tutte.

Existe una definición adicional en términos de recursión por eliminación y contracción. ^{[ 38 ]} La identidad de eliminación-contracción es

${\displaystyle F(M)=F(M-e)+F(M/e)}$

cuando${\displaystyle e}$no es ni un bucle ni un coloop. Un invariante de matroides (es decir, una función que toma el mismo valor en matroides isomorfos) que satisface esta recursión y la condición multiplicativa.

${\displaystyle F(M\oplus M')=F(M)F(M')}$

Se dice que es un invariante de Tutte-Grothendieck . ^{[ 36 ]} El polinomio de Tutte es el invariante más general de este tipo; es decir, el polinomio de Tutte es un invariante de Tutte-Grothendieck y todo invariante de este tipo es una evaluación del polinomio de Tutte. ^{[ 32 ]}

El polinomio de Tutte${\displaystyle T_{G}}$de un gráfico es el polinomio de Tutte${\displaystyle T_{M(G)}}$de su ciclo matroide.