Matroide

Abstracción de la independencia lineal de los vectores

En combinatoria , una rama de las matemáticas , un matroide / ˈm eɪ t r ɔɪ d / es una estructura que abstrae y generaliza la noción de independencia lineal en espacios vectoriales . Hay muchas formas equivalentes de definir un matroide axiomáticamente , siendo las más significativas en términos de: conjuntos independientes; bases o circuitos; funciones de rango; operadores de clausura; y conjuntos cerrados o planos . En el lenguaje de los conjuntos parcialmente ordenados , un matroide simple finito es equivalente a una red geométrica .

La teoría de matroides toma prestados muchos términos de los utilizados tanto en el álgebra lineal como en la teoría de grafos , en gran medida porque es la abstracción de varias nociones de importancia central en estos campos. Los matroides han encontrado aplicaciones en geometría , topología , optimización combinatoria , teoría de redes y teoría de codificación . ^{[1] [2]}

Definición

Hay muchas formas equivalentes de definir un matroide (finito). ^[a]

Conjuntos independientes

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

• (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 si entonces Esto a veces se denomina propiedad hereditaria o propiedad cerrada hacia abajo . ${\displaystyle A'\subseteq A\subseteq E\ ,}$ ${\displaystyle A\in {\mathcal {I}}}$ ${\displaystyle A'\in {\mathcal {I}}~.}$

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

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

Bases y circuitos

Un subconjunto del conjunto base que no es independiente se denomina dependiente . Un conjunto independiente máximo, es decir, un conjunto independiente que se vuelve dependiente al agregar cualquier elemento de , se denomina base para el matroide. Un circuito en un matroide es un subconjunto dependiente mínimo de , 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. ^[3] ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle M}$ ${\displaystyle E}$

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 como un par , donde es un conjunto finito como antes y es una colección de subconjuntos de llamados bases , con las siguientes propiedades: ^[3] ${\displaystyle M}$ ${\displaystyle (E,{\mathcal {B}})}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle E,}$

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

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

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

Funciones de rango

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

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

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

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

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

Estas propiedades se pueden utilizar como una de las definiciones alternativas de un matroide finito: Si satisface estas propiedades, entonces los conjuntos independientes de un matroide sobre se pueden definir como aquellos subconjuntos de con En el lenguaje de los conjuntos parcialmente ordenados , dicha estructura de matroide es equivalente a la red geométrica cuyos elementos son los subconjuntos parcialmente ordenados por inclusión. ${\displaystyle (E,r)}$ ${\displaystyle E}$ ${\displaystyle A}$ ${\displaystyle E}$ ${\displaystyle r(A)=|A|~.}$ ${\displaystyle A\subset M\ ,}$

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

Operadores de cierre

Sea un matroide en un conjunto finito , con función de rango como la anterior. La clausura o extensión de un subconjunto de es el conjunto ${\displaystyle M}$ ${\displaystyle E\ }$ ${\displaystyle r}$ ${\displaystyle \operatorname {cl} (A)}$ ${\displaystyle A}$ ${\displaystyle E}$

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

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

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

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

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

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

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

Pisos

Un conjunto cuyo cierre es igual a sí mismo se dice que es cerrado , o un plano o subespacio del matroide. ^[4] Un conjunto es cerrado si es máximo para su rango, lo que significa que la adición de cualquier otro elemento al conjunto aumentaría el rango. Los conjuntos cerrados de un matroide se caracterizan por una propiedad de partición de recubrimiento:

• (F1) Todo el conjunto de puntos está cerrado. ${\displaystyle E}$

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

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

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

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

Los planos de este matroide corresponden uno a uno con los elementos de la red; el plano correspondiente al elemento de la red es el conjunto ${\displaystyle y}$

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

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

Hiperplanos

En un matroide de rango, un plano de rango se denomina hiperplano . (Los hiperplanos también se denominan 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 de todos los elementos del matroide. Una definición equivalente es que un coátomo es un subconjunto de E que no genera M , pero tal que al agregarle cualquier otro elemento se forma un conjunto generador. ^[5] ${\displaystyle r\ ,}$ ${\displaystyle r-1}$ ${\displaystyle E}$

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

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

• (H2) Para cada y distinto con existe con ${\displaystyle x\in E}$ ${\displaystyle Y,Z\in {\mathcal {H}}}$ ${\displaystyle x\notin Y\cup Z\ ,}$ ${\displaystyle X\in {\mathcal {H}}}$ ${\displaystyle (Y\cap Z)\cup \{x\}\subseteq X~.}$

Grafoides

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

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

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

• (G3) ningún conjunto en y el conjunto en se intersecan exactamente en un elemento, y ${\displaystyle C}$ ${\displaystyle D}$

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

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

Ejemplos

Matroide libre

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

Matroides uniformes

Sea un conjunto finito y un número natural . Se puede definir un matroide en tomando cada subconjunto de elementos de como una base. Esto se conoce como el matroide uniforme de rango Un matroide uniforme con rango y con elementos se denota Todos los matroides uniformes de rango al menos 2 son simples (ver § Términos adicionales). El matroide uniforme de rango 2 en puntos se llama línea de puntos . 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 llaman matroides de partición . ${\displaystyle E}$ ${\displaystyle k}$ ${\displaystyle E}$ ${\displaystyle k}$ ${\displaystyle E}$ ${\displaystyle k~.}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle U_{k,n}~.}$ ${\displaystyle n}$ ${\displaystyle n}$ 

