La conjetura de los menores excluidos de Rota es una de varias conjeturas hechas por el matemático Gian-Carlo Rota . Algunos miembros de la comunidad de combinatoria estructural lo consideran un problema importante. Rota conjeturó en 1971 que, por cada campo finito , la familia de matroides que puede representarse sobre ese campo sólo tiene un número finito de menores excluidos . [1] Geelen, Gerards y Whittle han anunciado una prueba de la conjetura. [2]
Declaración de la conjetura
Si es un conjunto de puntos en un espacio vectorial definido sobre un campo, entonces los subconjuntos linealmente independientes de forman los conjuntos independientes de un matroide ; se dice que es una representación de cualquier matroide isomorfo a. No todos los matroides tienen una representación sobre todos los campos, por ejemplo, el plano de Fano es representable solo sobre campos de la característica dos. Otras matroides no se pueden representar en ningún campo. Las matroides que se pueden representar en un campo en particular forman una subclase adecuada de todas las matroides.
Un menor de un matroide es otro matroide formado por una secuencia de dos operaciones: deleción y contracción. En el caso de puntos de un espacio vectorial, eliminar un punto es simplemente eliminar ese punto de; La contracción es una operación dual en la que se elimina un punto y los puntos restantes se proyectan en un hiperplano que no contiene los puntos eliminados. De esto se deduce que si un matroide es representable sobre un campo, también lo son todos sus menores. Una matroide que no es representable sobre, y es menor- mínimo con esa propiedad, se llama "menor excluido"; una matroide es representable sobre si y solo si no contiene alguno de los menores prohibidos.
Para la representabilidad sobre los números reales , hay infinidad de menores prohibidos. [3] La conjetura de Rota es que, para cada campo finito, solo hay un número finito de menores prohibidos.
Resultados parciales
WT Tutte demostró que las matroides binarias (matroides representables sobre el campo de dos elementos) tienen un solo menor prohibido, la matroide uniforme (geométricamente, una línea con cuatro puntos). [4] [5]
Una matroide es representable sobre el campo ternario GF (3) si y solo si no tiene una o más de las siguientes cuatro matroides como menores: una línea de cinco puntos , su doble matroide (cinco puntos en posición general en tres dimensiones), el plano Fano, o el dual del plano Fano. Por tanto, la conjetura de Rota también es cierta en este caso. [6] [7] Como consecuencia de este resultado y de la caracterización menor prohibida por Tutte (1958) de las matroides regulares (matroides que se pueden representar en todos los campos) se sigue que una matroide es regular si y solo si es tanto binarios como ternarios. [7]
Hay siete menores prohibidos para las matroides representables sobre GF (4). [8] Ellos son:
- La línea de seis puntos .
- El dual a la línea de seis puntos, seis puntos en posición general en cuatro dimensiones.
- Una matroide de rango tres de seis puntos auto-dual con una sola línea de tres puntos.
- La matroide no Fano formada por los siete puntos en los vértices, los puntos medios de los bordes y el centroide de un triángulo equilátero en el plano euclidiano . Esta configuración es uno de los dos conjuntos conocidos de puntos planos con menos de líneas de dos puntos . [9]
- El dual del matroide que no es Fano.
- La matroide de ocho puntos de un antiprisma cuadrado .
- El matroide obtenido al relajar el par único de circuitos-hiperplanos inconexos del antiprisma cuadrado.
Este resultado ganó el premio Fulkerson 2003 para sus autores Jim Geelen , AMH Gerards y A. Kapoor. [10]
Para GF (5), se conocen varios menores prohibidos en hasta 12 elementos, [11] pero no se sabe si la lista está completa.
Prueba reportada
Geoff Whittle anunció durante una visita al Reino Unido en 2013 que él, Jim Geelen y Bert Gerards habían resuelto la conjetura de Rota. La colaboración implicó intensas visitas en las que los investigadores se sentaron juntos en una sala, todo el día, todos los días, frente a una pizarra. [12] Les llevará años redactar su investigación en su totalidad y publicarla. [13] [14] Un resumen de la prueba ha aparecido en los Avisos de la AMS. [15]
Ver también
- Conjetura de la base de Rota , una conjetura diferente de Rota sobre el álgebra lineal y las matroides
Referencias
- ^ 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.
- ^ "Resolviendo la conjetura de Rota" (PDF) , Notices of the American Mathematical Society : 736–743, 17 de agosto de 2014
- ^ 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.
- ^ Tutte, WT (1958), "Un teorema de homotopía para matroides. I, II", Transactions of the American Mathematical Society , 88 : 144-174, doi : 10.2307 / 1993244 , MR 0101526.
- ^ Tutte, WT (1965), "Lectures on matroids" , Journal of Research of the National Bureau of Standards , 69B : 1–47, doi : 10.6028 / jres.069b.001 , MR 0179781. Ver en particular la sección 5.3, "Caracterización de matroides binarios", p.17.
- ^ Bixby, Robert E. (1979), "Sobre la caracterización de Reid de las matroides ternarias", Journal of Combinatorial Theory , Serie B, 26 (2): 174-204, doi : 10.1016 / 0095-8956 (79) 90056-X , Señor 0532587. Bixby atribuye esta caracterización de matroides ternarios a Ralph Reid.
- ^ a b Seymour, PD (1979), "Representación matroide sobre GF (3)", Journal of Combinatorial Theory , Serie B, 26 (2): 159-173, doi : 10.1016 / 0095-8956 (79) 90055-8 , MR 0532586.
- ^ Geelen, JF ; Gerards, AMH; Kapoor, A. (2000), "Los menores excluidos de las matroides representables por GF (4)" (PDF) , Journal of Combinatorial Theory , Serie B, 79 (2): 247–299, doi : 10.1006 / jctb.2000.1963 , MR 1769191 , archivado desde el original (PDF) el 2010-09-24.
- ^ Kelly, LM ; Moser, WOJ (1958), "Sobre el número de líneas ordinarias determinadas por n puntos" , Can. J. Math. , 10 : 210–219, doi : 10.4153 / CJM-1958-024-6.
- ^ Cita del premio Fulkerson 2003, consultado el 18 de agosto de 2012 .
- ^ Betten, A .; Kingan, RJ; Kingan, SR (2007), "A note on GF (5) -representable matroids" (PDF) , MATCH Communications in Mathematical and in Computer Chemistry , 58 (2): 511-521, MR 2357372[ enlace muerto permanente ] .
- ^ Geelen, Gerards y Whittle anuncian una prueba de la conjetura de Rota Universidad de Waterloo, 28 de agosto de 2013
- ^ Conjetura de Rota: Investigador resuelve un problema matemático de 40 años PhysOrg, 15 de agosto de 2013.
- ^ Investigador de CWI demuestra la famosa conjetura de Rota Archivado el 26 deoctubre de 2013en elCWI de Wayback Machine , 22 de agosto de 2013.
- ^ "Resolviendo la conjetura de Rota" (PDF) , Notices of the American Mathematical Society : 736–743, 17 de agosto de 2014