stringtranslate.com

Matroide

En combinatoria , una rama de las matemáticas , un matroide / ˈm 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]

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

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]

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]

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.

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]

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.

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 .

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

Esto define un operador de cierre donde denota el conjunto de potencia , con las siguientes propiedades:

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 LaneSteinitz . Estas propiedades pueden tomarse como otra definición de matroide: cada función que obedece a estas propiedades determina un matroide. [3]

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:

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

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

Por lo tanto, la red de planos de este matroide es naturalmente isomorfa a .

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]

La familia de hiperplanos de un matroide tiene las siguientes propiedades, que pueden tomarse como otra axiomatización de los matroides: [5]

Grafoides

Minty (1966) definió un grafoide como un triple en el que y son clases de subconjuntos no vacíos de tales que

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.

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 .

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 . 

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.

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

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
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.

Este matroide se llama matroide de columna de , y se dice que representa .

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.

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]

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.

Posteriormente se descubrieron otros matroides en gráficos:

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.
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.

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 .
Definir un subconjunto de como algebraicamente independiente si el campo de extensión tiene un grado de trascendencia igual a [12]

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]

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

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.

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 = MS esto puede denominarse la eliminación de T , escrita M \ T o MT . 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 .

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.

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

Algoritmos

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

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

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

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]

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]

o directamente como [34]

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]

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:

sumados sobre los bemoles del rango correcto. Estos números se alternan en signo, de modo que para

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.

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.

lo que implica una serie de dualidades entre propiedades de y propiedades de Una definición del polinomio de Tutte es

Esto expresa el polinomio de Tutte como una evaluación del polinomio de co-rango-nulidad o generador de rango , [35]

De esta definición es fácil ver que el polinomio característico es, salvo un factor simple, una evaluación de específicamente,

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.

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

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

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.

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

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.
  4. Para cada subconjunto del espacio base, cada subconjunto independiente de puede extenderse a un subconjunto independiente máximo de

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 a veces todavía hoy.

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:

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

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.
  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

Citas

  1. ^ Neel y Neudauer (2009)
  2. ^ Kashyap, Soljanin y Vontobel (2009)
  3. ^ abcde 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. ^ ab 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. ^ abcd Oxley (1992), pág. 13
  8. ^ de Oxley (1992), págs. 115
  9. ^ de 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. ^ ab 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. ^ ab White (1986), pág. 130
  23. ^ Oxley (1992), pág. 52
  24. ^ Oxley (1992), pág. 347
  25. ^ por 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. ^ ab White (1987), pág. 127
  32. ^ Blanco (1987), pág. 120
  33. ^ Blanco (1987), pág. 123
  34. ^ ab White (1987), pág. 124
  35. ^ ab White (1987), pág. 126
  36. ^ Blanco (1992b), pág. 188
  37. ^ Blanco (1986), pág. 260
  38. ^ ab Nishimura y Kuroda (2009)

Referencias

Enlaces externos