Conjetura de Rota

Conjetura sobre menores prohibidos de matroides

La conjetura de Rota sobre los menores excluidos es una de las numerosas conjeturas formuladas por el matemático Gian-Carlo Rota . Algunos miembros de la comunidad de combinatoria estructural la consideran un problema importante. Rota conjeturó en 1971 que, para cada cuerpo finito , la familia de matroides que se puede representar sobre ese cuerpo tiene solo un número finito de menores excluidos . ^[1] Una prueba de la conjetura fue anunciada, pero no publicada, en 2014 por Geelen, Gerards y Whittle. ^[2]

Enunciado de la conjetura

Si es un conjunto de puntos en un espacio vectorial definido sobre un cuerpo , 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 cada cuerpo, por ejemplo, el plano de Fano es representable solo sobre cuerpos de característica dos. Otros matroides no son representables sobre ningún cuerpo. Los matroides que son representables sobre un cuerpo particular forman una subclase propia de todos los matroides. ${\displaystyle S}$ ${\displaystyle F}$ ${\displaystyle S}$ ${\displaystyle M}$ ${\displaystyle S}$ ${\displaystyle M}$

Un menor de un matroide es otro matroide formado por una secuencia de dos operaciones: eliminación y contracción. En el caso de puntos de un espacio vectorial, eliminar un punto es simplemente la eliminación de 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 cuerpo, entonces también lo son todos sus menores. Un matroide que no es representable sobre , y es mínimo menor con esa propiedad, se llama "menor excluido"; un matroide es representable sobre si y solo si no contiene uno de los menores prohibidos. ${\displaystyle S}$ ${\displaystyle F}$ ${\displaystyle M}$ ${\displaystyle F}$

Para la representabilidad sobre los números reales , hay infinitos menores prohibidos. ^[3] La conjetura de Rota es que, para cada cuerpo finito , solo hay un número finito de menores prohibidos. ${\displaystyle F}$

Resultados parciales

WT Tutte demostró que las matroides binarias (matroides representables sobre el campo de dos elementos) tienen un único menor prohibido, el matroide uniforme (geométricamente, una línea con cuatro puntos sobre ella). ^{[4] [5]} ${\displaystyle U{}_{4}^{2}}$

Un matroide es representable sobre el cuerpo ternario GF(3) si y sólo si no tiene uno o más de los siguientes cuatro matroides como menores: una línea de cinco puntos , su matroide dual (cinco puntos en posición general en tres dimensiones), el plano de Fano, o el dual del plano de Fano. Por lo tanto, la conjetura de Rota es verdadera también en este caso. ^{[6] [7]} Como consecuencia de este resultado y de la caracterización de menor prohibido por Tutte (1958) de los matroides regulares (matroides que pueden representarse sobre todos los cuerpos) se sigue que un matroide es regular si y sólo si es binario y ternario. ^[7] ${\displaystyle U{}_{5}^{2}}$ ${\displaystyle U{}_{5}^{3}}$

Hay siete menores prohibidos para los matroides representables sobre GF(4). ^[8] Son:

• La línea de seis puntos . ${\displaystyle U{}_{6}^{2}}$
• El dual de la línea de seis puntos, seis puntos en posición general en cuatro dimensiones. ${\displaystyle U{}_{6}^{4}}$
• Un matroide autodual de rango tres de seis puntos con una sola línea de tres puntos.
• Matroide no fanoide formado por los siete puntos en los vértices, puntos medios de las aristas y 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 dos líneas de puntos . ^[9] ${\displaystyle n/2}$
• El dual del matroide no-Fano.
• El matroide de ocho puntos de un antiprisma cuadrado .
• El matroide obtenido al relajar el único par de circuitos-hiperplanos disjuntos 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 sentaban juntos en una habitación, todo el día, todos los días, frente a una pizarra. ^[12] Les llevaría años escribir su investigación en su totalidad y publicarla. ^{[13] [14]} Un esquema de la prueba apareció en 2014 en Notices of the American Mathematical Society . ^[15] Solo un artículo de los mismos autores, relacionado con esta conjetura, ha aparecido posteriormente. ^[16]

Véase también

• Conjetura de la base de Rota , una conjetura diferente de Rota sobre álgebra lineal y matroides

Referencias

1. Rota, Gian-Carlo (1971), "Teoría combinatoria, antigua y nueva", Actes du Congrès International des Mathématiciens (Niza, 1970), Tomo 3 , París: Gauthier-Villars, págs. 229-233, MR  0505646.
2. "Resolución de la conjetura de Rota" (PDF) , Avisos de la American Mathematical Society : 736–743, 17 de agosto de 2014
3. Vámos, P. (1978), "El axioma faltante de la teoría matroide se ha perdido para siempre", Journal of the London Mathematical Society , Segunda serie, 18 (3): 403–408, doi :10.1112/jlms/s2-18.3.403, MR  0518224.
4. 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.
5. Tutte, WT (1965), "Conferencias sobre matroides", Revista de investigación de la Oficina Nacional de Normas , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR  0179781Véase en particular la sección 5.3, "Caracterización de matroides binarios", p.17.
6. 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 , MR  0532587Bixby atribuye esta caracterización de los matroides ternarios a Ralph Reid.
7. Seymour, PD (1979), "Representación de matroides sobre GF(3)", Journal of Combinatorial Theory , Serie B, 26 (2): 159–173, doi : 10.1016/0095-8956(79)90055-8 , MR  0532586.
8. Geelen, JF ; Gerards, AMH; Kapoor, A. (2000), "Los menores excluidos para 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 24 de septiembre de 2010.
9. 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.
10. Cita del Premio Fulkerson 2003, consultado el 18 de agosto de 2012.
11. Betten, A.; Kingan, RJ; Kingan, SR (2007), "Una nota sobre los matroides representables por GF(5)" (PDF) , MATCH Communications in Mathematical and in Computer Chemistry , 58 (2): 511–521, MR  2357372.
12. Geelen, Gerards y Whittle anuncian una prueba de la conjetura de Rota Universidad de Waterloo, 28 de agosto de 2013
13. Conjetura de Rota: Investigador resuelve un problema matemático de 40 años PhysOrg, 15 de agosto de 2013.
14. Investigador del CWI demuestra la famosa conjetura de Rota Archivado el 26 de octubre de 2013 en Wayback Machine. CWI, 22 de agosto de 2013.
15. "Resolución de la conjetura de Rota" (PDF) , Avisos de la American Mathematical Society : 736–743, 17 de agosto de 2014
16. Geelen, Jim; Gerards, Bert; Whittle, Geoff (2015), "Las matroides altamente conectadas en clases menores cerradas", Annals of Combinatorics , 19 (1): 107–123, arXiv : 1312.5012 , doi :10.1007/s00026-015-0251-3, MR  3319863