En la combinatoria , una rama de las matemáticas , un matroid / m eɪ t r ɔɪ d / es una estructura que resúmenes 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 planos. En el lenguaje de los conjuntos parcialmente ordenados , una matroide finita equivale a una retícula geométrica .
La teoría matroide se basa ampliamente en la terminología del álgebra lineal y la teoría de grafos , en gran parte 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 ( criptomórficas ) de definir una matroide (finita). [3]
Conjuntos independientes
En términos de independencia, una matroide finita es un par , dónde es un conjunto finito (llamado conjunto básico ) yes una familia de subconjuntos de(llamados conjuntos independientes ) con las siguientes propiedades: [4]
- (I1) El conjunto vacío es independiente, es decir, . Alternativamente, al menos un subconjunto de es independiente, es decir, .
- (I2) Todo subconjunto de un conjunto independiente es independiente, es decir, para cada , Si luego . A esto a veces se le llama propiedad hereditaria o propiedad cerrada a la baja .
- (I3) Si y son dos conjuntos independientes (es decir, cada conjunto es independiente) y tiene más elementos que , entonces existe tal que es en . 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 ).
Bases y circuitos
Un subconjunto del terreno que no es independiente se llama dependiente . Un conjunto independiente máximo, es decir, un conjunto independiente que se vuelve dependiente de la adición de cualquier elemento de—Se llama base del matroide. Un circuito en una matroide es un subconjunto dependiente mínimo de —Es decir, un conjunto dependiente cuyos subconjuntos propios son todos independientes. La terminología surge porque los circuitos de las matroides gráficas son ciclos en los gráficos correspondientes. [4]
Los conjuntos dependientes, las bases o los circuitos de una matroide caracterizan completamente a la 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 lo hace. no contiene un circuito. Las colecciones de conjuntos dependientes, de bases y de circuitos tienen propiedades simples que pueden tomarse como axiomas de una matroide. Por ejemplo, se puede definir un matroide ser un par , dónde es un conjunto finito como antes y es una colección de subconjuntos de , llamadas "bases", con las siguientes propiedades: [4]
- (B1) no está vacío.
- (B2) Si y son miembros distintos de y , entonces existe un elemento tal que . Esta propiedad se denomina propiedad de intercambio base .
De la propiedad de intercambio base se deduce que ningún miembro de puede ser un subconjunto adecuado de otro.
Funciones de rango
Es un resultado básico de la teoría matroide, directamente análogo a un teorema similar de bases en álgebra lineal , que dos bases cualesquiera de una matroidetener el mismo número de elementos. Este número se llama rango de . Si es una matroide en , y es un subconjunto de , luego una matroide en puede definirse considerando un subconjunto de ser independiente si y solo si es independiente en . Esto nos permite hablar sobre submatroides y sobre el rango de cualquier subconjunto de. El rango de un subconjuntoviene dada por la función de rango del matroide, que tiene las siguientes propiedades: [4]
- El valor de la función de rango es siempre un número entero no negativo .
- Para cualquier subconjunto , tenemos .
- Para dos subconjuntos cualesquiera , tenemos: . Es decir, el rango es una función submodular .
- Para cualquier conjunto y elemento , tenemos: . De la primera desigualdad se sigue de manera más general que, si, luego . 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 sobre se puede definir como esos subconjuntos de con . En el lenguaje de los conjuntos parcialmente ordenados , tal estructura matroide es equivalente a la celosía geométrica cuyos elementos son los subconjuntos, parcialmente ordenado por inclusión.
La diferencia se llama la nulidad del subconjunto. Es el número mínimo de elementos que se deben eliminar depara obtener un conjunto independiente. La nulidad de en se llama la nulidad de . La diferenciaa veces se llama el corank del subconjunto.
Operadores de cierre
Dejar ser una matroide en un conjunto finito , con función de rango como anteriormente. El cierre (o lapso ) de un subconjunto de es el set
- .
Esto define un operador de cierre dónde denota el conjunto de potencia , con las siguientes propiedades:
- Para todos los subconjuntos de , .
- Para todos los subconjuntos de , .
- Para todos los subconjuntos y de con , .
- Para todos los elementos , y de y todos los subconjuntos de , Si luego .
Las tres primeras 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ónque obedece a estas propiedades determina una matroide. [4]
Pisos
Se dice que un conjunto cuyo cierre es igual a sí mismo está cerrado , o un plano o subespacio de la matroide. [5] Un conjunto se cierra 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 cobertura:
- Todo el conjunto de puntos está cerrado.
- Si y son pisos, entonces es un piso.
- Si es un plano, entonces cada elemento de está precisamente en uno de los pisos esa tapa (significa que contiene correctamente pero no hay piso Entre y ).
La clase de todos los pisos, parcialmente ordenados por inclusión de conjuntos, forma una celosía matroide . Por el contrario, cada celosía 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 se corresponden uno por uno con los elementos de la celosía; el piso correspondiente al elemento de celosía es el set
- .
Por lo tanto, la celosía de los planos 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 coatoms o copoints .) Estos son los planos propios máximos; es decir, el único superconjunto de un hiperplano que también es plano es el conjuntode todos los elementos del matroide. Una definición equivalente es que un coatom es un subconjunto de E que no abarca M , pero tal que agregarle cualquier otro elemento crea un conjunto de expansión. [6]
La familia de hiperplanos de un matroide tiene las siguientes propiedades, que pueden tomarse como otra axiomatización de matroides: [6]
- No existen conjuntos distintos y en con . Es decir, los hiperplanos forman una familia Sperner .
- Para cada y distinto con , existe con .
Grafoides
Minty (1966) definió un grafoide como un triple en el cual y son clases de subconjuntos no vacíos de tal que
- ningún elemento de (llamado "circuito") contiene otro,
- ningún elemento de (llamado "cocircuito") contiene otro,
- no establecido en y establecer en se cruzan exactamente en un elemento, y
- cuando sea se representa como la unión disjunta de subconjuntos con (un conjunto singleton), entonces un existe tal que o un existe tal que
Demostró que hay un matroide para el que 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 suelo , luego es un grafoide. Por lo tanto, los grafoides dan una axiomatización criptomórfica auto-dual de las matroides.
Ejemplos de
Matroid gratis
Dejar ser un conjunto finito. El conjunto de todos los subconjuntos desatisface la definición de matroide. Se llama matroide libre sobre.
Matroides uniformes
Dejar ser un conjunto finito y un número natural . Uno puede definir una matroide en tomando cada -subconjunto de elementos de para ser una base. Esto se conoce como el matroide uniforme de rango.. Una matroide uniforme con rango y con los elementos se denota . Todas las matrices uniformes de rango al menos 2 son simples (ver § Terminología adicional ). La 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 denominan matroides de partición .
En el uniforme matroid , cada elemento es un bucle (un elemento que no pertenece a ningún conjunto independiente), y en la matroid 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 discreto . Una definición equivalente de una matroide discreta es una matroide en la que cada subconjunto adecuado, no vacío del conjunto básico es un separador.
Matroides del álgebra lineal
La teoría matroide se desarrolló principalmente a partir de un examen profundo de las propiedades de la independencia y la dimensión en los espacios vectoriales. Hay dos formas de presentar las matroides definidas de esta manera:
- Si es cualquier subconjunto finito de un espacio vectorial , entonces podemos definir un matroide en tomando los conjuntos independientes de para ser los subconjuntos linealmente independientes de. La validez de los axiomas de conjuntos independientes para este matroide se deriva del lema de intercambio de Steinitz . Si es una matroide que se puede definir de esta manera, decimos el conjunto representa . Las 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 de la matroide) y siete líneas (los planos no triviales propios del plano de Fano ). 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 el matroide de Fano utilizando los números reales en lugar de GF (2).
- Una matriz con entradas en un campo da lugar a una matroideen su conjunto de columnas. Los conjuntos de columnas dependientes en el matroide son aquellos que son linealmente dependientes como vectores. Este matroide se llama el 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. (Hay una diferencia técnica: una matriz de columnas puede tener elementos distintos que son el mismo vector, pero una matriz de vectores como se define anteriormente no. Por lo general, esta diferencia es insignificante y se puede ignorar, pero dejandoser un conjunto múltiple de vectores, uno trae las dos definiciones en completo acuerdo).
Una matroide que es equivalente a una matroide vectorial, aunque puede presentarse de manera diferente, se llama representable o lineal . Sies equivalente a una matroide vectorial sobre un campo , entonces decimos es representable sobre ; En particular,es representable real si es representable sobre los números reales. Por ejemplo, aunque una matriz 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. Un problema básico en la teoría de las matroides es caracterizar las matroides que pueden estar representadas en un campo dado.; La conjetura de Rota describe una posible caracterización para cada campo finito . Los principales resultados hasta ahora son caracterizaciones de matroides binarios (los representables sobre GF (2)) debido a Tutte (década de 1950), de matroides ternarios (representables sobre el campo de 3 elementos) debido a Reid y Bixby, y por separado a Seymour (década de 1970). ) y de matroides cuaternarios (representables sobre el campo de 4 elementos) debido a Geelen, Gerards y Kapoor (2000). Esta es una zona muy abierta. [ necesita actualización? ]
Una matroide regular es una matroide que se puede representar en todos los campos posibles. El matroide de 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 de la teoría de las matroides es la teoría de grafos .
Cada gráfico finito (o multigrafo ) da lugar a una matroide de la siguiente manera: tomar como el conjunto de todos los bordes en y considerar un conjunto de bordes independientes si y solo si es un bosque ; es decir, si no contiene un ciclo simple . Luegose llama ciclo matroide . Las matroides derivadas de esta forma son matroides gráficas . No todas las matroides son gráficas, pero todas las matroides de tres elementos son gráficas. [7] Cada matroide gráfico es regular.
Posteriormente se descubrieron otras matroides en los gráficos:
- La matroide bicircular de un gráfico se define llamando a un conjunto de aristas independientes si cada subconjunto conectado contiene como máximo un ciclo.
- En cualquier gráfico dirigido o no dirigido dejar y ser dos conjuntos distinguidos de vértices. En el set, define un subconjunto ser independiente si hay || caminos de vértice-disjuntos de sobre . Esto define una matroide enllamado gammoide : [8] un gammoide estricto es aquel para el que el conjunto es el conjunto completo de vértices de . [9]
- 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 emparejamientos del gráfico. Esto se llama matroide transversal , [10] [11] y es un caso especial de gammoide. [8] Las matroides transversales son las matroides duales a las gammoides estrictas. [9]
- 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, conocidos 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 del 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 da lugar a un gráfico sesgado y, por lo tanto, tienen matroides de marco y elevación.
- 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 .
- Dejar ser un gráfico conectado y sea su conjunto de bordes. Dejar ser la colección de subconjuntos de tal que todavía está conectado. Luego, cuyo conjunto de elementos es y con como su clase de conjuntos independientes, es una matroide llamada matroide de enlace de. La función de rangoes el número ciclomático del subgrafo inducido en el subconjunto de borde, 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 de extensiones de campo
Una tercera fuente original de teoría matroide es la teoría de campos .
Una extensión de un campo da lugar a una matroide. Suponer y son campos con conteniendo . Dejar ser cualquier subconjunto finito de . Definir un subconjunto de ser algebraicamente independiente si el campo de extensióntiene un grado de trascendencia igual a. [12]
Una matroide que es equivalente a una matroide de este tipo se llama matroide algebraica . [13] El problema de caracterizar las matroides algebraicas es extremadamente difícil; poco se sabe al respecto. El matroide de Vámos proporciona un ejemplo de un matroide que no es algebraico.
Construcciones basicas
Hay algunas formas estándar de hacer nuevas matroides a partir de las antiguas.
Dualidad
Si M es un matroide finita, podemos definir la ortogonales o matroide doble M * tomando el mismo conjunto subyacente y llamar a un conjunto de una base de M * si y sólo si su complemento es una base de M . No es difícil verificar que M * es un matroide y que el dual de M * es M . [14]
El dual puede describirse igualmente bien en términos de otras formas de definir un matroide. Por ejemplo:
- Un conjunto es independiente de M * si y sólo si sus tramos del complemento M .
- Un conjunto es un circuito de M * si y sólo si su complemento es un coatom en M .
- 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 M es una matroide gráfica si y solo si M es la matroide de un gráfico plano . En este caso, el dual de M es el matroid del gráfico doble de G . [15] El dual de un vector matroid representable en un campo en particular F también es representable sobre F . El dual de un matroide transversal es un gammoide estricto y viceversa.
Ejemplo
La matroide del ciclo de una gráfica es la matroide dual de su matroide de enlace.
Menores
Si M es una matroide con el conjunto de elementos E , y S es un subconjunto de E , la restricción de M a S , escrita M | S , es la matroid 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 RANK es la de M restringe a subconjuntos de S . En álgebra lineal, esto corresponde a la restricción al subespacio generado por los vectores en S . De manera equivalente, si T = M - S este puede denominarse la 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. [16] [17]
La doble operación de la restricción es la contracción. [18] Si T es un subconjunto de E , la contracción de M por T , escrito M / T , es la matroide en el conjunto subyacente E - T cuya función de rango es[19] En el á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 .
A matroid N que se obtiene de M por una secuencia de operaciones de restricción y contracción se denomina menor de M . [17] [20] Decimos que M contiene N como menor . Muchas familias importantes de matroides pueden caracterizarse por matroides menores-mínimos que no pertenecen a la familia; estos se denominan menores prohibidos o excluidos . [21]
Sumas y uniones
Deje que M sea un matroide con un conjunto subyacente de elementos E , y dejar que N sea otra matroide en un conjunto subyacente F . La suma directa de matroides M y N es el matroide cuyo conjunto subyacente es la unión disjunta de E y F , y cuyos conjuntos independientes son los sindicatos disjuntos de un conjunto independiente de M con un conjunto independiente de N .
La unión de M y N es el matroid cuyo conjunto subyacente es la unión (no la unión de la desunión) 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 . Por lo general, 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.
Terminología adicional
Deje que M sea un matroide con un conjunto subyacente de elementos E .
- E puede ser llamado el conjunto planta de M . Sus elementos pueden ser llamados los puntos de M .
- Un subconjunto de E abarca M si su cierre es E . Un conjunto se dice que abarcar un conjunto cerrado K si su cierre es K .
- La circunferencia de un matroide es el tamaño de su circuito más pequeño o conjunto dependiente.
- Un elemento que forma un circuito de un solo elemento de M se llama bucle . De manera equivalente, un elemento es un bucle si no pertenece a ninguna base. [7] [22]
- Un elemento que no pertenece a ningún circuito se llama coloop o istmo . De manera equivalente, un elemento es un coloop si pertenece a todas las bases. Loop y coloops son mutuamente duales. [22]
- Si un conjunto de dos elementos { f, g } es un circuito de M , a continuación, f y g son paralelo en M . [7]
- Una matroide se llama simple si no tiene circuitos que constan de 1 o 2 elementos. Es decir, no tiene bucles ni elementos paralelos. También se utiliza el término geometría combinatoria . [7] Un simple matroid obtenida de otra matroid M mediante la supresión de todos los bucles y eliminación de un elemento de cada circuito 2-elemento hasta que no hay circuitos de 2 elementos permanecen que se llama una simplificación de M . [23] Un matroide es co-simple si su matroide dual es simple. [24]
- Una unión de circuitos a veces se llama un ciclo de M . Por tanto, un ciclo es el complemento de un bemol del matroide dual. (Este uso entra en conflicto con el significado común de "ciclo" en la teoría de grafos).
- Un separador de M es un subconjunto S de E tal que. Un separador adecuado o no trivial es un separador que no es ni E ni el conjunto vacío. [25] Un separador irreducible es un separador que no contiene ningún otro separador no vacío. Los separadores irreducibles particionan el conjunto del suelo E .
- Una matroide que no puede escribirse como la suma directa de dos matroides no vacías, o equivalentemente que no tiene separadores adecuados, se llama conectada o irreducible . Un matroid está conectado si y solo si su dual está conectado. [26]
- A submatroid irreducible máxima de M se denomina un 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. [25]
- Una matroide M se llama frame matroid si, 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 base. [27]
- Un matroide se llama matroide de pavimentación si todos sus circuitos tienen un tamaño al menos igual a su rango. [28]
- El politopo matroide es el casco convexo de los vectores indicadores de las bases de.
Algoritmos
Algoritmo codicioso
Una matroide ponderada es una matroide junto con una función de sus elementos a los números reales no negativos . El peso de un subconjunto de elementos se define como la suma de los pesos de los elementos del subconjunto. El algoritmo codicioso se puede utilizar para encontrar una base de peso máximo de la matroide, comenzando desde el conjunto vacío y agregando repetidamente un elemento a la vez, en cada paso eligiendo un elemento de peso máximo entre los elementos cuya adición preservaría la independencia. del conjunto aumentado. [29] Este algoritmo no necesita saber nada sobre los detalles de la definición de la matroide, siempre que tenga acceso a la matroide a través de un oráculo de independencia , una subrutina para probar si un conjunto es independiente.
Este algoritmo de optimización se puede utilizar para caracterizar matroides: si una familia F de conjuntos, cerrados en 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 un matroide. [30]
La noción de matroide se ha generalizado para permitir otros tipos de conjuntos en los que un algoritmo codicioso proporciona soluciones óptimas; consulte la incrustación de greedoid y matroid para obtener más información.
Partición matroide
El problema de la partición matroide es dividir los elementos de una matroide en la menor cantidad posible de conjuntos independientes, y el problema del empaquetamiento de matroides es encontrar tantos conjuntos de expansión disjuntos como sea posible. Ambos pueden resolverse en tiempo polinomial y pueden generalizarse al problema de calcular el rango o encontrar un conjunto independiente en una suma matroide.
Intersección matroide
La intersección de dos o más matroides 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 el 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 Matroid
Dos sistemas independientes para cálculos con matroids 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 matroids. "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 un matroide finita M en el set de tierra E . Cada uno es un invariante matroide , lo que significa que los matroides isomorfos tienen el mismo polinomio.
Polinomio característico
El polinomio característico de M (que a veces se denomina polinomio cromático , [31] aunque no cuenta los colorantes), 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 celosía geométrica de la matroide y la suma se toma sobre todos los planos A de la matroide. [32]
Cuando M es el ciclo matroide M ( G ) de un gráfico G , el polinomio característico es una ligera transformación del polinomio cromático , que viene dado por χ G (λ) = λ c p M ( G ) (λ), donde c es el número de componentes conectados de G .
Cuando M es el vínculo matroid M * ( G ) de un gráfico de G , el polinomio característico es igual al polinomio flujo de G .
Cuando M es el matroide M ( A ) de un arreglo A de hiperplanos lineales en R n (o F n donde F es cualquier campo), el polinomio característico del arreglo viene dado por p A (λ) = λ n - r ( M ) p M ( A ) (λ).
Invariante beta
El invariante beta de un matroide, introducido por Crapo (1967), puede expresarse en términos del polinomio característico p 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 M está desconectado, vacío o en un bucle. De lo contrario, sólo depende de la red de pisos de M . Si M no tiene bucles ni coloops, entonces β ( M ) = β ( M ∗ ). [34]
Polinomio de Tutte
El polinomio de Tutte de un matroide, T M ( x , y ), generaliza el polinomio característico a dos variables. Esto le da más interpretaciones combinatorias y también le da la propiedad de dualidad.
lo que implica una serie de dualidades entre las propiedades de M y las propiedades de M *. Una definición del polinomio de Tutte es
Esto expresa el polinomio de Tutte como una evaluación del polinomio generador de rango o nulidad de rango , [35]
De esta definición es fácil ver que el polinomio característico es, hasta un factor simple, una evaluación de T M , 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 T (1,1) es el número de bases. [36] Esto, que suma menos subconjuntos pero tiene términos más complicados, era la definición original de Tutte.
Hay una definición más amplia en términos de recursividad por supresión y contracción. [37] La identidad de deleción-contracción es
- Cuándo no es un bucle ni un coloop.
Un invariante de matroides (es decir, una función que toma el mismo valor en matroides isomórficos) que satisface esta recursividad y la condición multiplicativa
se dice que es una 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 uno de esos invariantes es una evaluación del polinomio de Tutte. [31]
El polinomio de Tutte T G de un gráfico es el polinomio de Tutte T M ( G ) 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 forma 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 captar todos los aspectos importantes de la teoría de la 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 finito .
La siguiente generalización infinita más simple son las matroides finitarias. Un matroide es finitario si tiene la propiedad que
De manera equivalente, cada 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 grado de trascendencia posiblemente infinito. Una vez más, la clase de matroide finitario no es auto-dual, porque el dual de un matroide finitario no es finitario. Las matroides infinitas finitarias 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. Muchas nociones de matroides infinitos se definieron en respuesta a este desafío, pero la pregunta permaneció abierta. Uno de los enfoques examinados por DA Higgs se conoció como B-matroides y fue estudiado por Higgs, Oxley y otros en las décadas de 1960 y 1970. Según un resultado reciente de Bruhn, Diestel y Kriesell 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 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.
- Cada subconjunto de un conjunto independiente es independiente.
- Por cada nonmaximal (bajo inclusión set) conjunto independiente I y conjunto independiente maximal J , hay tal que es independiente.
- Para cada subconjunto X del espacio de base, cada subconjunto independiente I de X se puede extender a un subconjunto independiente máxima de X .
Con estos axiomas, cada matroide tiene un dual.
Historia
La teoría matroide fue introducida por Hassler Whitney ( 1935 ). También fue descubierto de forma independiente por Takeo Nakasawa , cuyo trabajo fue olvidado durante muchos años ( Nishimura & Kuroda 2009 ).
En su artículo fundamental, Whitney proporcionó dos axiomas para la independencia y definió cualquier estructura que se adhiera a estos axiomas como "matroides". (Aunque quizás estaba implícito, no incluyó un axioma que requiera que al menos un subconjunto sea independiente). 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 usados en la teoría matroide se asemejan 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, Saunders Mac Lane ( 1936 ) escribió un artículo importante sobre la relación de las matroides con la geometría proyectiva . Un año más tarde, BL van der Waerden ( 1937 ) notó 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 la teoría bajo el nombre de "sistemas de independencia" con miras a la teoría transversal , donde su nombre para el tema todavía se usa a veces.
En la década de 1950, WT Tutte se convirtió en la figura más destacada de la teoría matroide, cargo que mantuvo durante muchos años. Sus aportes fueron abundantes, incluyendo la caracterización de matroides binarias , regulares y gráficas por parte de menores excluidos ; el teorema de la representabilidad de la matroide regular; la teoría de los grupos en cadena y sus matroides; y las herramientas que usó para probar muchos de sus resultados, el "teorema de la ruta" y el " teorema de la homotopía de Tutte " (ver, por ejemplo, Tutte 1965 ), que son tan complejos que los teóricos posteriores se han tomado grandes problemas para eliminar la necesidad de utilizar ellos en pruebas. (Un buen ejemplo es la breve prueba de AMH Gerards ( 1989 ) de la caracterización de Tutte de las matroides regulares).
Henry Crapo ( 1969 ) y Thomas Brylawski ( 1972 ) generalizaron a las matroides el "dicromato" de Tutte, un polinomio gráfico ahora conocido como polinomio de Tutte (nombrado 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 en el polinomio de Tutte de un gráfico.
En 1976, Dominic Welsh publicó el primer libro completo sobre teoría matroide.
El teorema de descomposición de Paul Seymour para matroides regulares ( 1980 ) fue el trabajo más significativo e influyente de finales de los años setenta y ochenta. 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 matroide.
En ese momento había 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 ), quizás la mayor contribución individual de la década de 1990 . En el período actual (desde alrededor de 2000) el Proyecto Matroid Minors de Jim Geelen , Gerards, Whittle y otros, que intenta duplicar para matroids que son representables en un campo finito el éxito del Proyecto Robertson-Seymour Graph Minors (ver Robertson –Teorema de Seymour ), ha producido avances sustanciales en la teoría de la estructura 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 a Takeo Nakasawa , [38] Saunders Mac Lane , Richard Rado , WT Tutte , BL van der Waerden y Hassler Whitney . Otros contribuyentes importantes incluyen a Jack Edmonds , Jim Geelen , Eugene Lawler , László Lovász , Gian-Carlo Rota , PD Seymour y Dominic Welsh .
Ver también
- Antimatroide
- Matroide coxeter
- Matroide orientado
- Pregeometría (teoría de modelos)
- Polimatroide
- Greedoid
Notas
- ^ Neel, David L .; Neudauer, Nancy Ann (2009). "Matroids que has conocido" (PDF) . Revista de Matemáticas . 82 (1): 26–41. doi : 10.4169 / 193009809x469020 . Consultado el 4 de octubre de 2014 .
- ^ Kashyap, Navin; Soljanin, Emina; Vontobel, Pascal. "Aplicaciones de la teoría matroide y la optimización combinatoria a la teoría de la información y la codificación" (PDF) . www.birs.ca . Consultado el 4 de octubre de 2014 .
- ^ Una fuente estándar de definiciones básicas y resultados sobre matroides es Oxley (1992). Una fuente estándar más antigua es Welsh (1976). Véase el apéndice de Brylawski en White (1986), págs. 298-302, para obtener una lista de sistemas de axiomas equivalentes.
- ↑ a b c d e Welsh (1976) , Sección 1.2, "Axiom Systems for a Matroid", págs. 7-9.
- ^ Galés (1976) , Sección 1.8, "Conjuntos cerrados = Pisos = Subespacios", págs. 21-22.
- ↑ a b Welsh (1976) , Sección 2.2, "Los hiperplanos de un Matroid", págs. 38-39.
- ↑ a b c d Oxley , 1992 , p. 13
- ↑ a b Oxley , 1992 , págs. 115
- ↑ a b Oxley , 1992 , p. 100
- ^ Oxley 1992 , págs. 46–48
- ^ 1987
- ^ Oxley 1992 , p. 215
- ^ Oxley 1992 , p. 216
- ^ White 1986 , p. 32
- ^ White 1986 , p. 105
- ^ White 1986 , p. 131
- ↑ a b White , 1986 , p. 224
- ^ White 1986 , p. 139
- ^ White 1986 , p. 140
- ^ White 1986 , p. 150
- ^ White 1986 , págs. 146-147
- ↑ a b White , 1986 , p. 130
- ^ Oxley 1992 , p. 52
- ^ Oxley 1992 , p. 347
- ↑ a b Oxley , 1992 , p. 128
- ^ White 1986 , p. 110
- ^ Zaslavsky, Thomas (1994). "Frame matroids y gráficos sesgados" . EUR. J. Comb . 15 (3): 303–307. doi : 10.1006 / eujc.1994.1034 . ISSN 0195-6698 . Zbl 0797.05027 .
- ^ Oxley 1992 , p. 26
- ^ Oxley 1992 , p. 63
- ^ Oxley 1992 , p. 64
- ↑ a b White , 1987 , p. 127
- ^ White 1987 , p. 120
- ^ White 1987 , p. 123
- ↑ a b White , 1987 , p. 124
- ↑ a b White , 1987 , p. 126
- ^ White 1992 , p. 188
- ^ White 1986 , p. 260
- ^ Nishimura y Kuroda (2009) .
Referencias
- Bruhn, Henning; Diestel, Reinhard; Kriesell, Matthias; Pendavingh, Rudi; Wollan, Paul (2013), "Axiomas para matroides infinitos", Advances in Mathematics , 239 : 18–46, arXiv : 1003.3919 , doi : 10.1016 / j.aim.2013.01.011 , MR 3045140 , S2CID 10436077.
- Bryant, Víctor; Perfect, Hazel (1980), Independence Theory in Combinatorics , Londres y Nueva York: Chapman y Hall, ISBN 978-0-412-22430-0.
- Brylawski, Thomas H. (1972), "Una descomposición para geometrías combinatorias", Transactions of the American Mathematical Society , 171 : 235-282, doi : 10.2307 / 1996381 , JSTOR 1996381.
- Crapo, Henry H. (1969), "El polinomio de Tutte", Aequationes 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, Mass .: MIT Press, ISBN 978-0-262-53016-3, MR 0290980.
- Geelen, Jim; Gerards, AMH; Whittle, Geoff (2007), "Hacia una teoría de la estructura matroide-menor", en Grimmett, Geoffrey; et al. (eds.), Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh , Oxford Lecture Series in Mathematics and its Applications, 34 , Oxford: Oxford University Press, págs. 72–82.
- Gerards, AMH (1989), "Una prueba corta 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), "Varieties of combinatorial geometries", Transactions of the American Mathematical Society , 271 (2): 485–499, doi : 10.2307 / 1998894 , JSTOR 1998894.
- Kingan, Robert; Kingan, Sandra (2005), "A software system for matroids", Graphs and Discovery , Serie DIMACS en Matemáticas Discretas y Ciencias de la Computación Teórica, págs. 287–296.
- Kung, Joseph PS, ed. (1986), A Source Book in Matroid Theory , Boston: Birkhäuser, doi : 10.1007 / 978-1-4684-9199-9 , ISBN 978-0-8176-3173-4, MR 0890330.
- Mac Lane, Saunders (1936), "Algunas interpretaciones de la dependencia lineal abstracta en términos de geometría proyectiva", American Journal of Mathematics , 58 (1): 236-240, doi : 10.2307 / 2371070 , JSTOR 2371070.
- Minty, George J. (1966), "Sobre los fundamentos axiomáticos de las teorías de gráficos lineales dirigidos, redes eléctricas y programación de redes", Journal of Mathematics and Mechanics , 15 : 485–520, MR 0188102.
- Nishimura, Hirokazu; Kuroda, Susumu, eds. (2009), Un matemático perdido, Takeo Nakasawa. El padre olvidado de la teoría matroide , Basilea: Birkhäuser Verlag, doi : 10.1007 / 978-3-7643-8573-6 , ISBN 978-3-7643-8572-9, MR 2516551 , Zbl 1163.01001.
- Oxley, James (1992), Teoría Matroide , Oxford: Oxford University Press, ISBN 978-0-19-853563-8, MR 1207587 , Zbl 0.784,05002.
- Recski, András (1989), Matroid Theory and its Applications in Electric Network Theory and in Statics , Algorithms and Combinatorics, 6 , Berlín y Budapest: Springer-Verlag y Akademiai Kiado, doi : 10.1007 / 978-3-662-22143-3 , ISBN 978-3-540-15285-9, MR 1027839.
- Sapozhenko, AA (2001) [1994], "Matroid" , Encyclopedia of Mathematics , EMS Press
- Seymour, Paul D. (1980), "Descomposición de matroides regulares", Journal of Combinatorial Theory, Serie B , 28 (3): 305–359, doi : 10.1016 / 0095-8956 (80) 90075-1 , hdl : 10338 .dmlcz / 101946 , Zbl 0443.05027.
- Truemper, Klaus (1992), Descomposición de matroides , Boston: Academic Press, ISBN 978-0-12-701225-4, MR 1170126.
- Tutte, WT (1959), "Matroids and graphs", Transactions of the American Mathematical Society , 90 (3): 527–552, doi : 10.2307 / 1993185 , JSTOR 1993185 , MR 0101527.
- Tutte, WT (1965), "Lectures on matroids", Journal of Research of the National Bureau of Standards Section B , 69 : 1–47.
- Tutte, WT (1971), Introducción a la teoría de las matroides , Métodos analíticos y computacionales modernos en ciencia y matemáticas, 37 , Nueva York: American Elsevier Publishing Company, Zbl 0231.05027.
- Vámos, Peter (1978), "El axioma faltante de la teoría matroide se pierde para siempre", Journal of the London Mathematical Society , 18 (3): 403–408, doi : 10.1112 / jlms / s2-18.3.403.
- van der Waerden, BL (1937), Álgebra Moderna.
- Galés, DJA (1976), Teoría Matroide , Monografías de LMS, 8 , Academic Press, ISBN 978-0-12-744050-7, Zbl 0343.05002.
- White, Neil, ed. (1986), Teoría de las Matroides , Enciclopedia de las Matemáticas y sus Aplicaciones, 26 , Cambridge: Cambridge University Press, ISBN 978-0-521-30937-0, Zbl 0579.00001.
- White, Neil, ed. (1987), geometrías combinatorias , Enciclopedia de las matemáticas y sus aplicaciones, 29 , Cambridge: Cambridge University Press , ISBN 978-0-521-33339-9, Zbl 0626.00007
- White, Neil, ed. (1992), Matroid Applications , Encyclopedia of Mathematics and its Applications, 40 , Cambridge: Cambridge University Press, ISBN 978-0-521-38165-9, Zbl 0742.00052.
- Whitney, Hassler (1935), "Sobre las propiedades abstractas de la dependencia lineal", American Journal of Mathematics , 57 (3): 509–533, doi : 10.2307 / 2371182 , hdl : 10338.dmlcz / 100694 , JSTOR 2371182 , MR 1507091. Reimpreso en Kung (1986) , págs. 55–79.
- Whittle, Geoff (1995), "Una caracterización de las matroides representables sobre GF (3) y los racionales" (PDF) , Journal of Combinatorial Theory, Serie B , 65 (2): 222-261, doi : 10.1006 / jctb. 1995.1052[ enlace muerto permanente ] .
enlaces externos
- "Matroid" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
- Kingan, Sandra: teoría matroide . Una gran bibliografía de artículos matroid, software matroid y enlaces.
- Locke, SC: algoritmos codiciosos .
- Pagano, Steven R.: Matroides y gráficos firmados .
- Mark Hubenthal: A Brief Look At Matroids ( PDF ) (contiene pruebas de las declaraciones de este artículo)
- James Oxley: ¿Qué es un matroide? (PDF)
- Neil White: Aplicaciones de Matroid