Exposé Bourbaki 1100 : Les designs existent !
Exposé Bourbaki 1100 : Designs exist !
Anglais
Un problème ancien et central de combinatoire est le suivant : Existe-t-il une famille $S$ de parties à $q$ éléments d'un ensemble $X$ à $q$ éléments tel que toute partie de cardinal $r$ de $X$ soit contenue dans exactement $t$ membres de la famille $S$ ? Une telle famille $S$ est appelée design de paramètres $(n,q,r,t)$ ; dans le cas particulièrement intéressent où $t=1$, on parle de système de Steiner. Il était conjecturé que pour tout $(q,r,t)$, il existe un design de paramètres $(n,q,r,t)$ si $n$ est assez grand et si certaines conditions nécessaires de divisibilité sont satisfaites. Voici une brève histoire de cette question. L'existence des designs et des systèmes de Steiner a été soulevée par Plücker (1835), Kirkman (1846) et Steiner (1853). Lorsque $r = 2$, Richard Wilson (1972–1975) a prouvé leur existence pour toute valeur admissible assez grande de $n$. Rödl (1985) a établi l'existence d'objets approchés, résolvant ainsi une conjecture de Erdös et Hanani. Teirlink (1987) démontra leur existence pour une infinité de valeurs de $n$, les entiers $r$ et $q$ étant arbiraires et $t$ assez grand (sa construction n'a pas de répétitions de blocs). Keevash (2014) démontra l'existence de systèmes de Steiner pour presque toute valeur admissible assez grande de $n$. Il utilise une nouvelle méthode de construction algébrique aléatoire. Dans l'exposé, je décrirai le problème et son histoire, et j'expliquerai certains ingrédients des méthodes mises en œuvre par Wilson, Rödl et Keevash.