Seminario de Grafos “Una introducción al método de “Rödl Nibble”
Abstract: Un sistema de Steiner (n,k,t) (o t-design) es un hipergrafo k-uniforme en n vértices tal que todo subconjunto de t vértices está en una única arista. En 1847, Thomas Kirkman demostró que existen para k=3, t = 2, pero su existencia general fue un problema abierto por 167 años,
hasta Peter Keevash (2014).
En 1963, Erdős y Hanani conjeturaron que uno puede acercarse arbitrariamente a un sistema de Steiner en sentido asintótico exigiendo solo que cada t-subconjunto esté en al menos una arista (un cubrimiento).
En 1985 Vojtěch Rödl demostró la conjetura con un argumento probabilista sorprendentemente flexible: armar el cubrimiento de a “pequeños bocados”, eligiendo en cada paso un puñado de aristas al azar, de modo que lo que queda sigue siendo casi-regular y se puede volver a “morder”; iterando hasta que el residuo se vuelve despreciable.
El método pasó a llamarse Rödl Nibble y hoy es una herramienta importante en combinatoria probabilista: se ha usado para matchings casi-perfectos, índice cromático de hipergrafos y como ingrediente en la demostración general de la existencia de sistemas de Steiner.
Revisaremos el método a través de la formulación general de Pippenger y Spencer (1989) y deduciremos el teorema de Rödl como corolario.
Speaker: Raúl Astete (U.Chile)