English >

SMS 2012 - Survol

Date butoir pour soumettre une demande d'aide financière: 1er mars 2012

Le hasard n'a pas de place dans les méthodologies bien planifiées – il faut mettre un point sur chaque i et une barre sur chaque t. Mais dans la combinatoire, du moins, rien n'est plus loin de la vérité. Les méthodes probabilistes ont joué un rôle toujours croissant dans la résolution des problèmes combinatoires durant le développement de ce domaine. En un sens cela n'est pas étonnant, car le dénombrement est critique pour la combinatoire, et la probabilité discrète consiste simplement en le dénombrement. Mais la vraie explication de l'importance des arguments probabilistes dans ce domaine, et du type d'arguments employés, se trouve ailleurs.

Une des pierres angulaires de l'approche probabiliste à la résolution de ces problèmes combinatoires est le principe directeur suivant : il est possible d'obtenir des informations sur la structure globale à travers l'analyse locale; ce principe est un des thèmes unificateurs de l'école d'été. Peut-être l'exemple récent le plus connu d'une application de ce principe est la preuve récente par Green et Tao qu'il existe des progressions arithmétiques arbitrairement longues dans les nombres premiers. La preuve s'appuie sur le fait qu'interdire une structure, à savoir une progression arithmétique de longueur k, dans un ensemble d'entiers, nous permet de déduire des propriétés « pseudo-aléatoires » globales de l'ensemble des premiers. Un outil clé dans ce procédé est le (ou une variante du) Lemme de régularité de Szemerédi, qui a été généralisé indépendamment aux hypergraphes par Gowers et Rödl. Ces résultats ont aussi des applications importantes en théorie des graphes et des hypergraphes, et plusieurs des intervenants sont experts dans ce domaine.

Un autre résultat fondamental pour le « local-global » est le Lemme Local de Lovàsz (LLL). Ceci est une version de la méthode probabiliste par laquelle il peut être démontré qu'une propriété globale désirée (disons, d'un graphe aléatoire) s'applique en montrant que dans des voisinages locaux, l'apparition d'obstructions à la propriété est assez improbable. Grace à une découverte récente, il existe maintenant un algorithme aléatoire efficace pour trouver la structure dont le LLL garantit l'existence, essentiellement partout où s'applique le lemme.

Une troisième instance de ce paradigme est la théorie des marches aléatoires et le mélange rapide des chaînes aléatoires. Ici, en faisant et en contrôlant des choix locaux aléatoires, on peut démontrer qu'on peut effectuer l'échantillonnage d'un(e distribution de probabilité sur) un espace énorme. A ses fondements, cette technique repose sur la connection proche entre le temps de mélange de chaînes de Markov réversibles (marches aléatoires sur des graphes) et la conductance de telles chaînes. Plusieurs de nos intervenants présenteront des recherches de pointe qui utilisent ou développent cette perspective.

Dans les deux semaines précédant SMS 2012, la deuxième Ecole d'été en théorie des graphes (SSGT) commencera. La première moitié de la deuxième SSGT consistera en deux mini-cours de dix conférences de 90 minutes données chaque jour de semaine pendant cette période. Bruce Reed donnera une séquence de dix conférences sur la coloration des graphes et la méthode probabiliste, et notamment sur l'utilisation du lemme local pour prouver des résultats asymptotiquement optimaux pour les graphes. Louigi Addario-Berry donnera une séquence de dix conférences sur l'utilisation du temps de mélange, de rencontre, et de recouvrement des chaînes de Markov, et sur les marches aléatoires sur les graphes aléatoires. Ces deux semaines fourniront une introduction à certains des outils et des techniques probabilistes utilisés dans les recherches qui seront présentées au SMS. Pour plus de détails, consulter le site web de la SSGT 2012.