SMF

Exposé Bourbaki 1100 : Les designs existent !

Exposé Bourbaki 1100 : Designs exist !

Gil KALAI
Exposé Bourbaki 1100 : Les designs existent !
  • Consulter un extrait
  • Année : 2016
  • Tome : 380
  • Format : Électronique
  • Langue de l'ouvrage :
    Anglais
  • Class. Math. : Primary: 05B05, 05D40, secondary: 05C70, 51E05, 05B40.
  • Pages : 399-422
  • DOI : 10.24033/ast.994

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.

One of the central and oldest problems in combinatorics is : Can you find a collection $S$ of $q$-subsets from an $n$-element set $X$ so that every $r$-subset of $X$ is included in precisely $t$ sets in the collection ? A collection $S$ of this kind is called a design of parameters $(n,q,r,t)$, a special interest is the case $t=1$, and in this case $S$ is called a Steiner system. It was conjectured that a design of parameters $(n,q,r, t)$ exists for every $q$, $r$ and $t$ if $n$ is sufficiently large and is admissible, namely if some necessary simple divisibility conditions are satisfied. Until recently the known constructions came very far from this. Here is a brief history of the problem : The existence of designs and Steiner systems was asked by Plücker (1835), Kirkman (1846) and Steiner (1853). For $r=2$ which was of special interest, Richard Wilson (1972–1975) proved their existence for large enough admissible values of $n$. Rödl (1985) proved the existence of approximate objects (the property holds for $(1-o(1))$ $r$-subsets of $X$), thus answering a conjecture by Erdös and Hanani. Teirlink (1987) proved their existence for infinitely many values of $n$ when $r$ and $q$ are arbitrary and $t$ is a certain large number depending on $q$ and $r$ but not on $n$. (His construction also does not have repeated blocks.) Keevash (2014) proved the existence of Steiner systems for all but finitely many admissible values of $n$ for every $q$ and $r$. He uses a new method referred to as Randomized Algebraic Constructions. In the lecture I will describe the problem and its history and will try to explain some ingredients in the methods by Wilson, Rödl and Keevash.

Combinatoire, designs de bloc, système de Steiner, la méthode probabiliste, empilement et recouvrement, constructions algébriques aléatoires.
Combinatorics, block designs, Steiner systems, the probabilistic method, packing and covering, randomized algebraic constructions.
Prix
Adhérent 7 €
Non-Adhérent 10 €
Quantité
- +