Matroide

Abstracción de la independencia lineal de vectores.

En combinatoria , una rama de las matemáticas , una 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 axiomáticamente una matroide , siendo la más significativa en términos de: conjuntos independientes; bases o circuitos; funciones de rango; operadores de cierre; y conjuntos cerrados o pisos . En el lenguaje de conjuntos parcialmente ordenados , una matroide simple finita es equivalente a una red geométrica .

La teoría matroide toma prestado ampliamente de los términos utilizados tanto en álgebra lineal como en teoría de grafos , en gran parte porque es la abstracción de varias nociones de importancia central en estos campos. Las 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 una matroide (finita). ^[a]

conjuntos independientes

En términos de independencia, una matroide finita es un par donde hay un conjunto finito (llamado conjunto básico ) y 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 de los que existen , 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\smallsetminus 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 fundamental que no es independiente se llama dependiente . Un conjunto independiente máximo, es decir, un conjunto independiente que se vuelve dependiente al agregar cualquier elemento de , se llama base de la matroide. Un circuito en una matroide es un subconjunto mínimo dependiente de , es decir, un conjunto dependiente cuyos subconjuntos propios son todos independientes. El término surge porque los circuitos de las matroides gráficas son ciclos en los gráficos correspondientes. ^[3] ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle M}$ ${\displaystyle E}$

Los conjuntos dependientes, las bases o los circuitos de una matroide caracterizan completamente a la matroide: un conjunto es independiente si y sólo si no es dependiente, si y sólo si es un subconjunto de una base, y si y sólo si lo es. no contiene un circuito. Cada una de las colecciones de conjuntos dependientes, de bases y de circuitos tiene propiedades simples que pueden tomarse como axiomas para una matroide. Por ejemplo, se puede definir una matroide como un par , donde es un conjunto finito como antes y es una colección de subconjuntos de bases llamadas , 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 base . De esta propiedad se deduce que ningún miembro de puede ser un subconjunto propio de otro. ${\displaystyle {\mathcal {B}}}$

Funciones de rango