En el matroide uniforme cada elemento es un bucle (un elemento que no pertenece a ningún conjunto independiente), y en el matroide uniforme 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 llama matroide discreto . Una definición equivalente de un matroide discreto es un matroide en el que cada subconjunto propio, no vacío, del conjunto base es un separador. ${\displaystyle U_{0,n}\ ,}$ ${\displaystyle U_{n,n}\ ,}$ ${\displaystyle E}$

Matroides del álgebra lineal

El matroide de Fano, derivado del plano de Fano , es lineal en GF(2), pero no lineal en realidad.

El matroide Vámos , no lineal sobre ningún campo

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

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

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

Si es un matroide que se puede definir de esta manera, decimos que el conjunto representa ${\displaystyle M}$ ${\displaystyle E}$ ${\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 distintos de cero 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 los números reales en lugar de GF(2).

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

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

Por ejemplo, la matroide de Fano se puede representar de esta manera como una matriz de 3 × 7 (0,1) . Las matroides de 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 forma diferente, se llama representable o lineal . Si es equivalente a un matroide vectorial sobre un cuerpo , entonces decimos que es representable sobre ; en particular, es representable real si es representable sobre los números reales. Por ejemplo, aunque un matroide gráfico (ver más abajo) se presenta en términos de un grafo, también es representable por vectores sobre cualquier cuerpo. ${\displaystyle M}$ ${\displaystyle F}$ ${\displaystyle M}$ ${\displaystyle F}$ ${\displaystyle M}$

Un problema básico en la teoría de matroides es caracterizar los matroides que pueden representarse sobre un cuerpo dado ; la conjetura de Rota describe una caracterización posible para cada cuerpo finito . Los principales resultados hasta ahora son caracterizaciones de matroides binarios (aquellos representables sobre GF(2)) debido a Tutte (1950s), de matroides ternarios (representables sobre el cuerpo de 3 elementos) debido a Reid y Bixby, y por separado a Seymour (1970s), y de matroides cuaternarios (representables sobre el cuerpo de 4 elementos) debido a Geelen, Gerards y Kapoor (2000). Una prueba de la conjetura de Rota fue anunciada, pero no publicada, en 2014 por Geelen, Gerards y Whittle. ^[6] ${\displaystyle F}$

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

Matroides de la teoría de grafos

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

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

Posteriormente se descubrieron otros matroides en gráficos:

• El matroide bicircular de un grafo se define llamando independiente a un conjunto de aristas si cada subconjunto conexo contiene como máximo un ciclo.

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

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

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

Si cada ciclo pertenece a la clase distinguida, estas matroides coinciden con la matroide del ciclo de . Si no se distingue ningún ciclo, la matroide de marco es la matroide bicircular de Un grafo con signo, cuyos bordes están etiquetados por signos, y un grafo de ganancia, que es un grafo cuyos bordes están etiquetados de manera orientable a partir de un grupo, dan lugar cada uno a un grafo sesgado y, por lo tanto, tienen matroides de marco y de sustentación. ${\displaystyle G}$ ${\displaystyle G~.}$

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

• Sea un grafo conexo y sea su conjunto de aristas. Sea la colección de subconjuntos de tal que aún es conexo. Entonces cuyo conjunto de elementos es y con como su clase de conjuntos independientes, es un matroide llamado matroide de enlace de ${\displaystyle G}$ ${\displaystyle E}$ ${\displaystyle I}$ ${\displaystyle F}$ ${\displaystyle E}$ ${\displaystyle G-F}$ ${\displaystyle M^{*}(G)\ ,}$ ${\displaystyle E}$ ${\displaystyle I}$ ${\displaystyle G~.}$

La función de rango es el número ciclomático del subgrafo inducido en el subconjunto de aristas 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. ${\displaystyle r(F)}$ ${\displaystyle F\ ,}$

Matroides a partir de extensiones de campo

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

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

Supóngase que y son campos que contienen . Sea cualquier subconjunto finito de . ${\displaystyle F}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle F}$ ${\displaystyle E}$ ${\displaystyle K}$

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

Un matroide que es equivalente a un matroide de este tipo se llama matroide algebraico . ^[13] El problema de caracterizar los matroides algebraicos es extremadamente difícil; se sabe poco sobre él. El matroide Vámos proporciona un ejemplo de un matroide que no es algebraico.

Construcciones básicas

Existen algunas formas estándar de crear nuevos matroides a partir de los antiguos.

Dualidad

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

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

• Un conjunto es independiente si y sólo si su complemento abarca ${\displaystyle M^{*}}$ ${\displaystyle M~.}$

