En la teoría matemática de matroides , un menor de un matroide M es otro matroide N que se obtiene a partir de M mediante una secuencia de operaciones de restricción y contracción. Los menores de matroides están estrechamente relacionados con los menores de grafos , y las operaciones de restricción y contracción mediante las cuales se forman corresponden a las operaciones de eliminación de aristas y contracción de aristas en grafos. La teoría de menores de matroides conduce a descomposiciones estructurales de matroides y caracterizaciones de familias de matroides por menores prohibidos, análogas a la teoría correspondiente en grafos.
Si M es un matroide en el conjunto E y S es un subconjunto de E , entonces 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 .
Si T es un subconjunto independiente de E , la contracción de M por T , escrita M / T , es el matroide sobre el conjunto subyacente E − T cuyos conjuntos independientes son los conjuntos cuya unión con T es independiente en M . Esta definición puede extenderse a un conjunto arbitrario de T eligiendo una base para T y definiendo un conjunto como independiente en la contracción si su unión con esta base permanece independiente en M . La función de rango de la contracción es
Un matroide N es un menor de un matroide M si puede construirse a partir de M mediante operaciones de restricción y contracción.
En términos de la red geométrica formada por los planos de un matroide, tomar un menor de un matroide corresponde a tomar un intervalo de la red, la parte de la red que se encuentra entre un elemento de límite inferior y un elemento de límite superior dados. [1]
Muchas familias importantes de matroides están cerradas bajo la operación de tomar menores: si un matroide M pertenece a la familia, entonces cada menor de M también pertenece a la familia. En este caso, la familia puede caracterizarse por su conjunto de "matroides prohibidas", las matroides menores-minimalistas que no pertenecen a la familia. Un matroide pertenece a la familia si y solo si no tiene un matroide prohibido como menor. A menudo, pero no siempre, el conjunto de matroides prohibidas es finito, en paralelo con el teorema de Robertson-Seymour que establece que el conjunto de menores prohibidos de una familia de grafos menores-cerrados es siempre finito.
Un ejemplo de este fenómeno lo dan los matroides regulares , matroides que son representables sobre todos los cuerpos. De manera equivalente, un matroide es regular si puede ser representado por una matriz totalmente unimodular (una matriz cuyas submatrices cuadradas tienen todas determinantes iguales a 0, 1 o −1). Tutte (1958) demostró que un matroide es regular si y solo si no tiene uno de los tres menores prohibidos: el matroide uniforme (la línea de cuatro puntos), el plano de Fano o el matroide dual del plano de Fano. Para esto utilizó su difícil teorema de homotopía . Desde entonces se han encontrado pruebas más simples.
Las matroides gráficas , matroides cuyos conjuntos independientes son los subgrafos del bosque de un grafo, tienen cinco menores prohibidos: los tres para las matroides regulares, y los dos duales de las matroides gráficas para los grafos K 5 y K 3,3 que por el teorema de Wagner son menores prohibidos para los grafos planares .
Las matroides binarias , matroides representables sobre el cuerpo finito de dos elementos , incluyen tanto matroides gráficas como regulares. Tutte volvió a demostrar que estas matroides tienen una caracterización de menor prohibido: son las matroides que no tienen la línea de cuatro puntos como menor. Rota conjeturó que, para cualquier cuerpo finito, las matroides representables sobre ese cuerpo tienen un número finito de menores prohibidos. [2] Una prueba de esta conjetura fue anunciada, pero no publicada, por Geelen, Gerards y Whittle en 2014. [3] Las matroides que se pueden representar sobre los números reales tienen un número infinito de menores prohibidos. [4]
Las descomposiciones de ramas de matroides pueden definirse de manera análoga a su definición para grafos. Una descomposición de ramas de un matroide es una agrupación jerárquica de los elementos del matroide, representada como un árbol binario sin raíz con los elementos del matroide en sus hojas. Al eliminar cualquier borde de este árbol, los matroides se dividen en dos subconjuntos disjuntos; dicha división se denomina e-separación. Si r denota la función de rango del matroide, entonces el ancho de una e-separación se define como r ( A ) + r ( B ) − r ( M ) + 1 . El ancho de una descomposición es el ancho máximo de cualquiera de sus e-separaciones, y el ancho de rama de un matroide es el ancho mínimo de cualquiera de sus descomposiciones de ramas.
El ancho de rama de un grafo y el ancho de rama del matroide gráfico correspondiente pueden diferir: por ejemplo, el grafo de ruta de tres aristas y la estrella de tres aristas tienen diferentes anchos de rama, 2 y 1 respectivamente, pero ambos inducen el mismo matroide gráfico con ancho de rama 1. [5] Sin embargo, para grafos que no son árboles, el ancho de rama del grafo es igual al ancho de rama de su matroide gráfico asociado. [6] El ancho de rama de un matroide siempre es igual al ancho de rama de su dual. [5]
El ancho de rama es un componente importante de los intentos de extender la teoría de los menores de grafos a los matroides: aunque el ancho de árbol también se puede generalizar a los matroides, [7] y juega un papel más importante que el ancho de rama en la teoría de los menores de grafos, el ancho de rama tiene propiedades más convenientes en el entorno de los matroides. [8] Si una familia de matroides menores-cerrada representable sobre un cuerpo finito no incluye los matroides gráficos de todos los grafos planares, entonces hay un límite constante en el ancho de rama de los matroides en la familia, generalizando resultados similares para familias de grafos menores-cerradas. [9]
El teorema de Robertson-Seymour implica que cada propiedad matroide de los matroides gráficos caracterizados por una lista de menores prohibidos puede ser caracterizada por una lista finita. Otra forma de decir lo mismo es que el orden parcial en los matroides gráficos formado por la operación de menor es un cuasi-ordenamiento adecuado . Sin embargo, el ejemplo de los matroides representables de manera real, que tienen un número infinito de menores prohibidos, muestra que el orden de los menores no es un cuasi-ordenamiento adecuado en todos los matroides.
Robertson y Seymour conjeturaron que las matroides representables sobre cualquier cuerpo finito particular están bien ordenadas. Hasta ahora esto se ha demostrado sólo para las matroides de ancho de rama acotado. [10]
El teorema de estructura de grafos es una herramienta importante en la teoría de grafos menores, según el cual los grafos en cualquier familia cerrada por menores pueden construirse a partir de grafos más simples mediante operaciones de suma de clique . También se conocen algunos resultados análogos en la teoría de matroides. En particular, el teorema de descomposición de Seymour establece que todos los matroides regulares pueden construirse de manera simple como la suma de clique de los matroides gráficos, sus duales y un matroide especial de 10 elementos. [11] Como consecuencia, los programas lineales definidos por matrices totalmente unimodulares pueden resolverse combinatoriamente combinando las soluciones a un conjunto de problemas de árbol de expansión mínimo correspondientes a las partes gráficas y cográficas de esta descomposición.
Uno de los componentes importantes de la teoría de grafos menores es la existencia de un algoritmo para probar si un grafo H es un menor de otro grafo G , tomando una cantidad de tiempo que es polinomial en G para cualquier elección fija de H (y más fuertemente manejable con parámetros fijos si se permite que el tamaño de H varíe). Al combinar este resultado con el teorema de Robertson-Seymour, es posible reconocer los miembros de cualquier familia de grafos menores cerrados en tiempo polinomial . En consecuencia, en la teoría de matroides, sería deseable desarrollar algoritmos eficientes para reconocer si un matroide fijo dado es un menor de un matroide de entrada. Desafortunadamente, un resultado tan fuerte no es posible: en el modelo de oráculo de matroides , los únicos menores que se pueden reconocer en tiempo polinomial son los matroides uniformes con rango o corank uno. [12] Sin embargo, si el problema se restringe a los matroides que son representables sobre algún campo finito fijo (y representados como una matriz sobre ese campo), entonces, como en el caso del gráfico, se conjetura que es posible reconocer los matroides que contienen cualquier menor fijo en tiempo polinomial. [8]