Es un resultado básico de la teoría matroide, directamente análogo a un teorema de bases similar en álgebra lineal , que dos bases cualesquiera de una matroide tienen el mismo número de elementos. Este número se llama rango de Si es una matroide y es un subconjunto de , entonces una matroide se puede definir considerando que un subconjunto de es independiente si y sólo si es independiente en Esto nos permite hablar de submatroides y de el rango de cualquier subconjunto de El rango de un subconjunto viene dado por la función de rango de la 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 número 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 deduce 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 una matroide finita: Si satisface estas propiedades, entonces los conjuntos independientes de una matroide pueden definirse como aquellos subconjuntos de con En el lenguaje de conjuntos parcialmente ordenados , dicha estructura 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 para obtener un conjunto independiente. La nulidad de in 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 una matroide en un conjunto finito , con función de rango como la anterior. El cierre o lapso 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 potencias , 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 if then ${\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 primeras tres de estas propiedades son las propiedades definitorias de un operador de cierre. La cuarta a veces se denomina propiedad de intercambio Mac Lane - Steinitz . Estas propiedades pueden tomarse como otra definición de matroide: cada función que obedece a estas propiedades determina una matroide. ^[3] ${\displaystyle \operatorname {cl} :{\mathcal {P}}(E)\to {\mathcal {P}}(E)}$

Pisos

Se dice que un conjunto cuyo cierre es igual a sí mismo es cerrado , o un plano o subespacio de la 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 una matroide se caracterizan por una propiedad de partición de cobertura:

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

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

• (F3) Si es un piso, entonces cada elemento de está precisamente en uno de los pisos que cubre (lo que significa que contiene correctamente pero no hay ningún piso 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 pisos, parcialmente ordenada por inclusión de conjuntos, forma una red matroide . Por el contrario, 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 pisos de esta matroide se corresponden uno a uno con los elementos de la celosía; el plano correspondiente al elemento reticular es el conjunto ${\displaystyle y}$

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

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

Hiperplanos

En una matroide de rango, un piso de rango se llama hiperplano . (Los hiperplanos también se denominan coátomos o copuntos ). Estos son los bemoles propios máximos; es decir, el único superconjunto de un hiperplano que también es plano es el conjunto de todos los elementos de la matroide. Una definición equivalente es que un coatom es un subconjunto de E que no abarca M , pero que al agregarle cualquier otro elemento se forma un conjunto de expansión. ^[5] ${\displaystyle r\ ,}$ ${\displaystyle r-1}$ ${\displaystyle E}$

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

• (H1) No existen conjuntos distintos y en con Es decir, los hiperplanos forman una familia 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 otro, ${\displaystyle C}$

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

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

• (G4) siempre que se represente como la unión disjunta de subconjuntos con (un conjunto singleton), entonces existe tal que o existe 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 una matroide para la cual es la clase de circuitos y es la clase de cocircuitos. Por el contrario, si y son las clases de circuito y cocircuito de una matroide con conexión a tierra , entonces es un grafoide. Por lo tanto, los grafoides dan una axiomatización criptomórfica autodual de las 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 una matroide. Se llama matroid libre . ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle E}$

matroides uniformes

Sea un conjunto finito y un número natural . Se puede definir una matroide tomando cada subconjunto de elementos como base. Esto se conoce como matroide uniforme de rango. Se denota una matroide uniforme con rango y con elementos . Todas las matroides uniformes de rango al menos 2 son simples (ver § Términos adicionales). La matroide uniforme de rango 2 en puntos se llama línea de puntos . Una matroide es uniforme si y sólo si no tiene circuitos de tamaño menor que uno más el rango de la matroide. Las sumas directas de matroides uniformes se denominan 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 la matroide uniforme cada elemento es un bucle (un elemento que no pertenece a ningún conjunto independiente), y en la 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 una matroide de partición en la que cada elemento es un bucle o un coloop; se llama matroide discreta . Una definición equivalente de matroide discreta es una matroide en la que cada subconjunto adecuado y no vacío del conjunto fundamental es un separador. ${\displaystyle U_{0,n}\ ,}$ ${\displaystyle U_{n,n}\ ,}$ ${\displaystyle E}$

Matroides del álgebra lineal

La matroide Fano, derivada del plano Fano . Es GF(2) -lineal pero no real-lineal.

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

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

Si hay un subconjunto finito de un espacio vectorial , entonces podemos definir una matroide tomando los conjuntos independientes de como 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 esta matroide se deriva del lema de intercambio de Steinitz .

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

Las matroides de este tipo se denominan matroides vectoriales .

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

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

Esta 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 favorecer la representación matricial. ^[b]

Una matroide que es equivalente a una matroide vectorial, aunque puede presentarse de forma diferente, se llama representable o lineal . Si es equivalente a un vector matroide sobre un campo , entonces decimos que es representable sobre ; en particular, es real representable si es representable sobre los números reales. Por ejemplo, aunque una matroide gráfica (ver más abajo) se presenta en términos de un gráfico, también se puede representar mediante vectores sobre cualquier campo. ${\displaystyle M}$ ${\displaystyle F}$ ${\displaystyle M}$ ${\displaystyle F}$ ${\displaystyle M}$

Un problema básico en la teoría de las matroides es caracterizar las matroides que pueden representarse en un campo determinado ; La conjetura de Rota describe una posible caracterización de todo campo finito . Los principales resultados hasta ahora son caracterizaciones de matroides binarias (aquellas representables sobre GF(2)) debido a Tutte (década de 1950), de matroides ternarias (representables sobre el campo de 3 elementos) debido a Reid y Bixby, y por separado a Seymour (década de 1970) . , y de matroides cuaternarias (representables en el campo de 4 elementos) debido a Geelen, Gerards y Kapoor (2000) . Esta es en gran medida un área abierta. ^{[¿ necesita actualización? ]} ${\displaystyle F}$ harvp error: no target: CITEREFGeelenGerardsKapoor2000 (help)

Una matroide normal es una matroide que se puede representar en todos los campos posibles. La matroide Vámos es el ejemplo más simple de una 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 las matroides es la teoría de grafos .

Todo grafo finito (o multigrafo ) da lugar a una matroide de la siguiente manera: tomar como el conjunto de todas las aristas en y considerar un conjunto de aristas independientes si y sólo si es un bosque ; es decir, si no contiene un ciclo simple . Entonces se llama ciclo matroide . Las matroides derivadas de esta manera son matroides gráficas . No todas las matroides son gráficas, pero todas las matroides de tres elementos son gráficas. ^[6] Cada matroide gráfico es regular. ${\displaystyle G}$ ${\displaystyle M(G)}$ ${\displaystyle E}$ ${\displaystyle G}$ ${\displaystyle M(G)}$

Posteriormente se descubrieron otras matroides en gráficos:

• La matroide bicircular de un gráfico se define llamando independiente a un conjunto de aristas si cada subconjunto conectado 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 para que sea independiente si hay caminos separados por vértices desde hacia . Esto define una matroide llamada gammoide : ^[7] un gammoide estricto es aquel cuyo conjunto es el conjunto completo de vértices de . ^[8] ${\displaystyle G}$ ${\displaystyle E}$ ${\displaystyle F}$ ${\displaystyle E}$ ${\displaystyle U}$ ${\displaystyle |U|}$ ${\displaystyle F}$ ${\displaystyle U}$ ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle G}$

