En la teoría matemática de matroides , un menor de un matroide M es otro matroide N que se obtiene de M mediante una secuencia de operaciones de restricción y contracción. Los menores de Matroid están estrechamente relacionados con los menores de gráficos , y las operaciones de restricción y contracción por las que se forman corresponden a las operaciones de eliminación y contracción de bordes en los gráficos. La teoría de los menores matroides conduce a descomposiciones estructurales de los matroides y caracterizaciones de las familias matroides por menores prohibidos, análoga a la teoría correspondiente en los gráficos.
Definiciones
Si M es una matroide en el conjunto E y S es un subconjunto de E , entonces 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 .
Si T es un subconjunto independiente de E , la contracción de M por T , escrito M / T , es la matroide en el conjunto subyacente E - T cuyos conjuntos independientes son los conjuntos cuya unión con T es independiente de M . Esta definición puede extenderse a arbitraria T por la elección de una base para la T y la definición de un conjunto para ser independiente en la contracción si su unión con esta base se mantiene independiente de M . La función de rango de la contracción es
Un matroid N es menor de un matroid M si se puede construir a partir de M mediante operaciones de restricción y contracción.
En términos de la celosía geométrica formada por los planos de una matroide, tomar un menor de una matroide corresponde a tomar un intervalo de la celosía, la parte de la celosía que se encuentra entre un elemento de límite inferior y superior dado. [1]
Caracterizaciones matroides prohibidas
Muchas familias importantes de matroides se cierran bajo la operación de tomar menores: si un matroide M pertenece a la familia, entonces todos los menores de M también pertenecen a la familia. En este caso, la familia puede caracterizarse por su conjunto de "matroides prohibidos", los matroides menores-mínimos que no pertenecen a la familia. Un matroid pertenece a la familia si y solo si no tiene un matroid prohibido como menor de edad. A menudo, pero no siempre, el conjunto de matroides prohibidos 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 las matroides regulares , matroides que se pueden representar en todos los campos. De manera equivalente, una matroide es regular si se puede representar mediante una matriz totalmente unimodular (una matriz cuyas submatrices cuadradas tienen determinantes iguales a 0, 1 o -1). Tutte (1958) demostró que un matroid es regular si y solo si no tiene uno de los tres menores prohibidos: el uniforme matroid (la línea de cuatro puntos), el plano de Fano o el matroide dual del plano de Fano. Para ello utilizó su difícil teorema de homotopía . Desde entonces se han encontrado pruebas más sencillas.
Las matroides gráficas , matroides cuyos conjuntos independientes son los subgrafos forestales de un gráfico, tienen cinco menores prohibidos: los tres para las matroides regulares, y los dos duales de las matroides gráficas para las gráficas K 5 y K 3,3 que por el teorema de Wagner Están prohibidos los menores de edad para las gráficas planas .
Las matroides binarias , matroides representables sobre el campo finito de dos elementos , incluyen matroides gráficas y regulares. Tutte volvió a demostrar que estas matroides tienen una caracterización menor prohibida: son las matroides que no tienen la línea de cuatro puntos como menor. Rota conjeturó que, para cualquier campo finito, las matroides representables sobre ese campo tienen un número finito de menores prohibidos. [2] Geelen, Gerards y Whittle han anunciado una prueba completa de esta conjetura; [3] a partir de 2015[actualizar]no ha aparecido. Sin embargo, las matroides que se pueden representar sobre los números reales tienen infinitos menores prohibidos. [4]
Ancho de rama
Las descomposiciones de ramas de las matroides pueden definirse de forma análoga a su definición para gráficos. La descomposición de una rama de un matroide es un agrupamiento jerárquico de los elementos matroides, representados como un árbol binario sin raíces con los elementos del matroide en sus hojas. Al eliminar cualquier borde de este árbol, las matroides se dividen en dos subconjuntos disjuntos; tal partición se llama separación electrónica. Si r denota la función de rango de la matroide, entonces el ancho de una separación e 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 rama.
El ancho de rama de un gráfico y el ancho de rama del matroide gráfico correspondiente pueden diferir: por ejemplo, el gráfico de ruta de tres bordes y la estrella de tres bordes tienen anchos de rama diferentes, 2 y 1 respectivamente, pero ambos inducen el mismo matroide gráfico con ancho de rama 1. [5] Sin embargo, para gráficos que no son árboles, el ancho de rama del gráfico 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 grafos menores a matroides: aunque el ancho de árbol también se puede generalizar a matroides, [7] y juega un papel más importante que el ancho de rama en la teoría de grafos menores, el ancho de rama tiene propiedades más convenientes en la entorno matroide. [8] Si una familia de matroides menor-cerrada representable sobre un campo finito no incluye las matroides gráficas de todos los gráficos planos, entonces hay un límite constante en el ancho de rama de las matroides en la familia, generalizando resultados similares para menor-cerrado familias de gráficos. [9]
Bien casi ordenado
El teorema de Robertson-Seymour implica que cada propiedad matroide de las matroides gráficas caracterizadas por una lista de menores prohibidos puede caracterizarse por una lista finita. Otra forma de decir lo mismo es que el orden parcial en las matroides gráficas formado por la operación menor es un buen cuasi ordenamiento . Sin embargo, el ejemplo de las matroides real-representables, que tienen infinitos menores prohibidos, muestra que la ordenación menor no es una buena cuasi ordenación en todas las matroides.
Robertson y Seymour conjeturaron que las matroides representables sobre cualquier campo finito particular están bien cuasi ordenadas. Hasta ahora, esto se ha probado solo para las matroides de ancho de rama acotado. [10]
Descomposiciones matroides
El teorema de estructura de grafos es una herramienta importante en la teoría de grafos menores, según el cual los grafos de cualquier familia menor cerrada 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 matroide. En particular, el teorema de descomposición de Seymour establece que todas las matroides regulares se pueden construir de una manera simple como la suma de las matroides gráficas, sus duales y una 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ínimos correspondientes a las partes gráficas y cográficas de esta descomposición.
Algoritmos y complejidad
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 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 fijo -parámetro manejable si se permite que varíe el tamaño de H ). Combinando este resultado con el teorema de Robertson-Seymour, es posible reconocer los miembros de cualquier familia de grafos cerrados menores en tiempo polinomial . En consecuencia, en la teoría matroide, sería deseable desarrollar algoritmos eficientes para reconocer si una matroide fija dada es menor de una matroide de entrada. Desafortunadamente, un resultado tan fuerte no es posible: en el modelo del oráculo matroide , los únicos menores que pueden ser reconocidos en tiempo polinomial son los matroides uniformes con rango o corank. [12] Sin embargo, si el problema se restringe a las matroides que son representables sobre algún campo finito fijo (y representadas como una matriz sobre ese campo), entonces, como en el caso del gráfico, se conjetura que es posible reconocer las matroides que contener cualquier menor fijo en tiempo polinomial. [8]
Notas
- ^ Galés (2010) .
- ^ Rota (1971) .
- ^ "Resolver la conjetura de Rota" (PDF) , Avisos de la American Mathematical Society : 736–743, 17 de agosto de 2014
- ^ Vámos (1978) .
- ↑ a b Mazoit y Thomassé (2007) .
- ^ Mazoit y Thomassé (2007) ; Hicks y McMurray (2007) .
- ^ Hliněný y Whittle (2006) .
- ↑ a b Geelen, Gerards y Whittle (2006) .
- ^ Geelen, Gerards y Whittle (2006) ; Geelen, Gerards y Whittle (2007) .
- ^ Geelen, Gerards y Whittle (2002) ; Geelen, Gerards y Whittle (2006) .
- ^ Seymour (1980) .
- ^ Seymour y Walton (1981) .
Referencias
- Geelen, JF ; Gerards, AMH; Kapoor, A. (2000), "Los menores excluidos por GF (4) -representable matroids" , Journal of Combinatorial Theory , Serie B, 79 (2): 247–299, doi : 10.1006 / jctb.2000.1963 , MR 1769191.
- Geelen, Jim ; Gerards, Bert; Robertson, Neil ; Whittle, Geoff (2003), "Sobre los menores excluidos para las matroides de ancho de rama k ", Journal of Combinatorial Theory , Serie B, 88 (2): 261-265, doi : 10.1016 / S0095-8956 (02) 00046 -1.
- Geelen, Jim ; Gerards, Bert; Whittle, Geoff (2002), "Branch-width and well-cuasi-ordering in matroids and graphs" , Journal of Combinatorial Theory , Serie B, 84 (2): 270-290, doi : 10.1006 / jctb.2001.2082.
- Geelen, Jim ; Gerards, Bert; Whittle, Geoff (2006), "Hacia una teoría de la estructura de matrices y matroides" (PDF) , Proc. Congreso Internacional de Matemáticos , III , págs. 827–842.
- Geelen, Jim ; Gerards, Bert; Whittle, Geoff (2007), "Excluyendo un gráfico plano de las matroides representables por GF ( q )" (PDF) , Journal of Combinatorial Theory , Serie B, 97 (6): 971–998, doi : 10.1016 / j.jctb. 2007.02.005 , archivado desde el original (PDF) el 2010-09-24.
- Hicks, Illya V .; McMurray, Nolan B., Jr. (2007), "El ancho de rama de los gráficos y sus matroides de ciclo", Journal of Combinatorial Theory , Serie B, 97 (5): 681–692, doi : 10.1016 / j.jctb.2006.12. 007.
- Hliněný, Petr (2003), "Sobre propiedades matroides definibles en la lógica MSO", Proc. 28th International Symposium on Mathematical Foundations of Computer Science (MFCS '03) , Lecture Notes in Computer Science, 2747 , Springer-Verlag, págs. 470–479, doi : 10.1007 / 978-3-540-45138-9_41
- Hliněný, Petr; Whittle, Geoff (2006), "Matroid tree-width" (PDF) , European Journal of Combinatorics , 27 (7): 1117–1128, doi : 10.1016 / j.ejc.2006.06.005 , archivado desde el original (PDF) el 2012-03-06 , consultado el 2012-08-17. Addendum y corrigendum: Hliněný, Petr; Whittle, Geoff (2009), "Addendum to matroid tree-width", European Journal of Combinatorics , 30 (4): 1036–1044, doi : 10.1016 / j.ejc.2008.09.028.
- Mazoit, Frédéric; Thomassé, Stéphan (2007), "Branchwidth of graphic matroids", en Hilton, Anthony; Talbot, John (eds.), Surveys in Combinatorics 2007 (PDF) , London Mathematical Society Lecture Note Series, 346 , Cambridge University Press, p. 275.
- Rota, Gian-Carlo (1971), "Teoría combinatoria, vieja y nueva", Actes du Congrès International des Mathématiciens (Niza, 1970), tomo 3 , París: Gauthier-Villars, págs. 229-233, MR 0505646.
- Seymour, PD (1980), "Decomposition of regular matroids", Journal of Combinatorial Theory , Serie B, 28 (3): 305–359, doi : 10.1016 / 0095-8956 (80) 90075-1 , MR 0579077.
- Seymour, PD ; Walton, PN (1981), "Detecting matroid minors", Journal of the London Mathematical Society , Segunda serie, 23 (2): 193-203, doi : 10.1112 / jlms / s2-23.2.193 , MR 0609098.
- Tutte, WT (1958), "Un teorema de homotopía para matroides. I, II", Transactions of the American Mathematical Society , 88 (1): 144-174, doi : 10.2307 / 1993244 , JSTOR 1993244 , MR 0101526.
- Vámos, P. (1978), "El axioma faltante de la teoría matroide se pierde para siempre", Journal of the London Mathematical Society , Second Series, 18 (3): 403–408, doi : 10.1112 / jlms / s2-18.3.403 , MR 0518224.
- Welsh, DJA (2010) [1976], "4.4 Menores y su representación en el enrejado", Matroid Theory , Courier Dover Publications, págs. 65–67, ISBN 9780486474397.