¿Cuáles son algunos avances recientes en la teoría de grafos? Tomé un curso de posgrado en teoría de grafos, pero los resultados que uso de la teoría de grafos (espectrales y aleatorios) tienen más de 50 años. ¿Qué hay de nuevo y cuáles son los grandes avances recientes?

Luca Trevisan ha estado haciendo un gran trabajo de investigación sobre la teoría y los expansores de gráficos espectrales. Echa un vistazo a su artículo Max Cut y el valor propio más pequeño ([0806.1978] Max Cut y el valor propio más pequeño) donde propone un algoritmo de aproximación 0.531 para MAX-CUT, que es el primer algoritmo de aproximación que no utiliza programación semi-definida. La mejor aproximación posible para ese problema es la aproximación de 0.878 dada por Goemans y Williamson, basada en SDP (que es la mejor aproximación posible suponiendo la Conjetura de los juegos únicos).

Consulte también el blog de Luca Trevisan, que tiene una gran cantidad de recursos sobre algoritmos de gráficos espectrales y las desigualdades de Cheeger.

Luca ha estado ofreciendo cursos sobre teoría de grafos espectrales. Echa un vistazo a Particionamiento gráfico, expansores y métodos espectrales.

Un avance extremadamente importante se produjo en ~ 2002 por cortesía del legendario trabajo de Maria Chudnovsky y Paul Seymour (¡en un enorme documento de 150 páginas!).

• Esencialmente, se les ocurrió el Teorema del Gráfico Fuerte Perfecto
  Lo hicieron demostrando dos conjeturas (ver Reclamaciones ):
  i) Definiciones :

• Una gráfica [matemática] G [/ matemática] es perfecta, iff , [matemática] \ forall [/ matemática] induce sub-gráficas [matemática] H \ subconjunto_ {s} G [/ matemática], [matemática] \ chi (H ) [/ matemática] [matemática] = [/ matemática] [matemática] \ chi [/ matemática] [matemática] ([/ matemática] Max Induced Subgraph [matemática] H) [/ matemática].
• A Graph [math] G [/ math] es Berge, iff , [math] \ forall [/ math] induce Sub-Graphs [math] H \ subset_ {s} G [/ math], ([math] H \ neq C_ {5} [/ matemática]) [matemática] \ wedge [/ matemática] ([matemática] H \ neq \ overline {C_ {5}} [/ matemática])

• i) Perfect(G) [matemáticas] \ leftrightarrow [/ matemáticas] Berge(G)
• ii) Conforti, Cornuejols and Vuskovic Conjecture
  Pruebas : el documento prueba ambas afirmaciones.

  Documento: [matemáticas / 0212070] El teorema del gráfico perfecto fuerte

Aquí hay algunas cosas buenas de Spielman y Teng.

Esencialmente, ¡resolver para x en un sistema lineal de ecuaciones Lx = b donde L es un laplaciano de un gráfico puede aproximarse en un tiempo lineal al número de bordes del gráfico!

Hay un montón de maquinaria matemática necesaria para que esto suceda, y en la última década Spielman y Teng (y muchos otros) lo han desarrollado ampliamente.

http://www.cs.yale.edu/homes/spielman/Research/topicList.html