• En un gráfico bipartito , se puede formar una matroide en la que los elementos son vértices en un lado de la bipartición y los subconjuntos independientes son conjuntos de puntos finales de coincidencias del gráfico. Esto se llama matroide transversal , ^{[9] [10]} y es un caso especial de gammaide. ^[7] Las matroides transversales son las matroides duales de las gammaides estrictas. ^[8] ${\displaystyle G=(U,V,E)}$ ${\displaystyle U}$

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

Si cada ciclo pertenece a la clase distinguida, estas matroides coinciden con el ciclo matroide de . Si no se distingue ningún ciclo, la matroide de marco es la matroide bicircular de un gráfico con signo, cuyos bordes están etiquetados con signos, y un gráfico de ganancia, que es un gráfico cuyos bordes están etiquetados de forma orientable a partir de un grupo, cada uno de los cuales da lugar a un gráfico sesgado. y por lo tanto tienen matroides de marco y elevación. ${\displaystyle G}$ ${\displaystyle G~.}$

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

• Sea un gráfico conexo y su conjunto de aristas. Sea la colección de subconjuntos de tales que todavía están conectados. Entonces, cuyo conjunto de elementos es y con su clase de conjuntos independientes, es una matroide llamada 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 de extensiones de campo.

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

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

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

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

Una matroide que es equivalente a una matroide de este tipo se llama matroide algebraica . ^[12] El problema de caracterizar matroides algebraicas es extremadamente difícil; poco se sabe al respecto. La matroide Vámos proporciona un ejemplo de una matroide que no es algebraica.

Construcciones basicas

Existen algunas formas estándar de crear nuevas matroides a partir de las antiguas.

Dualidad

Si es una matroide finita, podemos definir la matroide ortogonal o dual tomando el mismo conjunto subyacente y llamando a un conjunto base en si y sólo si su complemento es una base en No es difícil verificar que es una matroide y que la matroide es finita. dual de es ^[13] ${\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 una matroide. Por ejemplo:

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

• Un conjunto es un circuito de si y sólo si su complemento es un coatom en ${\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 una matroide gráfica es una matroide gráfica si y sólo si es la matroide de un gráfico plano . En este caso, el dual de es la matroide del gráfico dual de ^[14] El dual de una matroide vectorial representable sobre un campo particular también se puede representar sobre El dual de una matroide transversal es un gammaide estricto y viceversa. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle G~.}$ ${\displaystyle F}$ ${\displaystyle F~.}$

Ejemplo

La matroide de ciclo de un gráfico es la matroide dual de su matroide de enlace.

Menores

Si M es una matroide con conjunto de elementos E y S es un subconjunto de E , la restricción de M a S , escrita M  | S , es la matroide del 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 eliminación de T , escrito M \ T o M − T. Las submatroides de M son precisamente el resultado de una secuencia de eliminaciones: el orden es irrelevante. ^{[15] [16]}

La doble operación de la restricción es la contracción. ^[17] Si T es un subconjunto de E , la contracción de M por T , escrita M / T , es la matroide en el conjunto subyacente E − T cuya función de rango es ^[18] 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).}$

Una matroide N que se obtiene de M mediante una secuencia de operaciones de restricción y contracción se denomina menor de M. ^{[16] [19]} Decimos que M contiene N como menor . Muchas familias importantes de matroides pueden caracterizarse por matroides menores-mínimas que no pertenecen a la familia; a estos se les llama menores prohibidos o excluidos . ^[20]

Sumas y uniones

Sea M una matroide con un conjunto subyacente de elementos E y sea N otra matroide en un conjunto subyacente F. La suma directa de matroides M y N es la 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 la 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. Normalmente 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.

