La conjetura de Rota.

Conjetura sobre menores prohibidos de matroides

La conjetura de los menores excluidos de Rota es una de varias conjeturas realizadas 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, para cada campo finito , la familia de matroides que puede representarse en ese campo tiene sólo un número finito de menores excluidos . ^[1] Geelen, Gerards y Whittle anunciaron una prueba de la conjetura, pero no la publicaron, en 2014. ^[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 una matroide ; Se dice que es una representación de cualquier matroide isomorfa . No todas las matroides tienen una representación sobre cada campo; por ejemplo, el plano de Fano es representable sólo sobre campos de característica dos. Otras matroides no se pueden representar en ningún campo. Las matroides que son representables en un campo particular forman una subclase adecuada de todas las matroides. ${\displaystyle S}$ ${\displaystyle F}$ ${\displaystyle S}$ ${\displaystyle M}$ ${\displaystyle S}$ ${\displaystyle M}$

Una menor de una matroide es otra matroide formada 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 una 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 si y sólo si no contiene uno de los menores prohibidos. ${\displaystyle S}$ ${\displaystyle F}$ ${\displaystyle M}$ ${\displaystyle F}$

Para la representabilidad de los números reales , existen infinitos menores prohibidos. ^[3] La conjetura de Rota es que, por cada campo finito , sólo existe 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, la matroide uniforme (geométricamente, una línea con cuatro puntos). ^{[4] [5]} ${\displaystyle U{}_{4}^{2}}$

Una matroide es representable sobre el campo ternario GF(3) si y sólo si no tiene una o más de las siguientes cuatro matroides 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 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 pueden representarse en todos los campos), se deduce que una matroide es regular si y sólo si es tanto binario como ternario. ^[7] ${\displaystyle U{}_{5}^{2}}$ ${\displaystyle U{}_{5}^{3}}$

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

• La línea de seis puntos . ${\displaystyle U{}_{6}^{2}}$
• El dual a la línea de seis puntos, seis puntos en posición general en cuatro dimensiones. ${\displaystyle U{}_{6}^{4}}$
• Una matroide autodual de rango tres de seis puntos 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 las aristas 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 líneas de menos de dos puntos . ^[9] ${\displaystyle n/2}$
• El dual de la matroide que no es Fano.
• La matroide de ocho puntas de un antiprisma cuadrado .
• La matroide se obtiene relajando el par único de hiperplanos-circuitos 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ó visitas intensas 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 redactar su investigación en su totalidad y publicarla. ^{[13] [14]} Un resumen de la prueba apareció en 2014 en los Avisos de la Sociedad Matemática Estadounidense . ^[15] Posteriormente sólo ha aparecido un artículo de los mismos autores, relacionado con esta conjetura. ^[dieciséis]

Ver también

• Conjetura básica 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. "Resolver 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 pierde para siempre", Revista de la Sociedad Matemática de Londres , Segunda Serie, 18 (3): 403–408, doi :10.1112/jlms/s2-18.3. 403, señor  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 Estándares , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR  0179781. Consulte en particular la sección 5.3, "Caracterización de matroides binarias", 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 , SEÑOR  0532587. Bixby atribuye esta caracterización de matroides ternarias a Ralph Reid.
7. 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 , Señor  0532586.
8. 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 24 de septiembre de 2010.
9. Kelly, LM ; Moser, WOJ (1958), "Sobre el número de líneas ordinarias determinado por n puntos", Can. J. Matemáticas. , 10 : 210–219, doi : 10.4153/CJM-1958-024-6.
10. Mención del Premio Fulkerson 2003, consultado el 18 de agosto de 2012.
11. Betten, A.; Kingan, RJ; Kingan, SR (2007), "Una nota sobre matroides representables 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 hace 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. "Resolver 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