¿Cuáles son los avances más significativos en matemática combinatoria hasta ahora?

La clasificación de grupos simples finitos probablemente podría considerarse como un avance combinatorio, aunque eso sería un poco exagerado. Al menos, la mayoría de los grupos esporádicos aparecieron como grupos automorfistas de estructuras combinatorias.

He escuchado de matemáticos importantes que los siguientes resultados fueron algunos de los mayores avances en combinatoria: el teorema de Robertson-Seymour, el teorema de Szemerédi.

Pero el campo de la combinatoria es demasiado amplio para poder dar una respuesta satisfactoria a esta pregunta. Cada avance importante en la teoría de la codificación, la teoría del diseño, la teoría de grafos, la teoría matroide, la geometría finita, la combinatoria poliédrica, etc. podría considerarse un avance en la matemática combinatoria. Aún así, estos son algunos de mis avances combinatorios favoritos *:

  • Este breve artículo de RC Bose que inició el uso del álgebra lineal en combinatoria: una nota sobre la desigualdad de Fisher para diseños de bloques incompletos equilibrados. Consulte la publicación de mi blog para obtener detalles y referencias adicionales: los orígenes del método de álgebra lineal en combinatoria.
  • El artículo de Segre sobre óvalos en planos de proyecto finitos es uno de los resultados más significativos en geometría finita y es uno de los primeros de su tipo: óvalos en un plano proyectivo finito. Consulte también su charla ICM sobre el tema: Sobre las geometrías de Galois.
  • Estos dos documentos de Erdös (no el primero de su tipo) dieron lugar a métodos probabilísticos en combinatoria: teoría de grafos y probabilidad I, II. El papel de Alfréd Rényi no debe pasarse por alto. Vea esto: modelo Erdős – Rényi.
  • El teorema de Szemerédi de Endre Szemerédi de 1975, que también introdujo el lema de regularidad de Szemerédi.
  • Este artículo de 1976 de Peter Cameron et al. estableció un vínculo interesante y útil entre áreas aparentemente disjuntas: gráficos lineales, sistemas de raíces y geometría elíptica, que luego desempeñaron un papel importante en la teoría de gráficos espectrales: gráficos con menos valor propio −2; una encuesta histórica y desarrollos recientes en gráficos excepcionales máximos
  • Uno de los primeros usos de los métodos topológicos en combinatoria por László Lovász, para probar la conjetura de Kneser, abrió una rama completamente nueva de las matemáticas. También es ahora uno de sus trabajos más citados: la conjetura, el número cromático y la homotopía de Kneser. Para más detalles, vea esto y esto.
  • Otro gran avance de Lovász fue su trabajo en la capacidad de Shannon de un gráfico.
  • La construcción de Ramanujan Graphs por Lubotzky, Philips y Sarnak.
  • Los contraejemplos de la conjetura de Borsuk encontrados por Jeff Kahn y Gil Kalai en 1993 fueron un gran avance. En 2013, Andriy V. Bondarenko demostró, usando el gráfico muy regular relacionado con el grupo simple finito [matemática] G_2 (4) [/ matemática], que esta conjetura es falsa para todas las dimensiones mayores o iguales a 65. Vea esta publicación de blog : ¡La conjetura de Borsuk es falsa para dimensiones superiores a 65!
  • La prueba del teorema del gráfico perfecto fuerte de Maria Chudnovsky, Neil Robertson, Paul Seymour y Robin Thomas. El documento original está disponible aquí, El teorema del gráfico perfecto fuerte.
  • La solución de la versión de campo finito de la conjetura de Kakeya por Dvir es un avance muy reciente. Vea esta publicación de blog de Terence Tao: la prueba de Dvir de la conjetura de Kakeya de campo finito, y este documento de encuesta sobre Métodos polinómicos en combinatoria.
  • Un contraejemplo a la Conjetura de Hirsch encontrada por Francisco Santos en 2010 es un gran avance en la combinatoria poliédrica, ya que resolvió uno de los problemas abiertos más antiguos en la programación lineal.
  • La prueba de la conjetura de MDS sobre campos primos por Simeon Ball, que generaliza el resultado clásico de Segre: en conjuntos de vectores de un espacio vectorial finito en el que cada subconjunto de tamaño base es una base.
  • La solución asintóticamente apretada al problema de distancias distintas de Erd en el avión por Guth y Katz. Aquí hay una bonita exposición de Terence Tao: El enlace de Guth-Katz.
  • Solución a una conjetura centenaria sobre la existencia de diseños de Peter Keevash. (bajo revisión)
  • Entrelazando familias I: gráficos bipartitos de Ramanujan de todos los grados por Adam Marcus, Daniel A. Spielman y Nikhil Srivastava.

* Seguiré actualizando esta lista a medida que aprenda más.

Finalmente, aquí hay una colección de artículos de matemáticos importantes que discuten algunos de los grandes avances en combinatoria:

  • Matemática discreta: métodos y desafíos por Noga Alon
  • Combinatoria entrando al tercer milenio por Peter Cameron

Esto está un poco lejos para mí, pero el trabajo de Timothy Gowers aplicando la combinatoria a la teoría espacial de Banach debería calificar.

Además, estaba leyendo esta mañana que la conjetura topológica de Tverberg, descrita como “un santo grial de la combinatoria topológica”, ha sido refutada:

La conjetura dice que cualquier mapa continuo de un símplex de dimensión [math] (r − 1) (d + 1) [/ math] a [math] \ mathbb {R} ^ d [/ math] mapea puntos desde r caras disjuntas del simplex al mismo punto en
[matemáticas] \ mathbb {R} ^ d [/ matemáticas]. En ciertos casos, se ha demostrado que la conjetura es cierta, pero se han encontrado contraejemplos en el caso de que [math] r [/ math] no sea una potencia principal, para valores suficientemente grandes de [math] d [/ math]: el más pequeño El contraejemplo encontrado es para un mapa del simplex 100 dimensional a [math] \ mathbb {R} ^ {19} [/ math], con [math] r = 6 [/ math].

El resultado fue presentado recientemente en el Oberwolfach Maths Research Institute, que está situado en la Selva Negra en Alemania y regularmente alberga bandas de matemáticos ferozmente inteligentes. La refutación, de Florian Frick, se encuentra en el artículo Contraejemplos a la Conjetura topológica de Tverberg.

La conjetura topológica de Tverberg es falsa