Terminos adicionales

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

• E puede denominarse conjunto fundamental de M . Sus elementos pueden denominarse puntos de M .

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

• La circunferencia de una 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. ^{[6] [21]}

• 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. ^[21]

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

• Una matroide se llama 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 . ^[6] Una matroide simple obtenida de otra 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. ^[22] Una matroide es co-simple si su matroide dual es simple. ^[23]

• A la unión de circuitos a veces se le llama ciclo de M. Por tanto, un ciclo es el complemento de un piso de la 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 adecuado o no trivial es un separador que no es ni E ni el conjunto vacío. ^[24] Un separador irreducible es un separador no vacío que no contiene ningún otro separador no vacío. Los separadores irreductibles dividen el conjunto de tierra E. ${\displaystyle r(S)+r(E-S)=r(M)}$

• Una matroide que no se puede escribir como la suma directa de dos matroides no vacías, o de manera equivalente, que no tiene separadores adecuados, se llama conectada o irreducible . Una matroide está conectada si y sólo si su dual está conectado. ^[25]

• Una submatroide máxima irreducible de M se llama componente de M . Un componente es la restricción de M a un separador irreducible y, por el contrario, la restricción de M a un separador irreducible es un componente. Un separador es una unión de componentes. ^[24]

• Una matroide M se llama matroide de marco si ella, o una matroide que la 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. ^[26]

• Una matroide se llama matroide pavimentadora si todos sus circuitos tienen un tamaño al menos igual a su rango. ^[27]

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

Algoritmos

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

• Encontrar un conjunto independiente de peso máximo en una matroide ponderada se puede resolver mediante un algoritmo codicioso. Este hecho puede incluso usarse 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 codicioso encuentra un conjunto de peso máximo en la familia, entonces F debe ser la familia de conjuntos independientes de una matroide. ^[28]

• El problema de partición de matroides consiste en dividir los elementos de una matroide en el menor número posible de conjuntos independientes, y el problema de empaquetado de matroides es encontrar tantos conjuntos de expansión disjuntos como sea posible. Ambos pueden resolverse en tiempo polinómico y generalizarse al problema de calcular el rango o encontrar un conjunto independiente en una suma matroide.

• Una intersección matroide de dos o más matroides en el mismo conjunto terrestre es la familia de conjuntos que son simultáneamente independientes en cada una de las 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 gráficos 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 matroide

Dos sistemas independientes para cálculos con matroides son Kingan's Oid y Hlineny's Macek. 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 cálculos combinatorios razonablemente eficientes con matroides representables.

Ambos sistemas de software matemático de código abierto, SAGE y Macaulay2, contienen paquetes matroid.

Invariantes polinomiales

Hay dos polinomios especialmente significativos asociados a una matroide finita M en el conjunto terrestre E. Cada una es una invariante matroide , lo que significa que las matroides isomorfas tienen el mismo polinomio.

Polinomio característico

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

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

