MULTIYEAR PROGRAM
RESEARCH SCHOOL
ÉCOLE DE RECHERCHE

ALEA Days
Journées ALEA

13 – 17  March, 2023

Groupe de travail du GDR-IM

INTRANET FOR ORGANIZERS

Scientific Committee 
Comité scientifique

Christina Goldschmidt (University of Oxford)
Irène Marcovici (IECN – Université de Lorraine)
Marc Noy (Universitat Politècnica de Catalunya)
Gilles Schaeffer (CNRS, École Polytechnique)

 

Organizing Committee
Comité d’organisation

Andrew Elvey Price (CNRS, IDP – Université de Tours)
Cédric Lecouvey (IDP – Université de Tours)
Cécile Mailler (University of Bath)
Kilian Raschel (CNRS, LAREMA – Université d’Angers)

contact: alea2023@idpoisson.fr

IMPORTANT WARNING:  Scam / Phishing / SMiShing ! Note that ill-intentioned people may be trying to contact some of participants by email or phone to get money and personal details, by pretending to be part of the staff of our conference center (CIRM).  CIRM and the organizers will NEVER contact you by phone on this issue and will NEVER ask you to pay for accommodation/ board / possible registration fee in advance. Any due payment will be taken onsite at CIRM during your stay.

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.

MINI-COURSES

Durée: 2x1h15 + 1h d’exercices

Je commencerai par présenter des décompositions arborescentes pour les graphes et les permutations : arbre de décomposition modulaire, arbre de décomposition par coupe et arbre de substitution pour les permutations. Je parlerai ensuite d’objets limites et de notions de convergence : graphon, permuton et convergence de Gromov-Prohorov. Le but est ensuite de faire le lien entre ces deux parties via la combinatoire analytique, en utilisant les décompositions arborescentes pour établir des résultats de convergence. Travaux en commun avec F. Bassino, M. Bouvel, L. Gerin, M. Maazoun et A. Pierrot.

La génération aléatoire est un outil de choix pour étudier les structures combinatoires et notamment leurs propriétés asymptotiques. Bien qu’il soit parfois possible de concevoir des générateurs ad hoc efficaces pour certaines classes d’objets combinatoires, nous nous intéresserons plutôt aux méthodes de générations dites « automatiques » : la méthode récursive et la méthode de Boltzmann en particulier. Dans les deux cas, il est possible de traduire directement les spécifications combinatoires issues de la méthode symbolique de Flajolet et Sedgewick en algorithmes de génération aléatoire uniforme (tous les objets de même taille ont la même probabilité d’être tirés). Ces deux techniques s’appuient fortement sur l’utilisation des séries génératrices afin de garantir l’uniformité des tirages. Dans le cas de la méthode récursive, on exploitera les coefficients des séries formelles alors que la méthode de Boltzmann s’appuie sur l’évaluation numérique de ces mêmes séries. Durant la séance d’exercices vous pourrez programmer vos propres générateurs suivant l’une ou l’autre de ces méthodes.

The subject of these lectures is the discrete Schwarzian Kadomtsev-Petviashvili (dSKP) recurrence. We will first explain the dSKP equation and its occurrences and then turn to the recurrence. We will prove an explicit expression for the solution as a function of the initial data; more precisely we will show that the solution is the ratio of two partition functions of an associated oriented dimer model. There are some cancellations in each partition function, and we will show an alternative, cancellation free expression involving complementary trees and forests. Apart from its combinatorial interest, this second expression is used to prove singularity results. Next, we will show how this equation appears in different geometric systems as for example: discrete holomorphic functions, polygon recutting or the pentagram map. Using our previous results, we prove explicit expressions for their solution, and handle the reoccurrence of singularities, also known as the Devron property. This is based on joint works with Niklas Affolter and Paul Melotti.

EXPOSÉS TUTORIELS

Durée: 1h 

Pendant cet exposé je donnerai un aperçu des méthodes galoisiennes appliquées aux équations fonctionnelles, afin de présenter des résultats sur la nature de certaines séries génératrices issues de la combinatoire, et en particulier de la combinatoire énumérative, récemment obtenus par plusieurs auteurs. L’objectif est de donner l’intuition du principe commun de ces preuves.

  • Si l’hypothèse P\neq NP a pour conséquence que les problèmes NP-difficiles ne sont pas résolubles en temps polynomial, l’obtention de résultats négatifs plus précis nécessite le recours à des hypothèses plus fortes. Dans cet exposé, nous présenterons certains résultats négatifs (bornes inférieures de complexité) obtenus à partir des hypothèses ETH (exponential time hypothesis) et SETH (strong exponential time hypothesis). Il y sera question de SAT, de graphes, de complexité (classique et parfois paramétrée), de problèmes difficiles mais aussi de problèmes polynomiaux.

A travers des exemples applicatifs, j’expliquerai comment l’approche champ moyen permet d’analyser les grands réseaux stochastiques. Si le fait que les états d’un nombre fini de noeuds du réseau deviennent indépendants à la limite est connu, je montrerai comment certaines interactions disparaissent aussi à la limite. Je parlerai sur des exemples du problème d’unicité du point d’équilibre de la limite champ moyen, et d’autres avancées récentes.

Les mélanges de cartes ont été étudiés en détail aussi bien du point de vue pratique que mathématique. Un résultat célèbre de Diaconis et Bayer dit essentiellement que 7 mélanges suffisent pour qu’un jeu de 52 cartes soit bien mélangé (c’est-à-dire, la mesure de probabilité sur les différentes permutations est presque la mesure uniforme). Du point de vue algébrique, ceci est relié à l’existence d’une sous-algèbre de l’algèbre du groupe symétrique, appelée algèbre des descentes. De nombreuses notions différentes de mélanges peuvent être traitées via une construction géométrique de Bidigare, Hanlon et Rockmore. Je ferai un survol de cette approche ainsi que de quelques résultats plus récents.

We introduce a family of geometrical lattice models generalising the well-known loop model on the hexagonal lattice. These models have a $U_q(sl_n)$ quantum group symmetry, the loop model being the $n=2$ case. The general models give rise to branching webs and describe, at a special point, the interfaces in $Z_n$ symmetric spin models. We mainly discuss the $n=3$ case of bipartite cubic webs, which is based on the Kuperberg $A_2$ spider. We exhibit a local vertex-model reformulation, analogous to the well-known correspondence between the loop model and the nineteen-vertex model. The local formulation allows us in particular to study the model by means of transfer matrices and conformal field theory. We find that it has a rich phase diagram, including a dense and a dilute phase that generalise those known for the loop model. Based on joint work with Augustin Lafay and Azat Gainutdinov (arXiv:2101.00282 and 2107.10106).

SHORT TALKS

to be announced

SPONSORS