|
MULTIYEAR PROGRAM
RESEARCH SCHOOL ECOLE DE RECHERCHE ALEA Days |
 |
 |
 |
|
Scientific Committee
Comité scientifique Mireille Bousquet-Mélou (CNRS – Université de Bordeaux) |
Organizing Committee
Comité d’organisation Louigi Addario-Berry (McGill University) contact: alea2020@cmap.polytechnique.fr |
|
The annual meeting Aléa is dedicated to the study of random discrete structures arising in various scientific domains, mainly in theoretical computer science, combinatorics and probability theory, but also in statistical physics, bioinformatics or in other branches of mathematics.
These structures are, for example, trees, words, permutations, lattice walks, more geometrical objects like planar maps, or other objects related to discrete dynamics like cellular automata. Aims and methods are diverse, ranging from enumeration, asymptotic properties and analytic combinatorics, probability, random generation… The Aléa meeting is closely related to the community of the Working Group Aléa of the “Groupement de recherche CNRS” gdr-im, which was created in the 90’s under the impulse of Philippe Flajolet to promote interactions between combinatorics and probability around the analysis of algorithms. In the last ten years it has been the birth place to many fruitful interdisciplinary collaborations (e.g. on planar maps, walks in quarter plane, algebraic urns…) and it has grown into one of the most active interface between computer scientists and mathematicians in France. The program of the conference aims both at broadening the common knowledge of the participants via mini-courses and invited long talks, and at reflecting the variety and dynamism of the community via short talks that are selected through an open call. |
Les journées Aléa sont consacrées à l’étude de l’aléa discret, i.e. l’étude des structures aléatoires discrètes telles qu’elles apparaissent dans diverses disciplines, principalement l’informatique théorique, la combinatoire et la théorie des probabilités, mais aussi la physique statistique, la bio-informatique ou d’autres branches des mathématiques.
Les objets d’études sont par exemple les arbres, les mots, les permutations, les chemins, ou des objets plus géométriques comme les cartes, ou encore liés à une dynamique discrète comme les automates cellulaires. Les objectifs et les méthodes utilisées sont divers : l’énumération, les propriétés asymptotiques et la combinatoire analytique, les propriétés probabilistes, la génération aléatoire… Les journées Aléa sont étroitement liées à la communauté du groupe de travail Aléa du gdr-im, créé à l’initiative de Philippe Flajolet vers la fin des années 90 pour favoriser les interactions entre combinatoristes et probabilistes autour de l’analyse d’algorithmes. Au cours de ces dix dernières années, elles ont été le creuset de nombreuses et fécondes collaborations interdisciplinaires (e.g. autour des cartes planaires, des marches dans le quart-de plan, des urnes algébriques…) et elles sont devenues lieu d’expression de l’une des interfaces math/info les plus actives en France. Le programme répond au double objectif d’assurer une forme de formation continue de la communauté au travers de cours invités et d’exposés longs, et de refléter sa diversité et son dynamisme au travers d’exposés courts sélectionnés via appel à propositions. |
L’un des nombreux problèmes posés par S. Ulam concerne l’asymptotique du cardinal maximal d’une sous-suite croissante d’une permutation aléatoire uniforme de [1,n]. Ce problème est résolu, du moins au premier ordre, en 1979, indépendamment par Logan et Shepp à l’Ouest et par Kerov et Vershik à l’Est, dans leur étude de la forme limite des tableaux de Young sous la mesure de Plancherel. Il en ressort que la plus longue sous-suite croissante est de cardinal équivalent à 2√n. Des fluctuations en n^{1/6} autour de ce résultat, faisant intervenir la loi de Tracy-Widom, ont été montrées en 1999 par Baik, Deift et Johansson, dans un travail faisant date.
Auparavant, en 1972, à l’occasion du sixième Symposium de Probabilités et Statistiques à Berkeley, Hammersley, dans un exposé sur une liste de sujets qui lui paraissent porteur, propose une approche probabiliste pour attaquer ce problème, mettant en jeu un processus de Poisson homogène sur un carré (qui engendre la permutation uniforme). Cependant, Hammersley ne mène pas à bout cette approche dans son texte. C’est Cator et Groeneboom, en 2007, qui arrivent à l’exploiter pour retrouver l’asymptotique en 2√n. Nous présenterons cette approche dans un contexte un peu simplifié, qui permet de bien en appréhender le principe.
Nous verrons ensuite comment cette même méthode permet de résoudre au premier ordre le problème de percolation de dernier passage appelé « Corner Growth Model » et résolu par H. Rost en 1981 par la théorie des systèmes de particules.
Nous verrons dans la séance d’exercices comment des variantes de ces cas peuvent être traités par cette même méthode.
Le cours ne demande pas de prérequis de probabilités très sophistiqués.
Reconfigurer une solution d’un problème donné, c’est lui appliquer des opérations élémentaires successives sans quitter l’espace des solutions. Un tel besoin apparaît naturellement dans des situations dynamiques où une solution donnée est déjà en place et doit être modifiée, sans qu’une rupture de service puisse être envisagée. C’est également un outil utile pour l’énumération ou le sampling uniforme de solutions. Plusieurs grandes questions sont étudiées : quelles opérations élémentaires garantissent que toute autre solution peut être ainsi atteinte ? À opérations fixées, quelle est la complexité de décider si une autre solution donnée peut être atteinte ? Que dire du nombre d’opérations nécessaires pour cela ?
Dans cet exposé, nous discuterons de divers résultats positifs et négatifs dans le cas particulier de la coloration de graphes.
to be announced
 |
 |
 |
  |
 |
 |