o de manera equivalente (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 de la matroide y la suma se toma sobre todos los pisos A de la matroide. ^[30]

• Cuando M es la matroide del ciclo M ( G ) de un gráfico 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 conectados de G .

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

• Cuando M es la matroide M ( A ) de una disposición A de hiperplanos lineales en ℝ ⁿ (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  (λ).

invariante beta

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

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

o directamente como ^[32]

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

La invariante beta no es negativa y es cero si y solo si está desconectada, vacía o es un bucle. De lo contrario, depende sólo de la red de pisos de Si no tiene bucles ni bucles, entonces ^[32] ${\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. Específicamente, el 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\},}$

resumido sobre pisos 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 el número de pisos de cada rango. Es decir, es el número de  pisos de 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 de la matroide de ciclo del grafo completo , y equivalentemente de la red de partición . Fueron nombrados en honor a Hassler Whitney , el (co)fundador de la teoría matroide, de Gian-Carlo Rota . El nombre se ha extendido a números similares para conjuntos finitos clasificados parcialmente ordenados .

polinomio tutte

El polinomio de Tutte de una matroide generaliza el polinomio característico a dos variables. Esto le da interpretaciones más combinatorias y también le otorga 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 de la nulidad de co-rango o polinomio generador de rango , ^[33]

${\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, hasta 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 de bases, lo que refleja el hecho de que es el número de bases. ^[34] Esta, que suma 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 recursividad por eliminación y contracción. ^[35] 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 coloop. Un invariante de matroides (es decir, una función que toma el mismo valor en matroides isomórficas) que satisface esta recursividad y la condición multiplicativa ${\displaystyle e}$

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

Se dice que es una invariante de Tutte-Grothendieck . ^[33] El polinomio de Tutte es el invariante más general; es decir, el polinomio de Tutte es un invariante de Tutte-Grothendieck y cada uno de esos invariantes es una evaluación del polinomio de Tutte. ^[29]

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

matroides infinitas

La teoría de las matroides infinitas es mucho más complicada que la de las matroides finitas y constituye un tema propio. Durante mucho tiempo, una de las dificultades ha sido que había muchas definiciones razonables y útiles, ninguna de las cuales parecía capturar todos los aspectos importantes de la teoría matroide finita. Por ejemplo, parecía difícil tener bases, circuitos y dualidad juntos en una noción de matroides infinitas.

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

La siguiente generalización infinita más simple son las matroides finitas, también conocidas como pregeometrías . Una matroide con un conjunto de terreno posiblemente infinito es finita 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').}$

De manera equivalente, todo conjunto dependiente contiene un conjunto dependiente finito.

Algunos ejemplos 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 de un grado de trascendencia posiblemente infinito. Nuevamente, la clase de matroide finitaria no es autodual, porque el dual de una matroide finitaria no es finitario.

Las matroides finitas infinitas 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 la década de 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 matroides B y fue estudiado por Higgs, Oxley y otros en las décadas de 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 de axioma equivalentes: en términos de independencia, bases, circuitos, cierre y rango. La dualidad de las B-matroides generaliza dualidades que se pueden observar en gráficos infinitos.

Los axiomas de independencia son los siguientes:

1. El conjunto vacío es independiente.
2. Todo subconjunto de un conjunto independiente es independiente.
3. Para cada conjunto independiente no máximo (inclusión de conjuntos inferiores) y conjunto independiente máximo , existe uno 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 matroide fue introducida por Whitney (1935). También fue descubierto de forma independiente por Takeo Nakasawa , cuyo trabajo fue olvidado durante muchos años Nishimura y Kuroda (2009).

En su artículo fundamental, Whitney proporcionó dos axiomas de independencia y definió cualquier estructura que se adhiriera 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 gráficos como a las matrices. Debido a esto, muchos de los términos utilizados en la teoría matroide se parecen a los términos de 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) observó similitudes entre la dependencia algebraica y lineal en su clásico libro de texto sobre álgebra moderna.

En la década de 1940, Richard Rado desarrolló más teoría bajo el nombre de "sistemas de independencia" con miras a la teoría transversal , donde todavía se utiliza a veces su nombre para el tema.

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, incluyendo

• la caracterización de matroides binarias , regulares y gráficas por menores excluidos

• el teorema de representabilidad de la matroide regular

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

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

• el "teorema del camino"

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

que son tan complicados 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 matroides el "dicromato" de Tutte, un polinomio gráfico ahora conocido como polinomio de Tutte (llamado 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 sobre el polinomio de Tutte de un gráfico.

En 1976, Dominic Welsh publicó el primer libro completo sobre la teoría de las 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 los años setenta y ochenta. Otra contribución fundamental, la 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 matroide.

En la década de 1980 hubo muchos otros contribuyentes importantes, pero no se debe omitir mencionar la extensión de Geoff Whittle a las matroides ternarias de la caracterización de Tutte de las matroides binarias que son representables sobre las 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 estructural de las matroides. Muchos otros también han contribuido a esa parte de la teoría matroide, que (en la primera y segunda décadas del siglo XXI) está floreciendo.

Investigadores

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

Susumu Kuroda ^[36]

Saunders MacLane

Richard Rado

Takeo Nakasawa

Hirokazu Nishimura ^[36]

WT Tutte

BL van der Waerden

Whitney Hassler

Algunos de los otros contribuyentes importantes son

Jack Edmons

Jim Geelen

Eugenio Lawler

László Lovász

Gian Carlo Rota

PD Seymour

dominical galés

Notas a pie de página

1. Oxley (1992) es una fuente estándar de definiciones y resultados básicos 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: una matroide de columna puede tener elementos distintos que sean el mismo vector, pero una matroide vectorial como se define anteriormente no puede. Por lo general, esta diferencia es insignificante y puede ignorarse, pero al dejar que sea un conjunto múltiple de vectores, las dos definiciones coinciden completamente. ${\displaystyle E}$
3. Aunque quizás estuviera implícito, Whitney (1935) no incluyó un axioma que requiriera que al menos un subconjunto fuera independiente.

4. Un buen ejemplo es la breve prueba de AMH Gerards (Gerards (1989)) de la caracterización de Tutte de las matroides regulares.
5. El Proyecto Matroid Minors es un intento de duplicar, para matroides que son representables en un campo finito, el éxito del Proyecto Robertson-Seymour Graph Minors (ver Teorema de Robertson-Seymour ).

Ver también

• antimatroide
• matroide coxeter
• Codicioso
• matroide orientada
• polimatroide
• Pregeometría (teoría de modelos)

Citas

1. Neel y Neudauer (2009)
2. Kashyap, Soljanin y Vontobel (2009)
3. Welsh (1976, págs. 7–9), Sección 1.2, "Sistemas de axiomas para una matroide".
4. Welsh (1976, págs. 21-22), Sección 1.8, "Conjuntos cerrados = Pisos = Subespacios".
5. Welsh (1976, págs. 38-39), Sección 2.2, "Los hiperplanos de una matroide".
6. Oxley (1992), pág. 13
7. Oxley (1992), págs.115
8. Oxley (1992), pág. 100
9. Oxley (1992), págs. 46–48
10. Blanco (1987), págs. 72–97
11. Oxley (1992), pág. 215
12. Oxley (1992), pág. 216
13. Blanco (1986), pág. 32
14. Blanco (1986), pág. 105
15. Blanco (1986), pág. 131
16. White (1986), pág. 224
17. Blanco (1986), pág. 139
18. Blanco (1986), pág. 140
19. Blanco (1986), pág. 150
20. Blanco (1986), págs. 146-147
21. White (1986), pág. 130
22. Oxley (1992), pág. 52
23. Oxley (1992), pág. 347
24. Oxley (1992), pág. 128
25. Blanco (1986), pág. 110
26. Zaslavsky (1994)
27. Oxley (1992), pág. 26
28. Oxley (1992), pág. 64
29. White (1987), pág. 127
30. Blanco (1987), pág. 120
31. Blanco (1987), pág. 123
32. White (1987), pág. 124
33. White (1987), pág. 126
34. Blanco (1992b), pág. 188
35. Blanco (1986), pág. 260
36. Nishimura y Kuroda (2009)

Referencias

• Bruhn, Henning; Diestel, Reinhard; Kriesell, Matías; Pendavingh, Rudi; Wollan, Paul (2013). "Axiomas para matroides infinitas". Avances en Matemáticas . 239 : 18–46. arXiv : 1003.3919 . doi : 10.1016/j.aim.2013.01.011 . SEÑOR  3045140. S2CID  10436077.

• Bryant, Víctor; Perfecto, Hazel (1980). Teoría de la Independencia en Combinatoria . Londres, Reino Unido y Nueva York, Nueva York: Chapman and Hall. ISBN 978-0-412-22430-0.

• Brylawski, Thomas H. (1972). "Una descomposición de geometrías combinatorias". Transacciones de la Sociedad Matemática Estadounidense . 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). Sobre los fundamentos de la teoría combinatoria: geometrías combinatorias. Cambridge, MA: MIT Press. ISBN 978-0-262-53016-3. SEÑOR  0290980 - vía Internet Archive (archive.org).

• Edmonds, Jack (5 a 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 . V Taller Internacional. Apuntes de conferencias sobre informática. vol. 2570 (edición de artículos revisados). 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, Jim ; Gerards, AMH; Whittle, Geoff (2007). "Hacia una teoría de la estructura menor matroide". En Grimmett, Geoffrey; et al. (eds.). Combinatoria, complejidad y azar: un tributo a Dominic Welsh . Serie de conferencias de Oxford sobre matemáticas y sus aplicaciones. 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". Transacciones de la Sociedad Matemática Estadounidense . 271 (2): 485–499. doi : 10.2307/1998894 . JSTOR  1998894.

• Kingan, Robert; Kingan, Sandra (2005). "Un sistema de software para matroides". Gráficos y descubrimiento . Serie DIMACS en Matemática Discreta e Informática Teórica. págs. 287–296.

• Kashyap, Navin; Soljanin, Emina; Vontobel, Pascal (2009). Aplicaciones de la teoría matroide y la optimización combinatoria a la teoría de la información y la codificación (PDF) (Reporte) . Consultado el 4 de octubre de 2014 , a través de www.birs.ca.

• Kung, Joseph PS, ed. (1986). Un libro de consulta sobre la teoría matroide. Boston, MA: Birkhäuser. doi :10.1007/978-1-4684-9199-9. ISBN 978-0-8176-3173-4. SEÑOR  0890330 - vía Internet Archive (archive.org).

• MacLane, Saunders (1936). "Algunas interpretaciones de la dependencia lineal abstracta en términos de geometría proyectiva". Revista Estadounidense de Matemáticas . 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". Revista de Matemáticas y Mecánica . 15 : 485–520. SEÑOR  0188102.

• Neel, David L.; Neudauer, Nancy A. (2009). "Matroides que has conocido" (PDF) . Revista Matemáticas . 82 (1): 26–41. doi :10.4169/193009809x469020 . Consultado el 4 de octubre de 2014 , a través de la Mathematical Association of America (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. SEÑOR  2516551. Zbl  1163.01001.

• Oxley, James (1992). Teoría matroide . Oxford, Reino Unido: Oxford University Press. ISBN 978-0-19-853563-8. SEÑOR  1207587. Zbl  0784.05002.

• Recski, András (1989). Teoría matroide y sus aplicaciones en teoría de redes eléctricas y en 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. SEÑOR  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". Revista de teoría combinatoria . 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: Prensa académica. ISBN 978-0-12-701225-4. SEÑOR  1170126 - a través de emis.de.

• Tutte, WT (1959). "Matroides y gráficos". Transacciones de la Sociedad Matemática Estadounidense . 90 (3): 527–552. doi : 10.2307/1993185 . JSTOR  1993185. SEÑOR  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 las Matroides . Métodos analíticos y computacionales modernos en ciencias y matemáticas. vol. 37. Nueva York, Nueva York: American Elsevier Publishing Company. Zbl  0231.05027.

• Vamos, Peter (1978). "El axioma que falta en la teoría matroide se pierde para siempre". Revista de la Sociedad Matemática de Londres . 18 (3): 403–408. doi :10.1112/jlms/s2-18.3.403.

• van der Waerden, BL (1937). Álgebra moderna .

• Galés, DJA (1976). Teoría matroide . Monografías de LMS. vol. 8. Prensa Académica. ISBN 978-0-12-744050-7. Zbl  0343.05002.

• Blanco, Neil, ed. (1986). Teoría de las 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).

• Blanco, Neil, ed. (1987). Geometrías combinatorias . 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).

• Blanco, Neil, ed. (1992a). Aplicaciones 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". Revista Estadounidense de Matemáticas . 57 (3): 509–533. doi :10.2307/2371182. hdl : 10338.dmlcz/100694 . JSTOR  2371182. SEÑOR  1507091.— Reimpreso en Kung (1986), págs. 55–79

• Whittle, Geoff (1995). "Una caracterización de las matroides representables sobre GF (3) y los racionales". Revista de teoría combinatoria . Serie B. 65 (2): 222–261. doi : 10.1006/jctb.1995.1052 .

• Zaslavsky, Thomas (1994). "Matroides de marcos y gráficos sesgados". EUR. J. peine. 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]

• Kingán, Sandra. "Teoría matroide". userhome.brooklyn.cuny.edu (sitio personal académico). Colegio de Brooklyn . Brooklyn, Nueva York: Universidad de la ciudad de Nueva York .- Una gran bibliografía de artículos matroid, software matroid y enlaces.

• Locke, SC "Algoritmos codiciosos". math.fau.edu (sitio personal académico). Boca Ratón, FL: Universidad Atlántica de Florida .

• Pagano, Steven R. "Matroides y gráficos firmados". math.binghamton.edu (sitio personal académico). Binghamton, Nueva York: Universidad de Binghamton .

• Hubenthal, Marcos. "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 declaraciones de este artículo.

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

• Blanco, Neil, ed. (1992b). Aplicaciones matroides. Prensa de la Universidad de Cambridge. ISBN 978-0-5213-8165-9. ISSN  0953-4806 - a través de Google Books.