00:00:00 / 00:00:00

The existence of designs, after Peter Keevash

De Gil Kalai

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.

Informations sur la vidéo

  • Date de captation 27/06/2015
  • Date de publication 27/06/2015
  • Institut IHP
  • Licence CC BY-NC-ND
  • Format MP4

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow




Inscrivez-vous

  • Mettez des vidéos en favori
  • Ajoutez des vidéos à regarder plus tard &
    conservez votre historique de consultation
  • Commentez avec la communauté
    scientifique
  • Recevez des notifications de mise à jour
    de vos sujets favoris
Donner son avis