• Un conjunto es un circuito si y sólo si su complemento es un conjunto. ${\displaystyle M^{*}}$ ${\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 un matroide gráfico es un matroide gráfico si y solo si es el matroide de un grafo planar . En este caso, el dual de es el matroide del grafo dual de ^[15] El dual de un matroide vectorial representable sobre un campo particular también es representable sobre El dual de un matroide transversal es un gammoide estricto y viceversa. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle G~.}$ ${\displaystyle F}$ ${\displaystyle F~.}$

Ejemplo

El matroide de ciclo de un grafo es el matroide dual de su matroide de enlace.

Menores de edad

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 en 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 manera equivalente, si T = M − S esto puede denominarse la eliminación de T , escrita M \ T o M − T . Los submatroides de M son precisamente los resultados de una secuencia de eliminaciones: el orden es irrelevante. ^{[16] [17]}

La operación dual de restricción es la contracción. ^[18] 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 ^[19] En álgebra lineal, esto corresponde a mirar el espacio cociente por el espacio lineal generado por los vectores en T , junto con las imágenes de los vectores en E - T . ${\displaystyle r'(A)=r(A\cup T)-r(T).}$

Un matroide N que se obtiene a partir de M mediante una secuencia de operaciones de restricción y contracción se denomina menor de M. ^{[17] [20]} 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 . ^[21]

Sumas y uniones

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 esa suposición no es esencial. Si E y F son disjuntos, la unión es la suma directa.

Términos adicionales

Sea M un matroide con un conjunto subyacente de elementos E.

• E puede llamarse el conjunto fundamental de M . Sus elementos pueden llamarse los puntos de M .

• Un subconjunto de E abarca M si su clausura es E . Se dice que un conjunto abarca un conjunto cerrado K si su clausura es K .

• La circunferencia de un matroide es el tamaño de su circuito más pequeño o conjunto dependiente.

• Un elemento que forma un circuito de un solo elemento de M se llama bucle . De manera equivalente, un elemento es un bucle si no pertenece a ninguna base. ^{[7] [22]}

• Un elemento que no pertenece a ningún circuito se llama coloop o istmo . De manera equivalente, un elemento es un coloop si pertenece a todas las bases.

Los bucles y los coloops son mutuamente duales. ^[22]

• Si un conjunto de dos elementos { f, g } es un circuito de M , entonces f y g son paralelos en M . ^[7]

• Un matroide se denomina simple si no tiene circuitos que consten de 1 o 2 elementos. Es decir, no tiene bucles ni elementos paralelos. También se utiliza el término geometría combinatoria . ^[7] Un matroide simple obtenido a partir de otro matroide M eliminando todos los bucles y eliminando un elemento de cada circuito de 2 elementos hasta que no queden circuitos de 2 elementos se denomina simplificación de M. ^[23] Un matroide es co-simple si su matroide dual es simple. [ ^24]

• A la unión de circuitos a veces se la denomina ciclo de M. Por lo tanto, un ciclo es el complemento de un plano del matroide dual. (Este uso entra en conflicto con el significado común de "ciclo" en la teoría de grafos).

• Un separador de M es un subconjunto S de E tal que . Un separador propio o no trivial es un separador que no es ni E ni el conjunto vacío. ^[25] Un separador irreducible es un separador no vacío que no contiene ningún otro separador no vacío. Los separadores irreducibles particionan el conjunto base E . ${\displaystyle r(S)+r(E-S)=r(M)}$

• Un matroide que no puede escribirse como la suma directa de dos matroides no vacías, o equivalentemente que no tiene separadores propios, se llama conexo o irreducible . Un matroide es conexo si y solo si su dual es conexo. ^[26]

• Un submatroide irreducible máximo de M se denomina componente de M. Un componente es la restricción de M a un separador irreducible y, a la inversa, la restricción de M a un separador irreducible es un componente. Un separador es una unión de componentes. ^[25]

• Un matroide M se denomina matroide de marco si él, o un matroide que lo contiene, tiene una base tal que todos los puntos de M están contenidos en las líneas que unen pares de elementos de base. ^[27]

• Un matroide se denomina matroide de pavimentación si todos sus circuitos tienen un tamaño al menos igual a su rango. ^[28]

• El politopo matroide es la envoltura convexa de los vectores indicadores de las bases de . ${\displaystyle P_{M}}$ ${\displaystyle M}$

Algoritmos

En cada matroide se pueden resolver de manera eficiente varios problemas importantes de optimización combinatoria. En particular:

• La búsqueda de un conjunto independiente de peso máximo en un matroide ponderado se puede resolver mediante un algoritmo voraz . Este hecho puede incluso utilizarse para caracterizar matroides: si una familia F de conjuntos, cerrada tomando subconjuntos, tiene la propiedad de que, sin importar cómo se ponderen los conjuntos, el algoritmo voraz encuentra un conjunto de peso máximo en la familia, entonces F debe ser la familia de conjuntos independientes de un matroide. ^[29]

• El problema de partición de un matroide consiste en dividir los elementos de un matroide en la menor cantidad posible de conjuntos independientes, y el problema de empaquetamiento de un matroide consiste en encontrar la mayor cantidad posible de conjuntos generadores disjuntos. Ambos pueden resolverse en tiempo polinómico y pueden generalizarse al problema de calcular el rango o encontrar un conjunto independiente en una suma de matroides.

• Una intersección matroide de dos o más matroides en el mismo conjunto base es la familia de conjuntos que son simultáneamente independientes en cada uno de los matroides. El problema de encontrar el conjunto más grande, o el conjunto ponderado máximo, en la intersección de dos matroides se puede encontrar en tiempo polinomial y proporciona una solución a muchos otros problemas importantes de optimización combinatoria. Por ejemplo, la coincidencia máxima en grafos bipartitos se puede expresar como un problema de intersección de dos matroides de partición . Sin embargo, encontrar el conjunto más grande en una intersección de tres o más matroides es NP-completo .

Software Matroid

Dos sistemas independientes para realizar cálculos con matroides son Oid de Kingan y Macek de Hlineny. Ambos son paquetes de código abierto. "Oid" es un sistema de software interactivo y extensible para experimentar con matroides. "Macek" es un sistema de software especializado con herramientas y rutinas para realizar cálculos combinatorios razonablemente eficientes con matroides representables.

Ambos sistemas de software matemático de código abierto, SAGE y Macaulay2, contienen paquetes de matroides. Maple tiene un paquete para trabajar con matroides desde la versión 2024. ^[30]

Invariantes polinomiales

Hay dos polinomios especialmente significativos asociados a un matroide finito M en el conjunto base E. Cada uno es un matroide invariante , lo que significa que los matroides isomorfos tienen el mismo polinomio.

Polinomio característico

El polinomio característico de M –a veces llamado polinomio cromático , ^[31] 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 esté 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. ^[32]

• 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 dada por χ _G  (λ) = λ ^c p _{M ( G )}  (λ), donde c es el número de componentes conexos 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 un arreglo A de hiperplanos lineales en ℝ ⁿ (o F ⁿ donde F es cualquier cuerpo), el polinomio característico del arreglo está dado por p _A  (λ) = λ ^{n − r ( M )} p _M  (λ).

Invariante beta

El invariante beta de un matroide, introducido por Crapo (1967), puede expresarse en términos del polinomio característico como una evaluación de la derivada ^[33] ${\displaystyle p}$

${\displaystyle \beta (M)=(-1)^{r(M)-1}p_{M}'(1)}$

o directamente como ^[34]

${\displaystyle \beta (M)=(-1)^{r(M)}\sum _{X\subseteq E}(-1)^{|X|}r(X)~.}$

El invariante beta no es negativo y es cero si y solo si está desconectado, o vacío, o es un bucle. De lo contrario, depende solo de la red de planos de Si no tiene bucles ni coloops, entonces ^[34] ${\displaystyle M}$ ${\displaystyle M~.}$ ${\displaystyle M}$ ${\displaystyle \beta (M)=\beta (M^{*})~.}$

Números de Whitney

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

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

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

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

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 de ciclo del grafo completo y, equivalentemente, del retículo de partición . Recibieron el nombre de Hassler Whitney , el (co)fundador de la teoría de matroides, por Gian-Carlo Rota . El nombre se ha extendido a los números similares para conjuntos parcialmente ordenados de rango finito .

Polinomio de Tutte

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

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

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

${\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 de co-rango-nulidad o generador de rango , ^[35]

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

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

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

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

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

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

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

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

se dice que es un invariante de Tutte-Grothendieck . ^[35] El polinomio de Tutte es el invariante más general; es decir, el polinomio de Tutte es un invariante de Tutte-Grothendieck y cada invariante de este tipo es una evaluación del polinomio de Tutte. ^[31]

El polinomio de Tutte de un grafo es el polinomio de Tutte de su matroide cíclico. ${\displaystyle T_{G}}$ ${\displaystyle T_{M(G)}}$

Matroides infinitos

La teoría de los matroides infinitos es mucho más complicada que la de los matroides finitos y constituye un tema en sí misma. Durante mucho tiempo, una de las dificultades ha sido que existían muchas definiciones razonables y útiles, ninguna de las cuales parecía captar todos los aspectos importantes de la teoría de los matroides finitos. Por ejemplo, parecía difícil reunir bases, circuitos y dualidad en una sola noción de matroides infinitos.

La definición más simple de un matroide infinito es requerir un rango finito ; es decir, el rango de E es finito. Esta teoría es similar a la de los matroides finitos excepto por la falla de la dualidad debido al hecho de que el dual de un matroide infinito de rango finito no tiene rango finito. Los matroides de rango finito incluyen cualquier subconjunto de espacios vectoriales de dimensión finita y de extensiones de campo de grado de trascendencia finito .

La siguiente generalización infinita más simple son los matroides finitarios, también conocidos como pregeometrías . Un matroide con un conjunto base posiblemente infinito es finitario si tiene la propiedad de que

${\displaystyle x\in \operatorname {cl} (Y)\ \Leftrightarrow \ {\text{ there is a finite set }}Y'\subseteq Y{\text{ such that }}x\in \operatorname {cl} (Y').}$

Equivalentemente, cada conjunto dependiente contiene un conjunto dependiente finito.

Ejemplos de ello son la dependencia lineal de subconjuntos arbitrarios de espacios vectoriales de dimensión infinita (pero no dependencias infinitas como en los espacios de Hilbert y Banach ), y la dependencia algebraica en subconjuntos arbitrarios de extensiones de campo con un grado de trascendencia posiblemente infinito. Nuevamente, la clase de matroide finitario no es autodual, porque el dual de un matroide finitario no es finitario.

Los matroides infinitos finitarios se estudian en la teoría de modelos , una rama de la lógica matemática con fuertes vínculos con el álgebra .

A finales de los años 1960, los teóricos de las matroides pidieron una noción más general que compartiera los diferentes aspectos de las matroides finitas y generalizara su dualidad. Se definieron muchas nociones de matroides infinitas en respuesta a este desafío, pero la cuestión permaneció abierta. Uno de los enfoques examinados por DA Higgs se conoció como B-matroides y fue estudiado por Higgs, Oxley y otros en los años 1960 y 1970. Según un resultado reciente de Bruhn et al. (2013), resuelve el problema: al llegar a la misma noción de forma independiente, proporcionaron cinco sistemas equivalentes de axiomas, en términos de independencia, bases, circuitos, cierre y rango. La dualidad de las B-matroides generaliza las dualidades que se pueden observar en grafos infinitos.

Los axiomas de independencia son los siguientes:

1. El conjunto vacío es independiente.
2. Cada subconjunto de un conjunto independiente es independiente.
3. Para cada conjunto independiente no máximo (bajo inclusión de conjuntos) y conjunto independiente máximo , existe tal que es independiente. ${\displaystyle \ I\ }$ ${\displaystyle \ J\ }$ ${\displaystyle \ x\in J\smallsetminus I\ }$ ${\displaystyle \ I\cup \{x\}\ }$
4. Para cada subconjunto del espacio base, cada subconjunto independiente de puede extenderse a un subconjunto independiente máximo de ${\displaystyle \ X\ }$ ${\displaystyle \ I\ }$ ${\displaystyle \ X\ }$ ${\displaystyle \ X~.}$

Con estos axiomas, cada matroide tiene un dual.

Historia

La teoría de los matroides fue introducida por Whitney (1935). También fue descubierta de forma independiente por Takeo Nakasawa , cuyo trabajo fue olvidado durante muchos años por Nishimura y Kuroda (2009).

En su artículo seminal, Whitney proporcionó dos axiomas para la independencia y definió cualquier estructura que se adhiera a estos axiomas como "matroides". ^[c] Su observación clave fue que estos axiomas proporcionan una abstracción de "independencia" que es común tanto a los grafos como a las matrices. Debido a esto, muchos de los términos utilizados en la teoría de matroides se parecen a los términos para sus conceptos análogos en álgebra lineal o teoría de grafos .

Casi inmediatamente después de que Whitney escribiera por primera vez sobre las matroides, MacLane (1936) escribió un importante artículo sobre la relación de las matroides con la geometría proyectiva . Un año después, van der Waerden (1937) señaló similitudes entre la dependencia algebraica y la lineal en su clásico libro de texto sobre Álgebra Moderna.

En la década de 1940, Richard Rado desarrolló una teoría adicional bajo el nombre de "sistemas de independencia" con la mirada puesta en la teoría transversal , donde su nombre para el tema se utiliza todavía a veces.

En la década de 1950, WT Tutte se convirtió en la figura más destacada de la teoría matroide, posición que mantuvo durante muchos años. Sus contribuciones fueron abundantes, entre ellas:

• La caracterización de matroides binarios , regulares y gráficos por menores excluidos.

• Teorema de representabilidad de los matroides regulares

• La teoría de los grupos de cadenas y sus matroides.

y las herramientas que utilizó para comprobar muchos de sus resultados:

• El "teorema del camino"

• " Teorema de homotopía de Tutte " (ver, por ejemplo, Tutte (1965))

que son tan complicadas que los teóricos posteriores se han tomado grandes molestias para eliminar su necesidad en las pruebas. ^[d]

Crapo (1969) y Brylawski (1972) generalizaron a las matroides el "dicromato" de Tutte, un polinomio gráfico que hoy se conoce como polinomio de Tutte (nombrado así por Crapo). Su trabajo ha sido seguido recientemente (especialmente en la década de 2000) por una avalancha de artículos, aunque no tantos como los que trataban sobre el polinomio de Tutte de un grafo.

En 1976 Dominic Welsh publicó el primer libro completo sobre la teoría de matroides.

El teorema de descomposición de Paul Seymour para matroides regulares (Seymour (1980)) fue el trabajo más significativo e influyente de finales de la década de 1970 y de la década de 1980. Otra contribución fundamental, de Kahn y Kung (1982), mostró por qué las geometrías proyectivas y las geometrías de Dowling juegan un papel tan importante en la teoría de matroides.

En la década de 1980 hubo muchos otros contribuyentes importantes, pero no se debe dejar de mencionar la extensión de Geoff Whittle a los matroides ternarios de la caracterización de Tutte de los matroides binarios que son representables sobre los racionales (Whittle 1995), tal vez la mayor contribución individual de la década de 1990.

En el período actual (desde alrededor del año 2000), el proyecto Matroid Minors de Geelen , Gerards, Whittle y otros ^[e] ha producido avances sustanciales en la teoría de la estructura de los matroides. Muchos otros también han contribuido a esa parte de la teoría de los matroides que (en la primera y segunda décadas del siglo XXI) está en pleno auge.

Investigadores

Los matemáticos que fueron pioneros en el estudio de las matroides incluyen

Susumu Kuroda ^[38]

Saunders MacLane

Richard Rado

Takeo Nakasawa

Hirokazu Nishimura ^[38]

WT todo

BL van der Waerden

Hassler Whitney

Algunos de los otros contribuyentes importantes son:

Jack Edmonds

Jim Geelen

Eugene Lawler

Laszlo Lovász

Gian-Carlo Rota

PD Seymour

Dominic Welsh

Notas al pie

1. Oxley (1992) es una fuente estándar para definiciones básicas y resultados sobre matroides; Welsh (1976) es una fuente estándar más antigua.
   Véase el apéndice de Brylawski en White (1986), págs. 298-302, para obtener una lista de sistemas de axiomas matroides que son equivalentes.

2. Hay una diferencia técnica: un matroide de columna puede tener elementos distintos que sean el mismo vector, pero un matroide de vector como el definido anteriormente no puede. Por lo general, esta diferencia es insignificante y se puede ignorar, pero al permitir que sea un multiconjunto de vectores, las dos definiciones coinciden por completo. ${\displaystyle E}$
3. Aunque tal vez estaba implícito, Whitney (1935) no incluyó un axioma que exigiera que al menos un subconjunto fuera independiente.

4. Un buen ejemplo es la prueba corta de AMH Gerards (Gerards (1989)) de la caracterización de Tutte de los matroides regulares.
5. El Proyecto Matroid Minors es un intento de duplicar, para matroides que se pueden representar sobre un campo finito, el éxito del Proyecto Robertson-Seymour Graph Minors (véase el teorema de Robertson-Seymour ).

Véase también

• Antimatroide  – Sistema matemático de ordenamientos o conjuntos con axioma de anticambio
• Matroide de Coxeter  : generalización de la teoría de grupos de matroides
• Greedoid  : sistema de conjuntos utilizado en la optimización voraz
• Matroide orientado  – Abstracción del álgebra lineal ordenada
• Polimatroide  : análogo multiconjunto de los matroides
• Pregeometría (teoría de modelos)  : formulación de matroides mediante operadores de cierre

Citas

1. Neel y Neudauer (2009)
2. Kashyap, Soljanin y Vontobel (2009)
3. Welsh (1976, págs. 7–9), Sección 1.2, "Sistemas axiomáticos para un matroide".
4. Welsh (1976, págs. 21-22), Sección 1.8, "Conjuntos cerrados = Planos = Subespacios".
5. Welsh (1976, págs. 38-39), Sección 2.2, "Los hiperplanos de un matroide".
6. "Resolución de la conjetura de Rota" (PDF) . Avisos de la American Mathematical Society : 736–743. 17 de agosto de 2014.
7. Oxley (1992), pág. 13
8. Oxley (1992), págs. 115
9. Oxley (1992), pág. 100
10. Oxley (1992), págs. 46-48
11. White (1987), págs. 72-97
12. Oxley (1992), pág. 215
13. Oxley (1992), pág. 216
14. Blanco (1986), pág. 32
15. Blanco (1986), pág. 105
16. Blanco (1986), pág. 131
17. White (1986), pág. 224
18. Blanco (1986), pág. 139
19. Blanco (1986), pág. 140
20. Blanco (1986), pág. 150
21. White (1986), págs. 146-147
22. White (1986), pág. 130
23. Oxley (1992), pág. 52
24. Oxley (1992), pág. 347
25. Oxley (1992), pág. 128
26. Blanco (1986), pág. 110
27. Zaslavski (1994)
28. Oxley (1992), pág. 26
29. Oxley (1992), pág. 64
30. "Los paquetes Matroids e Hypergraphs en Maple 2024" (PDF) . MapleSoft . Consultado el 19 de agosto de 2024 .
31. White (1987), pág. 127
32. Blanco (1987), pág. 120
33. Blanco (1987), pág. 123
34. White (1987), pág. 124
35. White (1987), pág. 126
36. Blanco (1992b), pág. 188
37. Blanco (1986), pág. 260
38. Nishimura y Kuroda (2009)

Referencias

• Bruhn, Henning; Diestel, Reinhard; Kriesell, Matthias; Pendavingh, Rudi; Wollan, Paul (2013). "Axiomas para matroides infinitos". Avances en Matemáticas . 239 : 18–46. arXiv : 1003.3919 . doi : 10.1016/j.aim.2013.01.011 . MR  3045140. S2CID  10436077.
• Bryant, Victor; Perfect, Hazel (1980). Teoría de la independencia en combinatoria . Londres, Reino Unido y Nueva York, NY: Chapman and Hall. ISBN 978-0-412-22430-0.
• Brylawski, Thomas H. (1972). "Una descomposición para geometrías combinatorias". Transactions of the American Mathematical Society . 171 : 235–282. doi : 10.2307/1996381 . JSTOR  1996381.
• Crapo, Henry H. (1969). "El polinomio de Tutte". Aecuaciones Mathematicae . 3 (3): 211–229. doi :10.1007/BF01817442. S2CID  119602825.
• Crapo, Henry H. ; Rota, Gian-Carlo (1970). Fundamentos de la teoría combinatoria: geometrías combinatorias. Cambridge, MA: MIT Press. ISBN 978-0-262-53016-3.MR  0290980 – vía Internet Archive ( archive.org).
• Edmonds, Jack (5–9 de marzo de 2001). "Funciones submodulares, matroides y ciertos poliedros". En Jünger, Michael; Reinelt, Gerhard; Rinaldi, Giovanni (eds.). Optimización combinatoria: ¡Eureka, te encoges!: artículos dedicados a Jack Edmonds . 5.º taller internacional. Lecture Notes in Computer Science. Vol. 2570 (edición revisada de artículos). Aussois, FR: Berlín, Heidelberg: Springer (publicado en 2003). págs. 11–26. CiteSeerX  10.1.1.454.4060 . doi :10.1007/3-540-36478-1_2. ISBN . 978-3-540-36478-8.
• Geelen, JF; Gerards, AMH; Kapoor, A. (2000). "Los menores excluidos para matroides GF(4)-representables". Journal of Combinatorial Theory . Serie B. 79 (2): 247–299. doi :10.1006/jctb.2000.1963. MR  1769191.
• Geelen, Jim ; Gerards, AMH; Whittle, Geoff (2007). "Hacia una teoría de la estructura matroide-menor". En Grimmett, Geoffrey; et al. (eds.). Combinatoria, complejidad y azar: un tributo a Dominic Welsh . Oxford Lecture Series in Mathematics and its Applications. Vol. 34. Oxford, Reino Unido: Oxford University Press. págs. 72–82.
• Gerards, AMH (1989). "Una breve prueba de la caracterización de Tutte de matrices totalmente unimodulares". Álgebra lineal y sus aplicaciones . 114–115: 207–212. doi : 10.1016/0024-3795(89)90461-8 .
• Kahn, Jeff; Kung, Joseph PS (1982). "Variedades de geometrías combinatorias". Transactions of the American Mathematical Society . 271 (2): 485–499. doi : 10.2307/1998894 . JSTOR  1998894.
• Kingan, Robert; Kingan, Sandra (2005). "Un sistema de software para matroides". Graphs and Discovery . Serie DIMACS en Matemáticas discretas y Ciencias de la computación teórica. págs. 287–296.
• Kashyap, Navin; Soljanin, Emina; Vontobel, Pascal (2009). Aplicaciones de la teoría de matroides y la optimización combinatoria a la teoría de la información y la codificación (PDF) (Informe) . Recuperado el 4 de octubre de 2014 – a través de www.birs.ca.
• Kung, Joseph PS, ed. (1986). Un libro de consulta sobre teoría de matroides. Boston, MA: Birkhäuser. doi :10.1007/978-1-4684-9199-9. ISBN 978-0-8176-3173-4.MR  0890330 – vía Internet Archive ( archive.org).
• MacLane, Saunders (1936). "Algunas interpretaciones de la dependencia lineal abstracta en términos de geometría proyectiva". American Journal of Mathematics . 58 (1): 236–240. doi :10.2307/2371070. JSTOR  2371070.
• Minty, George J. (1966). "Sobre los fundamentos axiomáticos de las teorías de grafos lineales dirigidos, redes eléctricas y programación de redes". Journal of Mathematics and Mechanics . 15 : 485–520. MR  0188102.
• Neel, David L.; Neudauer, Nancy A. (2009). "Matroides que has conocido" (PDF) . Revista de Matemáticas . 82 (1): 26–41. doi :10.4169/193009809x469020 . Consultado el 4 de octubre de 2014 – a través de la Asociación Matemática de América (maa.org).
• Nishimura, Hirokazu; Kuroda, Susumu, eds. (2009). Un matemático perdido, Takeo Nakasawa: el padre olvidado de la teoría matroide . Basilea, CH: Birkhäuser Verlag. doi :10.1007/978-3-7643-8573-6. ISBN 978-3-7643-8572-9.MR  2516551.Zbl 1163.01001  .​
• Oxley, James (1992). Matroid Theory . Oxford, Reino Unido: Oxford University Press. ISBN 978-0-19-853563-8.MR  1207587.Zbl 0784.05002  .​
• Recski, András (1989). Teoría de matroides y sus aplicaciones en la teoría de redes eléctricas y en la estática . Algoritmos y combinatoria. Vol. 6. Berlín, DE y Budapest, HU: Springer-Verlag y Akademiai Kiado. doi :10.1007/978-3-662-22143-3. ISBN 978-3-540-15285-9. MR  1027839. S2CID  117772439 – vía Internet Archive (archive.org).
• Sapozhenko, AA (2001) [1994]. "Matroid". Enciclopedia de Matemáticas . EMS Press .
• Seymour, Paul D. (1980). "Descomposición de matroides regulares". Journal of Combinatorial Theory . Serie B. 28 (3): 305–359. doi : 10.1016/0095-8956(80)90075-1 . hdl : 10338.dmlcz/101946 . Zbl  0443.05027.
• Truemper, Klaus (1992). Descomposición matroide. Boston, MA: Academic Press. ISBN 978-0-12-701225-4.MR 1170126 –  vía emis.de.
• Tutte, WT (1959). "Matroides y grafos". Transacciones de la American Mathematical Society . 90 (3): 527–552. doi : 10.2307/1993185 . JSTOR  1993185. MR  0101527.
• Tutte, WT (1965). "Conferencias sobre matroides". Revista de investigación de la Oficina Nacional de Normas . Sección B. 69 : 1–47.
• Tutte, WT (1971). Introducción a la teoría de matroides . Métodos analíticos y computacionales modernos en ciencia y matemáticas. Vol. 37. Nueva York, NY: American Elsevier Publishing Company. Zbl  0231.05027.
• Vámos, Peter (1978). "El axioma faltante de la teoría matroide se ha perdido para siempre". Journal of the London Mathematical Society . 18 (3): 403–408. doi :10.1112/jlms/s2-18.3.403.
• van der Waerden, BL (1937). Álgebra moderna .
• Welsh, DJA (1976). Matroid Theory . LMS Monographs. Vol. 8. Academic Press. ISBN. 978-0-12-744050-7.Zbl 0343.05002  .
• White, Neil, ed. (1986). Teoría de matroides . Enciclopedia de matemáticas y sus aplicaciones. Vol. 26. Cambridge, Reino Unido: Cambridge University Press. ISBN 978-0-521-30937-0. Zbl  0579.00001 - vía Internet Archive (archive.org).
• White, Neil, ed. (1987). Combinatorial Geometries . Enciclopedia de matemáticas y sus aplicaciones. Vol. 29. Cambridge, Reino Unido: Cambridge University Press . ISBN. 978-0-521-33339-9. Zbl  0626.00007 - vía Internet Archive (archive.org).
• White, Neil, ed. (1992a). Aplicaciones de Matroid . Enciclopedia de Matemáticas y sus Aplicaciones. Vol. 40. Cambridge, Reino Unido: Cambridge University Press. ISBN 978-0-521-38165-9. Zbl  0742.00052 - vía Internet Archive (archive.org).
• Whitney, Hassler (1935). "Sobre las propiedades abstractas de la dependencia lineal". American Journal of Mathematics . 57 (3): 509–533. doi :10.2307/2371182. hdl : 10338.dmlcz/100694 . JSTOR  2371182. MR  1507091.— Reimpreso en Kung (1986), págs. 55-79
• Whittle, Geoff (1995). "Una caracterización de los matroides representables sobre GF(3) y los racionales". Journal of Combinatorial Theory . Serie B. 65 (2): 222–261. doi : 10.1006/jctb.1995.1052 .
• Zaslavsky, Thomas (1994). "Matroides de trama y grafos sesgados". Eur. J. Comb. 15 (3): 303–307. doi : 10.1006/eujc.1994.1034 . ISSN  0195-6698. Zbl  0797.05027.

Enlaces externos

• "Matroid". Enciclopedia de Matemáticas . EMS Press . 2001 [1994].

• Kingan, Sandra. "Teoría de los matroides". userhome.brooklyn.cuny.edu (sitio personal académico). Brooklyn College . Brooklyn, NY: City University of New York .— Una amplia bibliografía de artículos sobre matroides, software sobre matroides y enlaces.

• Locke, SC "Algoritmos voraces". math.fau.edu (sitio personal académico). Boca Raton, FL: Florida Atlantic University .

• Pagano, Steven R. "Matroides y grafos con signo". math.binghamton.edu (sitio personal académico). Binghamton, NY: Binghamton University .

• Hubenthal, Mark. "Una breve mirada a las matroides" (PDF) . math.washington.edu (sitio personal académico). Seattle, WA: Universidad de Washington . Archivado desde el original (PDF) el 12 de agosto de 2010.—Da pruebas de las afirmaciones de este artículo.

• Oxley, James. "¿Qué es un matroide?" (PDF) . math.lsu.edu (sitio personal académico). Baton Rouge, LA: Universidad Estatal de Luisiana .

• White, Neil, ed. (1992b). Aplicaciones de Matroid. Cambridge University Press. ISBN 978-0-5213-8165-9. ISSN  0953-4806 – vía Google Books.