Timothy Gowers (Cambridge et FSMP) - Mardi 15 mai 2018 (14h30, amphi Hennequin)
Nouvelles bornes pour la fonction d’Erdös et Rogers
Soient s, t deux entiers tels que s < t. Si G est un graphe d’ordre n, et si G ne contient aucune clique d’ordre t, quelle est la taille, au minimum, du plus grand sous-graphe induit qui ne contient aucune clique d’ordre s ? Ceci est une question qui a été posée en 1962 par Erdös et Rogers. En général, le problème reste ouvert. Je présenterai une construction, obtenue récemment avec Oliver Janzer, qui fournit des nouvelles bornes supérieures dans plusieurs cas.
(Lire la suite...)