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]
(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 .
(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 .
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 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]
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]
(B1) no está vacío.
(B2) Si y son miembros distintos de y entonces existe un elemento tal que
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.
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]
(R3) Para dos subconjuntos cualesquiera , tenemos: Es decir, el rango es una función submodular .
(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 .
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.
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 .
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
(C4) Para todos los elementos y de y todos los subconjuntos de if then
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]
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.
(F2) Si y son pisos, entonces es un piso.
(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 ).
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
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
Por lo tanto, la red de pisos de esta matroide es naturalmente isomorfa a .
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]
La familia de hiperplanos de una matroide tiene las siguientes propiedades, que pueden tomarse como otra axiomatización más de las matroides: [5]
(H1) No existen conjuntos distintos y en con Es decir, los hiperplanos forman una familia Sperner .
(H2) Para cada y distinto con existe con
Grafoides
Minty (1966) definió un grafoide como un triple en el que y son clases de subconjuntos no vacíos de tales que
(G1) ningún elemento de (llamado "circuito") contiene otro,
(G2) ningún elemento de (llamado "cocircuito") contiene otro,
(G3) ningún conjunto y conjunto se cruzan exactamente en un elemento, y
(G4) siempre que se represente como la unión disjunta de subconjuntos con (un conjunto singleton), entonces existe tal que o existe tal que
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.
Ejemplos
matroide libre
Sea un conjunto finito. El conjunto de todos los subconjuntos de define los conjuntos independientes de una matroide. Se llama matroide libre .
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 .
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.
Matroides del álgebra lineal
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
Si es una matroide que se puede definir de esta manera, decimos que el conjunto representa
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.
Esta 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 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.
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.
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]
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]
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.
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.
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 como clase de conjuntos independientes, es una matroide llamada matroide de enlace de
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.
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]
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
Un conjunto es un circuito de si y sólo si su complemento es un coatom en
La función de rango del dual es
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.
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 .
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.
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]
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
o de manera equivalente (siempre que el conjunto vacío esté cerrado en M ) como
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 ℝ n (o F n 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]
o directamente como [32]
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]
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:
resumido sobre pisos del rango correcto. Estos números se alternan en signo, de modo que para
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.
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.
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 de la nulidad de co-rango o polinomio generador de rango , [33]
De esta definición es fácil ver que el polinomio característico es, hasta un factor simple, una evaluación de específicamente,
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.
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
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
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.
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
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.
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:
El conjunto vacío es independiente.
Todo subconjunto de un conjunto independiente es independiente.
Para cada conjunto independiente no máximo (inclusión de conjuntos inferiores) y conjunto independiente máximo , existe uno que es independiente.
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 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
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
^
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.
^
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.
^
Aunque quizás estuviera implícito, Whitney (1935) no incluyó un axioma que requiriera que al menos un subconjunto fuera independiente.
^
Un buen ejemplo es la breve prueba de AMH Gerards (Gerards (1989)) de la caracterización de Tutte de las matroides regulares.
^
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 ).
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 .
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).
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.
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).
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 (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.
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.
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.
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.