ABC

A

• Boris Adamczewski (Institut de Mathématiques de Marseille, CNRS),
  Congruences « à la Lucas » et indépendance algébrique de G-fonctions.
  2/04/2015.

Les diagonales de fractions rationnelles forment une classe de fonctions analytiques se situant au confluent de plusieurs grands thèmes : la combinatoire énumérative, la théorie des équations différentielles, l'arithmétique, la géométrie algébrique et l'informatique théorique. Lorsque leurs coefficients sont des nombres rationnels, ces séries ont la propriété remarquable d'être algébriques modulo presque tout nombre premier p. Cette propriété implique l'existence de congruences générales satisfaites par leurs coefficients. Dans de nombreux cas, on obtient en fait des congruences bien plus spécifiques et bien connues des combinatoristes, du type de celles introduites par Lucas. J'expliquerai comment en déduire des résultats d'indépendance algébrique pour certaines familles de G-fonctions sans avoir recours à la théorie de Galois différentielle.

Il s'agit de travaux communs avec J. Bell et E. Delaygue.

• Marie Albenque (Laboratoire d’Informatique de l’École Polytechnique),
  Bijections entre cartes planaires et arbres bourgeonnants.
  6/02/2014.
  Transparents.

Les arbres bourgeonnants sont des arbres portant des décorations qui permettent de leur associer une carte planaire. Trouver des bijections entre des familles de cartes et d'arbres bourgeonnants fournit un outil précieux dans l'étude des cartes planaires; cela permet en effet de ramener l'étude de la carte à celle de l'arbre associé, souvent plus simple.

De nombreuses bijections ont été obtenues ces 15 dernières années et dans cet exposé je présenterai un schéma général qui, en se spécialisant, permet d'obtenir beaucoup de ces constructions comme des cas particuliers ainsi que de nouvelles constructions. Ce résultat s'inscrit dans la lignée de travaux par Bernardi et Fusy et qui visent à unifier les bijections existantes entre cartes et arbres.

Une question fondamentale, encore largement ouverte, est maintenant de comprendre comment les distances entre deux sommets de la carte peuvent être retrouvées à partir de l'arbre bourgeonnant. J'expliquerai comment cette question peut être résolue dans le cas des triangulations simples.
Cet exposé repose sur des travaux avec Louigi Addario-Berry et Dominique Poulalhon

• Marie Albenque (LIX, École Polytechnique),
  Géométrie des clusters de spins dans les triangulations munies d’un modèle d’Ising.
  3/02/2022.

Dans cet exposé, je présenterai des résultats, obtenus en collaboration avec Laurent Ménard, sur la géométrie des clusters de spins dans des triangulations munies d’un modèle d’Ising, et qui s’appuie sur des travaux obtenus précédemment en collaboration avec Laurent Ménard et Gilles Schaeffer. 

Dans ce modèle, on considère des triangulations dont les sommets sont décorés par des spins + ou -. Cela nous permet de définir une loi de probabilités qui consiste à échantillonner une triangulation décorée avec une probabilité qui dépend de son nombre d’arêtes monochromatiques, via un paramètre nu. Le fait qu’il existe une valeur critique du paramètre pour ce modèle, a été initialement prouvé dans la littérature physique par Kazakov, et a ensuite été retrouvé par des méthodes combinatoires par Bousquet-Mélou et Schaeffer et par Bouttier, Di Francesco and Guitter. 

Je montrerai comment on peut étudier géométriquement la transition de de phase de ce modèle via l’étude du volume et du périmètre de ses clusters monochromatiques. En particulier,  je montrerai que quand nu est critique ou sous critique, le cluster de la racine est fini presque sûrement et infini avec une probabilité positive quand nu est surcritique.

• Omid Amini (CNRS, École Polytechnique),
  Logarithmic tree factorials.
  4/10/2019.

To any rooted tree we associate a sequence of numbers that we call logarithmic factorials of the tree. This provides a generalization of the work of Manjul Bhargava to a combinatorial setting suitable for the study of questions around generalized factorials.

The aim of the talk will be to present basic aspects of this framework with connections to algebra, number theory, and probability, and to discuss several open questions.

• Federico Ardila (SFSU USA),
  Arithmetic Tutte polynomials of classical Coxeter groups.
  28/03/2013.

Arithmetic Tutte polynomials of classical Coxeter groups The Tutte polynomial is a very important combinatorial invariant of an arrangement of hyperplanes. It encodes a great amount of enumerative, topological, and algebraic information about the arrangement - whether the underlying vector space is real, complex, or finite. The arithmetic Tutte polynomial, introduced by Moci in 2009, plays the analogous role for toric arrangements. We introduce a "finite field method" for computing arithmetic Tutte polynomials, and use it to compute these polynomials for the classical Coxeter groups. The talk will not assume previous knowledge of the subject.

Joint work with Federico Castillo (Los Andes / UC Davis) and Mike Henley (SFSU).

• Nathalie Aubrun (LISN, Saclay),
  Jeux de tuiles robustes et problème du domino.
  

04/04/2024.
Transparents.

L'un des problèmes les plus fondamentaux en théorie du pavage est le problème du domino : étant donné un ensemble de tuiles, peut-on décider s'il existe un moyen de paver le plan? Depuis les années 60 on sait que ce problème est indécidable en général y compris en se restreignant aux tuiles de Wang, qui sont des tuiles carrées unitaires avec des couleurs sur leurs bords et que l'on peut assembler à condition qu'elles partagent la même couleur sur leur bord commun. Dans cet exposé je présenterai une notion de robustesse pour des jeux de tuiles de Wang : plusieurs jeux de tuiles célèbres de la littérature possèdent cette propriété, et satisfont donc un certain invariant de manière prouvable, et le problème du domino devient décidable pour les jeux de tuiles robustes.
Il s’agit d’un travail en collaboration avec Manon Blanc et Olivier Bournez.

• Jean-Christophe Aval (Labri, Bordeaux),
  Fonctions de parking.
  01/06/2017.

Les fonctions de parking sont des objets classiques en combinatoire, énumérative ou algébrique. On peut les définir comme des étiquetages de chemins de Duck, qui sont des chemins avec des pas $(1,0)$ et $(0,1)$, usuellement dessinés dans le carré $n \times n$, et contraints à être au-dessus de la diagonale. Il est bien connu que leur nombre est $(n + 1)^{n-1}$. Le groupe symétrique $S_n$ agit sur les fonctions de parking par permutation des étiquettes. Cette action est élégamment traduite en termes de fonctions symétriques via la caractéristique de Frobenius. Dans cet exposé, nous étudierons certaines généralisations : pour les fonctions de parking incluses dans un rectangle $m\times n$, pour les fonctions de parking de Schroder, analogues du cas précédent pour les chemins de  Schroder, pour lesquels un troisième type de pas $(1,1)$ est permis. Enfin, nous verrons une notion de fonctions de parking {\em entrelacées}, relatives à une action de $S_n \times S_m$. 

C'est un travail en commun avec F. Bergeron (Montréal).

• Arvind Ayyer (Indian Institute of Science, Bangalore)
  Computer algebra for the study of two-dimensional exclusion processes..
  07/12/2023

Transparents.

We define a new disordered asymmetric simple exclusion process (ASEP) with two species of particles, first-class and second-class, on a two-dimensional toroidal lattice. The dynamics is controlled by first-class particles, which only move horizontally, with forward and backward hopping rates $p_i$ and $q_i$ respectively if the particle is on row $i$. The motion of second-class particles depends on the relative position of these with respect to the first-class ones, and can be both horizontal and vertical.

In the first part of my talk, I will illustrate how we used computer algebra software, specifically Mathematica and SageMath, to understand the stationary distribution of this process. We computed the partition function, as well as densities and currents of all particles in the steady state. We observed a novel mechanism we call the Scott Russell phenomenon: the current of second class particles in the vertical direction is the same as that of first-class particles in the horizontal direction. In the second part of my talk, I will show how we simulated the process and realized that the Scott Russell phenomenon also holds out of equilibrium.

This is partly joint work with P. Nadeau (European Journal of Combinatorics, 2022).

B

• Axel Bacher (LIPN, Université Paris Nord),
  Autour des algorithmes de rejet anticipé.
  21/9/2017.
  Transparents.

Les algorithmes de rejet anticipé sont une classe d'algorithmes de génération aléatoire dont les plus célèbres sont les algorithmes dits florentins pour les mots de Motzkin (Barcucci et al., 1992). Je présenterai plusieurs de ces algorithmes et montrerai des résultats permettant de les analyser de manière systématique en loi limite. Je montrerai aussi comment, dans certains cas (mots de Dyck ou arbres binaires, notamment), on peut obtenir des algorithmes plus efficaces en s'affranchissant de tout rejet. Enfin, je détaillerai les propriétés des lois limites de ces algorithmes, dont les densités vérifient une équation différentielle avec retard, ce qui entraîne une structure un peu inhabituelle (par exemple, elles ont une singularité en tous les points entiers).

Travail en commun avec Olivier Bodini, Alice Jacquot et Andrea Sportiello.

• Imre Bárány (Hungarian Academy of Sciences),
  Tensors, colours, octahedra.
  4/06/2015.
• Anne-Laure Basdevant (Université Paris Nanterre),
  Plus longue sous suite croissante avec contraintes.
  7/02/2019.

Étant donné un nuage de points poissonien, Hammersley étudia dans les années 70 le nombre maximal de points du nuage par lequel un chemin croissant peut passer. Ceci permettait alors d'obtenir la longueur asymptotique de la plus longue sous-suite croissante dans une grande permutation aléatoire. Dans cet exposé, nous généraliserons le problème d'Hammersley en rajoutant diverses contraintes sur le chemin et nous exposerons des couplages qui permettent de se ramener au problème originel. 

Travail en collaboration avec Lucas Gerin.

• Frédérique Bassino (LIPN, Paris Nord),
  Enumération asymptotique d’automates finis.
  24/05/2012.
  Transparents.

Cet exposé portera sur l'énumération d'automates finis. Les automates peuvent être vus comme des graphes orientés dont les arêtes sont étiquetées sur un alphabet fini et dont deux sous-ensembles de sommets sont distingués (l'ensemble respectivement des états initiaux et des états terminaux). Nous présenterons les résultats obtenus depuis la fin des années 70 concernant l'énumération des automates détermnistes et accessibles, i.e. dans lesquels tout état peut-être atteint par un chemin partant de l'unique état initial. Nous déterminerons ensuite précisément la proportion asymptotique d'automates minimaux parmi les automates déterministes accessibles et complets. Toutes ces estimations peuvent être obtenue grâce à une interprétation combinatoire des propriétés structurelles des automates et des bijections pour se ramener à l'étude combinatoire de tableaux particuliers.

• Michel Bauer (IPHT CEA/DSM),
  Variables échangeables, martingales et mesures non-destructives en mécanique quantique.
  27/09/2012.
  Transparents.

Plus de 80 ans après la découverte des lois de la mécanique quantique, celles-ci continuent de susciter l'étonnement. La notion de mesure en particulier, reste très mystérieuse. Des expériences récentes très simples et belles, que nous décrirons brièvement, permettent de lever légèrement un coin du voile. Après avoir présenté, pour des non-physiciens, les notions de base de la mécanique quantique, nous montrerons pourquoi l'interprétation de ces expériences est étroitement liée à la théorie des variables échangeables, au théorème de de Finetti et au théorème de convergence des martingales.

• Anna Ben Hamou (LPSM, Sorbonne Université),
  Inférence statistique sur des arbres aléatoires récursifs à communautés.
  1/06/2023.

Dans cet exposé, on introduira un modèle d’arbre aléatoire récursif présentant une structure à deux « communautés », au sens où chaque nouveau noeud s’attache de façon préférentielle à un noeud du même type que lui, cette préférence étant mesurée par un paramètre $q\in [0,1]$. De nombreuses questions d’ordre statistique peuvent être posées sur ce modèle: si l’on observe l’arbre aléatoire obtenu au bout d’un temps donné, en enlevant la donnée des types mais en gardant éventuellement la donnée des temps d’arrivée, peut-on estimer le paramètre $q$? Ou simplement distinguer deux valeurs différentes de ce paramètre? De façon plus ambitieuse, peut-on trouver une partition des noeuds qui soit corrélée de façon significative avec la « vraie » partition? Nous apporterons des débuts de réponses à ces questions, ce qui nous permettra surtout de les reformuler de façon plus précise. Il s’agit d’un travail ehttps://semflajolet.math.cnrs.fr/wp-content/uploads/2023/10/boutillier_2023.pdfhttps://semflajolet.math.cnrs.fr/wp-content/uploads/2023/10/boutillier_2023.pdfn collaboration avec Vasiliki Velona (Université hébraïque de Jerusalem).

• François Bergeron (UQAM Montréal),
  Combinatoire de Catalan et espaces de polynômes harmoniques diagonaux.
  2/12/2011.
  Transparents. Synthèse.

Au cours des vingt dernières années, l'étude des espaces de polynômes harmoniques diagonaux a mené à une étude fine de la combinatoire des fonctions de stationnement (parking functions), et de paramètres sur celles-ci. Nous allons présenter certains de ces développements, avec des extensions qui font intervenir l'ordre de Tamari ainsi que ses extensions aux cas de chemins de Dyck généralisés. Nous conclurons en abordant de nouveaux problèmes combinatoires soulevés par cette étude.

• François Bergeron (UQAM Montréal),
  Autour de la conjecture de Foulkes.
  6/06/2019.

La conjecture de Foulkes, tout comme ses généralisations, se traduit de nombreuses façons selon le domaine considéré. Voilà pourquoi, selon qu’on adopte le point de vue de la combinatoire énumérative, de la théorie de Polya, de la théorie de la représentation, ou des fonctions symétriques, elle fait intervenir des phénomènes combinatoires de toute sorte. Telle qu’énoncée par Foulkes, la conjecture originale remonte au début des années 1950’s. Mais Hadamard en avait déjà formulé une version équivalente, plus géométrique, dès la fin du 19e siècle. Nous allons en présenter les grandes lignes dans un contexte historique, et discuter de quelques implications combinatoires intrigantes. Si le temps le permet, on en présentera 1 $q$-extension.

• Valerie Berthé (LIAFA),
  Dynamique euclidienne : une approche symbolique.
  31/01/2013.
  Transparents.

La transformation de Gauss (qui sous-tend le développement en fraction continue) a été très efficacement étudiée par Baladi-Vallée sous l'angle de l'analyse dynamique d'algorithmes. Le but de cet exposé est de montrer comment revisiter les résultats obtenus dans ce contexte sous l'angle de la dynamique symbolique.

• Valérie Berthé (IRIF)
  Exposants de Lyapunov, produits de matrices et fractions continues.
  2/06/2022.
  Transparents.

Les fractions continues classiques fournissent les meilleures approximations rationnelles de réels. On attend de fractions continues multidimensionnelles qu'elles produisent simultanément des approximations rationnelles avec le même dénominateur pour des d-uplets donnés de nombres réels, et ce d'une manière efficace. Le principal avantage de la plupart des fractions continues unimodulaires classiques est qu'elles peuvent être exprimées comme des systèmes dynamiques dont l'étude ergodique a déjà été bien comprise. Nous discuterons ici de leur principal inconvénient qui réside dans leurs propriétés d'approximation et de convergence en haute dimension. En effet, leur convergence est régie par les exposants de Lyapounov qui décrivent le comportement asymptotique des valeurs singulières de grands produits de matrices aléatoires, sous l'hypothèse ergodique. Nous discuterons ici d'un travail mené en collaboration avec W. Steiner et J. Thuswaldner, où nous avons remarqué expérimentalement que le second exposant de Lyapounov n'est même pas négatif en haute dimension pour les algorithmes les plus classiques tels que les algorithmes de Jacobi-Perron, Brun ou Selmer, ce qui empêche la convergence forte de ces algorithmes.

• Jérémie Bettinelli (CNRS, École Polytechnique),
  Une bijection (améliorée) pour les cartes nonorientables.
  28/11/2019.

Récemment, Chapuy et Dolega ont trouvé une bijection entre les quadrangulations biparties d'une surface nonorientable et les cartes à une face de la même surface, dont les sommets sont étiquetés. Cette bijection généralise la bijection de Chapuy, Marcus et Schaeffer qui se concentrait sur les surfaces orientables et qui généralisait la fameuse bijection de Cori, Vauquelin et Schaeffer entre les quadranguations planes et les arbres bien étiquetés.

Au cours de cet exposé, nous allons un pas plus loin en présentant une bijection entre les cartes générales d'une surface nonorientable donnée et certaines cartes étiquetées à une face de la même surface. Cette bijection généralise à la fois la bijection de Chapuy et Dolega et celle de Bouttier, Di Francesco et Guitter pour les cartes planes générales. La version présentée ici a été améliorée par rapport à une ancienne version que nous avons pu présenter précédemment, au sens notamment où les objets codants sont aujourd'hui plus simples à décrire.

• Riccardo Biagioli (ICJ, Universite Claude Bernard Lyon 1),
  $321$-avoiding affine permutations, heaps, and periodic parallelogram polyominoes.
  7/12/2017.
  Transparents.

Among permutations, those that avoid the pattern $321$ are of great interest in combinatorics and algebra. They are known to be counted by the $n$th Catalan number. From an algebraic point of view, a permutation is $321$-avoiding if, and only if its corresponding element in the Coxeter group of type $A$ is fully commutative. 

In this talk we consider their affine analogues, so $321$-avoiding affine permutations. We show some combinatorial characterizations of them, and we prove a formula for their enumeration with respect to the inversion number. This is done in two different ways, both related to Viennot’s theory of heaps. First, we encode these permutations using certain heaps of monomers and dimers. For the second method, we introduce periodic parallelogram polyominoes, which are new combinatorial objects of independent interest. We enumerate them by extending the approach of Bousquet-Mélou and Viennot used for classical parallelogram polyominoes. We finally establish a connection between these new objects and $321$-avoiding affine permutations. 

This talk is based on a joint work with Frédéric Jouhet and Philippe Nadeau.

• Philippe Biane (IGM,MLV),
  Polynômes orthogonaux et équations de Painlevé discrètes.
  7/10/2011.
  Transparents. Synthèse.

Les polynômes orthogonaux ont de riches propriétés combinatoires. Dans cet exposé je considérerai des polynômes orthogonaux sur le cercle unité, proches de ceux d'Askey-Wilson mais qui ne s'y ramènent pas. Les coefficients de leurs relations de récurrence ne sont pas donnés par une formule explicite mais sont déterminés par une autre relation de récurrence qui est en fait une équation de Painlevé discrète (j'expliquerai dans l'exposé ce que sont les équations de Painlevé). Cette équation de récurrence provient d'une structure géométrique remarquable qui fait intervenir les systèmes de racines affines $D_5$ et $A_3$, plongés de façon orthogonale dans $E_8$.

• Philippe Biane (Institut Gaspard Monge),
  Processus d’exclusion simple quantique, associaèdre et cumulants libres.
  31/03/2022
  Transparents.

Le processus d'exclusion simple quantique est un modèle  de particules fermioniques (particules quantiques satisfaisant le principe d'exclusion) qui se déplacent aléatoirement sur un intervalle. C'est une version quantique du processus d'exclusion simple bien connu et très étudié. D. Bernard et T. Jin ont montré que les fluctuations de la mesure stationnaire de ce processus peuvent être décrites par des polynômes remarquables. Dans cet exposé je présenterai ce modèle et je donnerai une formule combinatoire explicite pour ces polynômes au moyen des arbres de Schröder (ou, de façon équivalente, de l'associaèdre). Je montrerai également que ces polynômes peuvent s'interpréter comme des cumulants libres (ces cumulants viennent de la théorie des probabilités libres, j'expliquerai ce que c'est).

• Marthe Bonamy (CNRS, LaBRI, Univ. Bordeaux),
  Partitioning a graph into isomorphic subgraphs.
  15/2/2018.
  Transparents.

Given a graph G and a subgraph H of G, we can wonder whether G admits a perfect H-packing, i.e. whether we can partition the vertices of G into (induced) copies of H. A classical example of such a question is whether a graph admits a perfect matching. There does not seem to be any good sufficient conditions for G to admit a perfect H-packing. Here, we investigate when a sufficiently high Cartesian power of G admits a perfect H-packing. We generalize a theorem of Gruslys for hypercubes to powers of even cycles, and disprove a conjecture of Gruslys as well as one by Gruslys, Leader and Tan that considers the edge setting.

This type of questions has ramifications far beyond the scope of graph theory.

This is joint work with Natasha Morrison and Alex Scott.

• Marthe Bonamy (LaBRI)
  One (graph) minor to rule them all .

10/10/2024.

Robertson, Seymour and Thomas proved in 2006 that every planar graph on n vertices is a minor of the 2n*2n square grid. This theorem is notably convenient in proving that any graph not containing a given planar graph as a minor has bounded treewidth. After a gentle introduction to graph minors, I will discuss the equivalent of grids for classes other than planar graphs.

• Nicolas Bonichon (CNRS et LaBRI, Université de Bordeaux),
  d-Permutations de Baxter et autres d-permutations à motifs exclus.
  6/10/2022.
  Transparents.

Une permutation de taille $n$ peut-être identifiée à son diagramme : un nuage de $n$ points dans la grille $[n]^2$ tel que chaque ligne et chaque colonne contienne exactement un point. Dans ce papier nous considérons des permutations multidimensionnelles (ou $d$-permutations), qui peuvent être identifiées à des nuages de $n$ points dans la grille $[n]^d$ tels que chaque hyperplan $x_i=j$ avec $i \in [d]$ et $j \in [n]$ contienne exactement 1 point.

Dans un premier temps nous investiguons de manière exhaustive l’énumération des classes de permutations qui évitent des petits motifs. Nous proposons quelques bijections vers d’autres objets combinatoires pour expliquer certaines séquences connues, mais nous laissons également quelques questions ouvertes.

Dans un deuxième temps nous proposons une généralisation des permutations de Baxter aux $d$-permutations. De plus, nous proposons une caractérisation de ces permutations en termes de motifs liés (vincular patterns).

Travail réalisé en collaboration avec Pierre-Jean Morel.

• Valentin Bonzom (LIGM, Université Gustave Eiffel),
  Propriétés d’invariance des b-poids pour les cartes déformées de Chapuy et Dołęga.
  28/09/2023.
  Transparents.

Les cartes combinatoires sont des collages de polygones formant des surfaces de genre arbitraire et orientables ou non. On s'intéressera ici à des modèles de cartes, orientables ou non, introduits par Chapuy and Dołęga. Les cartes y sont pondérées par des b-poids, qui sont des polynômes en une variable b, déterminés récursivement par élimination des arêtes à partir de la racine. Ces modèles sont motivés par le lien avec la combinatoire algébrique, au sens où leurs séries génératrices se développent naturellement sur les polynômes de Jack pour la variable alpha=1+b. Néanmoins, la définition des b-poids les rend délicats à manipuler. Nous prouverons des propriétés d'invariance de la moyenne des b-poids qui sont bien connues pour les cartes orientables mais non-triviales ici. Ce sont des résultats à paraître avec Victor Nador (LaBRI - LIPN).

• Charles Bordenave (CNRS, Université Aix-Marseille),
  Marche au hasard sur un graphe expanseur avec un revêtement.
  29/11/18.

Le temps de mélange d'une chaîne de Markov ergodique finie a une coupure si sa distance à l'équilibre reste proche de sa valeur initiale puis chute abruptement vers zéro. Ce phénomène a été établi pour de nombreuses chaînes de Markov mais il n'y a cependant pas de théorie générale qui l'explique. Dans cet exposé, dans le contexte des marches aléatoires sur des graphes expanseurs, nous verrons des nouveaux critères spectraux pour le phénomène de coupure. Nous établirons notamment une identité entre  des séries génératrices de marches anisotropiques sur le groupe libre.

Travail en collaboration avec Hubert Lacoin (IMPA).

• Gaetan Borot (Max Planck Institute for Mathematics, Bonn),
  The ABCD of topological recursion.
  30/3/2017.

I will give a short introduction to the formalism of topological recursion, which has been simplified and generalised by a recent proposal by Kontsevich and Soibelman: no geometry is necessary to present it, only algebra and combinatorics. The initial data is now a collection (L_i)_i of differential operators in many variables, which are atmost quadratic in derivatives and satisfy Lie algebra commutation relations. The topological recursion then produces the Taylor coefficients of the common solution to the equations {L_i Z = 0}_{i}. For the simplest initial data, Z just counts trivalent graphs with certain conditions, and can be exactly computed in terms of Whittaker functions. In general, the topological recursion appears as a sum over these graphs. 
In fact, finding initial data is not a priori an easy task ! I will present 3 classes of initial data, respectively obtained from the data of a Frobenius algebra, of a non-commutative Frobenius algebra, and of the vector space of formal series with coefficients in a Frobenius algebra. This third class of examples contains the topological recursion from the former Eynard and Orantin perspective -- so, I will review some already known applications of topological recursion to various problems of enumerative geometry, in light of Kontsevich-Soibelman approach, which is hopefully combinatoralist-friendly. 

If time permits I will pose and motivate open questions about large genus asymptotics. 

Based on joint work with J.E. Andersen, L. Chekhov and N. Orantin.

• Alin Bostan (SpecFun, INRIA Saclay),
  Computer Algebra for Lattice Path Combinatorics.
  28/03/2013.
  Transparents.

Classifying lattice walks in restricted lattices is an important problem in enumerative combinatorics. Recently, computer algebra methods have been used to explore and solve a number of difficult questions related to lattice walks. In this talk, we will give an overview of recent results on structural properties and explicit formulas for generating functions of walks in the quarter plane, with an emphasis on the algorithmic methodology.

• Alin Bostan (INRIA Saclay),
  How to decide if a D-finite power series is algebraic?
  04/04/2024.
  Transparents.

A power series is said to be D-finite ("differentially finite”) if it satisfies a linear differential equation with polynomial coefficients. D-finite power series are ubiquitous in combinatorics, as well as in number theory and mathematical physics. In a seminal 1980 article, Richard Stanley asked whether it is possible to decide if a given D-finite power series is algebraic or transcendental.  There are several very useful sufficient criteria for transcendence, but none also provides a sufficient condition. One of them is a powerful criterion due to Philippe Flajolet, based on asymptotics of coefficients. Characterizing the algebraicity of a D-finite power series is a highly non-trivial task even if the sequence of its coefficients satisfies a recurrence of order one: this question was completely settled only in 2023 by Florian Fürnsinn and Sergey Yurkevich, building on important articles by Gilles Christol (1986) and by Frits Beukers and Gert Heckman (1989). In this talk, I will present answers to Stanley’s question and illustrate them through several examples coming from combinatorics and number theory.

• Mireille Bousquet-Mélou (LABRI, Bordeaux),
  Sur les chemins auto-évitants.
  07/10/2011.
  Transparents.

Un chemin auto-évitant sur un réseau de dimension $d$ est une marche qui ne visite jamais deux fois le même sommet. Ces objets naturels sont étudiés en combinatoire, en probabilités, et en physique statistique, mais leurs propriétés sont mal connues, surtout en petite dimension $(d=2,3)$. On présentera d'abord une courte synthèse des résultats et conjectures existants — remarquables pour la dimension 2. Puis on discutera de la recherche de familles exactement résolubles de tels chemins.

• Mireille Bousquet-Mélou (CNRS, LaBRI, Université Bordeaux),
  Sur les orientations bipolaires des cartes planaires.
  29/11/2018.
  Transparents.

Les cartes planaires, étudiées depuis les années 60 par Tutte -- puis beaucoup d'autres -- sont désormais bien comprises. En particulier, 20 ou 30 ans après les premiers travaux récursifs de Tutte, de belles bijections sont venues expliquer la simplicité de ses formules d'énumération. Plus tard, ces bijections ont ouvert la voie à l'étude des grandes cartes aléatoires, vues comme des espaces métriques.

Les cartes équipées d'une structure restent plus mystérieuses. Pour beaucoup de structures, par exemple les colorations propres, l'énumération a été faite, mais pas de façon bijective. Et les propriétés asymptotiques des grandes cartes structurées restent à élucider.

Dans cet exposé, on traitera des cartes équipées d'une orientation bipolaire, en montrant qu'elles ont une combinatoire particulièrement riche, liée notamment aux chemins confinés dans un cône. Ceci permet de les dénombrer, récursivement et bijectivement, et d'établir quelques résultats d'universalité asymptotique.

Travail en commun avec Éric Fusy et Kilian Raschel.

• Mireille Bousquet-Mélou (LaBRI, Université de Bordeaux)
  Computer algebra in my combinatorics life.

O7/12/2023.
Transparents.

Many of my papers would just not exist without computer algebra. I will describe how CA has become an essential tool in my research in enumerative combinatorics. The point of view will be that of a (sometimes naive) user, not of an expert. Many examples and questions will be taken from a joint paper with Michael Wallner dealing with the enumeration of king walks avoiding a quadrant (arXiv 2021, to appear). My hope is that some of the questions that I will raise will have an immediate answer ("yes, this is done") and/or that some people in the audience will find a question interesting enough to take it back home.

Cédric Boutillier (LPMA, Paris 6),
The Z-invariant Ising model on isoradial graphs.
30/3/2017.
Transparents.

The Ising model is a mathematical model for ferromagnetism in which spins are located at vertices of a graph. For a large class of embedded planar graphs, called isoradial graphs, local weights for this model can be found so that an integrability condition (the Yang-Baxter relation) is satisfied. The model is then said to be Z-invariant.

In a joint work with Béatrice de Tilière (Créteil) and Kilian Raschel (Tours), we study the Z-invariant Ising model on infinite isoradial graphs. We show that certain probabilistic quantities have a local expression in terms of the geometry of the embedding of the graph. Our main tool is Fisher's bijection between the Ising model and a dimer model on a decorated graph. We will discuss the properties of this model in connection with the geometry of an algebraic curbe naturally
associated to the dimer model.

• Cédric Boutillier (LPSM, Sorbonne Université)
  Limites de tableaux de Young aléatoires : une approche déterminantale.
  28/09/2023.
  Transparents.

Nous présentons des résultats pour la limite d'échelle et la limite locale de grands tableaux de Young standards uniformes dont la forme (renormalisée) λ0 est fixée. Le point de départ est l'analyse asymptotique d'un processus déterminantal étudié par Gorin et Rahman, qui permet en particulier :
- de calculer la surface limite pour la limite d'échelle à partir d'une équation polynomiale dépendant de λ0;  
- de décrire la limite locale de ces grands tableaux de Young par une famille de tableaux de Young infinis, construits à partir du processus du collier de perles.
Collaboration avec Jacopo Borga, Valentin Féray et Pierre-Loïc Méliot.

• Jérémie Bouttier (IPHT, CEA et LIAFA, CNRS et Université Paris Diderot),
  Des boucles sur les cartes aléatoires.
  20/10/2011.
  Transparents.

Introduit en physique statistique, le modèle $O(n)$ peut être formulé en termes de boucles évitantes (ou cycles disjoints) sur un graphe, $n$ jouant le rôle d'un poids par boucle. Ce modèle a été naturellement considéré sur les cartes aléatoires et, dans certains cas, "résolu" à l'aide d'intégrales matricielles. Nous proposons ici une nouvelle approche combinatoire à ce modèle. Le problème combinatoire consiste à énumérer les cartes planaires munies d'une configuration de boucles évitantes. A une telle carte, l'opération consistant à effacer toutes les boucles et leurs intérieurs associe une autre carte, sans boucles mais à "trous". Cette opération n'est bien sûr pas bijective, mais donne une décomposition qui se traduit par des relations de substitutions entre séries génératrices, que nous pouvons résoudre explicitement dans certains cas. En termes probabilistes, notre décomposition établit un lien entre le modèle $O(n)$ et le modèle des "cartes stables" introduit par Le Gall et Miermont.
Travail en collaboration avec G. Borot et E. Guitter.

• Jérémie Bouttier (IPhT, ENS Lyon),
  De la mesure uniforme à la mesure de Plancherel sur les partitions d’entiers.
  4/04/2019.
  Transparents.

Il existe deux mesures de probabilités "naturelles" sur l'ensemble des partitions d'un entier $n$ : la mesure uniforme, naturelle du point de vue énumératif, et la mesure de Plancherel, naturelle au sens de la théorie des représentations du groupe symétrique.

Ces deux mesures présentent un phénomène de forme-limite : lorsque $n$ devient grand, les diagrammes de Young associés convergent, une fois remis à l'échelle, vers des formes géométriques déterministes (Vershik-Kerov-Logan-Shepp pour Plancherel, Vershik pour uniforme).

Cependant, leurs limites microscopiques sont bien différentes : localement la mesure uniforme ressemble à une marche aléatoire (Okounkov) tandis que la mesure de Plancherel donne le processus déterminantal sinus discret (Borodin-Okounkov-Olshanski). Quant à la distribution de la plus grande part, la loi-limite de ses fluctuations est la loi de Gumbel pour la mesure uniforme (Erdős-Lehner) et la loi de Tracy-Widom β=2 pour la mesure de Plancherel (Baik-Deift-Johansson).

Nous proposons une mesure interpolant entre les deux cas. Il s'agit de l'exemple non trivial le plus simple d'un processus de Schur périodique, tel qu'introduit par Borodin. Nous obtenons une description complète des transitions pour la limite microscopique et la loi de la plus grande
part, dont nous verrons qu'elles ont lieu dans des régimes différents. En particulier, la transition pour la loi de la plus grande part s'interprète physiquement comme une compétition entre fluctuations "thermiques" et "quantiques" dans un système de fermions confinés.

Cet exposé repose sur un travail effectué en collaboration avec Dan Betea (Math Phys Anal Geom (2019) 22:3, arXiv:1807.09022 [math-ph]).

• Mathilde Bouvel (Université de Zurich),
  Operators of equivalent sorting power, and related Wilf-equivalences.
  5/12/2013
  Transparents.

Permutation patterns and permutation classes (defined by the avoidance of a set of patterns) have been first introduced in the seventies, in connection with the analysis of sorting devices and partial sorting algorithm. Enumerative combinatorics soon became interested in the study of permutation classes, and many so-called Wilf-equivalences have been proved. Two permutation classes (or two sets of excluded patterns that characterize them) are said Wilf-equivalent when they are enumerated by the same sequence.

In this talk, I will start with a (biased) panorama of these early results on permutation classes, and present new results obtained first with Olivier Guibert (LaBRI, Bordeaux) and then with Michael Albert (Univ. Otago, New Zealand). The main point of this work is the study of some partial sorting operators. But it has unexpected enumerative consequences, as our study allows us to deduce families of Wilf-equivalences.

• Mathilde Bouvel (CNRS, LORIA),
  Mathilde Bouvel (CNRS, LORIA).
  Limite en graphon des cographes aléatoires.
  1/4/2021.
  Transparents.

Étant donnée une famille de graphes, une question naturelle (qui constitue un pan de la littérature en graphes aléatoires) est de décrire la forme limite d'un graphe pris uniformément au hasard dans cette famille. On étudiera cette question pour la famille des cographes, et on décrira leur limite (appelée le "cographon Brownien") dans le formalisme des graphons.

Dans l'exposé, je ne supposerai aucune connaissance préalable des cographes ni des graphons. J'en présenterai d'abord les définitions et quelques propriétés clés, notamment le codage des cographes par des "cotrees". Je décrirai les étapes principales de la preuve de la limite en graphon dans le cas des cographes étiquetés. Cette preuve utilise surtout de la combinatoire analytique sur les "cotrees".

Si le temps le permet, je mentionnerai plusieurs résultats associés, notamment la limite en graphon des cographes non-étiquetés, et des résultats parallèles dans le monde des permutations qui suggèrent une universalité du cographon Brownien.

Travail en commun avec F. Bassino, V. Feray, L. Gerin, M. Maazoun, A. Pierrot.

• Nicolas Broutin (INRIA Rocquencourt),
  Recherches partiellement spécifiées dans les arbres multidimensionnels.
  20/10/2011.
  Transparents.

Nous considérons la recherche d'éléments dans des structures de données multidimensionnelles (quad trees, k-d trees), en particulier lorsque certaines coordonnées ne sont pas spécifiées (partial match query). Nous supposons que les données consistent en un ensemble de points uniformes dans le carré unité. Pour ce modèle, dans une structure contenant $n$ points, Flajolet et Puech ont montré que le nombre de noeuds $C_n(U)$ à visiter pour répondre à une requête demandant l'ensemble des données dont la première coordonnée est $x=U$ est tel que $E[C_n]\sim \kappa n^{\beta}$, où $\kappa$ et $\beta$ sont des constantes explicites. Nous développons une approche basée sur l'analyse des coûts $C_n(s)$ pour des requêtes à $x=s$ fixé. Nous donnons en particulier des estimations précises de la variance et de la distribution limite de $C_n(s)$ lorsque $n\to\infty$. Nos résultats permettent de décrire un processus limite pour $C_n(s)$ lorsque $s$ varie dans $(0,1)$. Nous en déduisons par exemple que le coût de la pire requête est aussi de la forme $\kappa' n^{\beta}$, pour la puissance $\beta$ que précédemment.

Travail en collaboration avec Ralph Neininger et Henning Sulzbach.

• Nicolas Broutin (LPSM)
  Minorants convexes, processus de fragmentation/coalescence et limites d’échelle.
  10/10/2024.

Je présenterai une manière de construire des arbres aléatoires basée sur les minorants convexes de fonctions (aléatoires). Dans le cas Brownien, cette procédure est reliée au coalescent additif et à l'arbre continu Brownien, c'est-à-dire la limite d'échelle d'arbres uniformes, et de la fragmentation naturelle qui consiste à retirer les arêtes dans un ordre aléatoire.

En modifiant un peu la fonction de départ, on obtient un arbre lié au coalescent multiplicatif (graphes aléatoires) et à l'arbre couvrant minimum d'un graphe complet pondéré aléatoirement. Cette construction conduit aussi à la définition naturelle de nouveaux processus de coalescence/fragmentation liés à des graphes aléatoires contraints et/ou à la percolation d'invasion avec sources multiples.

L'exposé sera basé sur des travaux en commun avec J.-F. Marckert d'une part et Arthur Rousseau d'autre part.

• Timothy Budd (Université de Copenhague),
  The peeling process on random planar maps with loops.
  3/12/2015.
  Transparents.

We consider random Boltzmann-distributed bipartite planar maps coupled to $O(n)$ loop models. Inspired by recent progress by Borot and Bouttier on nesting statistics, we show that the perimeter associated to a particular exploration process of such surfaces, the peeling process, can be conveniently described by conditioned random walks on the integers. The corresponding scaling limits in terms of positive self-similar Markov processes can be explicitly identified, and correspond to stable processes which are confined to the half-line with non-standard, but quite natural, boundary conditions. The self-similarity of these processes allows us to employ modern machinery to compute distributions of related exponential integrals, which can be given a natural interpretation in terms of the geometry of the random surfaces with loops.

• Yann Bugeaud (IRMA, Strasbourg),
  Sur le développement décimal de $e$.
  3/12/2015.

Il est fort probable que $e$, $\log 2$ et $\sqrt 2$ soient tous trois normaux en base $10$, c'est-à-dire que, pour tout entier $k$, tout bloc de $k$ chiffres $0, 1, … , 9$ apparaisse dans leur développement décimal avec la fréquence $1/10^k$. De tels résultats semblent cependant complètement hors de portée. Nous nous intéressons à des questions apparemment plus simples : nous prenons un point de vue de combinatoire des mots et, pour tout entier $b$, regardons le développement en base $b$ d'un nombre réel comme un mot infini sur l'alphabet $0, 1, ... , b-1$. Nous montrons que pour $e$, $\log(2016/2015)$ et tout nombre algébrique irrationnel (entre autres nombres classiques), ces mots infinis ne sont pas "trop simples", dans un sens précis. Aucune connaissance particulière n'est requise pour suivre l'exposé.

C

• Luigi Cantini (Laboratoire de Physique Théorique et Modélisation, Université de Cergy Pontoise),
  Inhomogenous Multispecies TASEP on a ring.
  16/10/2014.
  Transparents.

I will report on some ongoing work about a multispecies version of the TASEP, a model which describes the stochastic evolution of a system of particles of different species (labeled by an integer) on a periodic oriented one dimensional lattice, where two neighboring particles exchange their position with a rate which depends on their species. For some choice of these rates the Markov matrix turns out to be integrable and for the same choice the (unnormalized) stationary probability is conjectured to show remarkable positivity and combinatorial properties. I will discuss how integrabilty leads to an interesting algebraic structure underlying this problem which allows to provide exact formulas for the stationary probability of some classes of configurations.

• Pierre Cartier (IHES),
  Algèbres de Hopf combinatoires.
  26/5/2011.
  Transparents.

Les opérations de contraction et d'insertion dans les graphes — selon la prédiction de G.-C. Rota — conduisent à des algèbres de Hopf. On décrira deux exemples principaux, liés aux diagrammes de Feynman et à la monodromie d'équations différentielles. On explicitera les théorèmes de structure sous-jacents.

• Cesar Ceballos (Univ. Vienna),
  Hopf Dreams.
  12/04/2018.
  Transparents.

In this talk we will introduce a new Hopf algebra structure on pipe dreams. These combinatorial objects were introduced by Bergeron and Billey back in the 90’s, and play a fundamental role in the combinatorial understanding of Schubert polynomials in the study of Schubert varieties. We will show remarkable combinatorial properties of the Hopf dream algebra, unexpected connections to the enumeration of certain lattice walks on the quarter plane, and applications to the theory of multivariate diagonal harmonics. This is current joint work with Nantel Bergeron and Vincent Pilaud.

• Peggy Cénac (Université de Bourgogne),
  Chaînes de Markov à mémoire variable et marches aléatoires persistantes.
  28/11/2019.

Cet exposé présentera une petite zoologie de chaînes de Markov à mémoire variable, avec des conditions d’existence et unicité de mesure invariante. Il sera ensuite question de marches aléatoires persistantes, construites à partir de chaînes de Markov à mémoire non bornée, où les longueurs de sauts de la marche ne sont pas forcément intégrables. Un critère de récurrence/transience s’exprimant en fonction des paramètres du modèle sera énoncé. Suivront plusieurs exemples illustrant le caractère instable du type de la marche lorsqu’on perturbe légèrement les paramètres. Les travaux décrits dans cet exposé sont le fruit de plusieurs collaboration avec B. Chauvin, F. Paccaut et N. Pouyanne ou B. de Loynes, A. Le Ny et Y. Offret et A. Rousselle.

• Guillaume Chapuy (LIAFA, CNRS),
  Une formule pour compter les cartes de genre positif.
  3/04/2014.
  Transparents.

Je parlerai de cartes, qui sont des graphes dessinés sur des surfaces orientables. L'énumération de ces objets est un domaine très riche qui a fait l'objet de nombreux travaux. Je donnerai une formule extrêmement simple, apparemment nouvelle, obtenue récemment avec Sean Carrell (Waterloo) permettant d'énumérer les cartes orientables par le genre et le nombre d'arêtes. Cette formule repose sur le fait «classique» que les séries génératrices multivariées de cartes et objets apparentés sont des tau-fonctions de la hiérarchie KP. J'essaierai de dédramatiser un peu cet énoncé en donnant une idée brève de la combinatoire algébrique sur laquelle il repose. Puis je tenterai de montrer comment obtenir une formule toute simple à partir de là dans le cas des cartes générales. Si le temps le permet je tenterai de mettre ce résultat en perspective en le comparant avec ce que l'on peut dire via d'autres approches, bijectives ou à base d'équations de Tutte/boucles. Bien que notre formule soit de saveur très combinatoire, je ne parlerai pas de son interprétation bijective, car je ne la connais pas!

• Philippe Chassaing (IECN),
  The height of the Lyndon tree.
  31/01/2013.
  Transparents. Synthèse.

We consider the set $L_n$ of n-letters long Lyndon words on the alphabet $\{0,1\}$. For a random uniform element $l_n$ of the set $L_n$, the binary tree obtained by successive standard factorization of $l_n$ and of the factors produced by these factorization is the Lyndon tree of $l_n$. We prove that the height $H_n$ of the Lyndon tree of $l_n$ satisfies $\lim_n (H_n/ \ln n) = \Delta$, in which the constant $\Delta$ is solution of an equation involving large deviation rate functions related to the asymptotics of Eulerian numbers ($\Delta \approx 5.091\ldots$). The convergence is the convergence in probability of random variables.

Joint work with Lucas Mercier.

• Frédéric Chapoton (Institut Camille Jordan – ICJ, CNRS),
  Combinatoire des couplages et des ensembles indépendants dans les arbres.
  3/02/2014.
  Transparents.

En théorie des graphes, les notions de couplage et d'ensemble indépendant sont très classiques et fondamentales. Dans cet exposé, je présenterai une description élégante (due à Zito et Bauer-Coulomb) de ce qui se passe dans les arbres, qui fait intervenir un tri-coloriage
canonique des sommets. Il sera notamment question de diagrammes de Feynman, et d'une relation amusante entre le principe de dissymétrie et le Lagrangien d'une théorie quantique des champs. On esquissera aussi une relation avec la géométrie de certaines variétés.

• Brigitte Chauvin (Université de Versailles),
  Des Arbres dans les Urnes de Pólya et réciproquement.
  6/12/2012.
  Transparents.

Les urnes de Pólya se prêtent à de nombreuses approches : par combinatoire analytique, on obtient une description exacte de la composition de l'urne à un instant $n$ fini. C'est plutôt une description par tranche. Quand les systèmes différentiels obtenus se résolvent, c'est magique.
La vision probabiliste conduit plutôt à des résultats sur le comportement global limite de l'urne quand $n$ tend vers l'infini. Nous verrons qu'une transition de phase existe, entre les « petites urnes » à asymptotique Gaussienne et les «grandes urnes», pour lesquelles l'asymptotique du vecteur composition de l'urne fait apparaître une variable aléatoire limite $W$ dont la loi est non classique. L'étude probabiliste repose sur la mise en évidence de la structure arborescente de l'évolution de l'urne. Un raisonnement de type «diviser pour régner» conduit à écrire des équations de point fixe en loi pour $W$, qui ont un intérêt en elles-mêmes et qui donnent des indications sur $W$ (densité, moments) et aussi des conjectures. Enfin plonger l'urne en temps continu produit un processus de branchement dont les agréables propriétés d'indépendance conduisent à d'autres équations de point fixe en loi, pas tout à fait les mêmes qu'en temps discret. Lorsqu'on traduit ces équations sur la transformée de Fourier de $W$, le système différentiel obtenu se résout, faisant avancer la compréhension de $W$.
Travail commun avec Quansheng Liu, Cécile Mailler et Nicolas Pouyanne.

• Maria Chlouveraki (UVSQ),
  Le défaut et le poids des multipartitions.
  25/11/2021.

La combinatoire des multipartitions joue un rôle-clef dans la théorie des représentations des algèbres de Ariki-Koike, qui généralisent les algèbres de Iwahori-Hecke de type A et B. Dans cet expose, nous verrons comment nous pouvons généraliser les notions de longueur de crochet et de poids dans le cadre de multipartitions et les utiliser pour étudier les représentations de ces algèbres dans le cas non-semisimple. Plus spécifiquement, nous allons associer la notion de poids à la notion de défaut qui provient de la théorie des representations, et nous allons montrer que cette dernière est un invariant de blocs. Ceci est un travail en commun avec Nicolas Jacon.

• Frédéric Chyzak (INRIA Saclay),
  Explicit generating series for small-step walks in the quarter plane.
  8/10/2015.
  Transparents.

Lattice walks occur frequently in discrete mathematics, statistical physics, probability theory, and operational research.  The algebraic properties of their enumeration generating series vary greatly according to the family of admissible steps chosen to define them: their generating series are sometimes rational, algebraic, or D-finite, or sometimes they possess no apparent equation.  This has recently motivated a large classification effort.  Interestingly, the equations involved often have degrees, orders, and sizes, making calculations an interesting challenge for computer algebra.

In this talk, we study nearest-neighbours walks on the square lattice, that is, models of walks on the square lattice, defined by a fixed step set that is a subset of the 8 non-zero vectors with coordinates 0 or ±1.  We concern ourselves with the counting of walks constrained to remain in the quarter plane, counted by length.  In the past, Bousquet-Mélou and Mishna showed that only 19 essentially different models of walks possess a non-algebraic D-finite generating series; the linear differential equations have then been guessed by Bostan and Kauers. In this work in progress, we give the first proof that these equations are satisfied by the corresponding generating series.  This allows to derive nice formulas for the generating series, expressed in terms of Gauss' hypergeometric series, to decide their algebraicity or transcendence.  This also gives hope to extract asymptotic formulas for the number of walks counted by lengths.

Based on work in progress with Alin Bostan, Mark van Hoeij, Manuel Kauers, and Lucien Pech.

• Julien Clément (GREYC, Caen),
  Trier des clés: une analyse en moyenne du nombre de comparaisons de symboles.
  29/03/2012.

On aborde classiquement l'analyse en moyenne d'algorithmes en s'intéressant à la complexité mesurée en nombre de comparaisons. On a alors des résultats de complexité du type "tel algorithme est en $O(n \log n)$ en moyenne" (par exemple Quicksort pour citer un des plus connus). Ces affirmations se basent sur des hypothèses spécifiques -- que les comparaisons entre les données (ou clés), pour les deux premiers, et les comparaisons entre symboles pour le troisième ont un coût unitaire -- et elles ont le mérite évident de présenter un tableau facile à assimiler de la complexité des algorithmes de tri. Cependant, ces hypothèses simplificatrices sont de fait discutables: elles ne permettent pas de comparer précisément les avantages et inconvénients d'algorithmes reposant sur des principes différents (i.e., ceux qui comparent les clés et ceux qui utilisent une représentation sous forme de suite de symboles) d'une manière qui soit totalement satisfaisante à la fois du point de vue de la théorie de l'information et du point de vue algorithmique. En effet, d'abord le calcul n'est pas vu à son niveau le plus fondamental, c'est-à-dire, par la manipulation de symboles élémentaires tels que le bit, l'octet, le caractère ou le mot-machine. De plus les analyses simplifiées ne sont pas toujours informatives dans beaucoup d'applications (bases de données ou traitement de la langue naturelle), où l'information est de nature hautement 'non atomique' , au sens qu'elle ne se réduit pas à un seul mot-machine. J'exposerai à l'aide de plusieurs exemples d'algorithmes de tri une méthode qui permet d'analyser en moyenne le nombre de comparaisons de symboles. Les clés à trier sont vues comme des séquences de symboles produit par un modèle de source général. Pour des sources particulières (comme les sources sans mémoire) on accède à une analyse fine (avec le calcul de constantes explicites...) de certains de ces algorithmes de tri. 

En collaboration avec Brigitte Vallée, Thu Hien Nguyen-Thi (et initié avec Philippe Flajolet).

• Eric Colin de Verdière (CNRS, ENS),
  Théorèmes à la Helly, motifs d’intersections et combinatoire topologique.
  3/10/2013.
  Transparents.

Le théorème de Helly (1923) énonce une propriété des motifs d'intersections des familles (finies) de convexes de $R^d$: Pour vérifier qu'une telle famille est d'intersection non vide, il suffit de vérifier que chaque sous-famille de taille au plus $d+1$ est d'intersection non vide. 
On peut représenter combinatoirement les motifs d'intersections d'une famille quelconque d'ensembles à l'aide d'un complexe simplicial, son _nerf_.  Le théorème du nerf en combinatoire topologique permet de montrer une version topologique du théorème de Helly. 

Je décrirai une généralisation de ce dernier résultat à des familles d'objets non connexes de $R^d$, qui repose sur une variante de la notion de nerf et sur une extension d'un théorème de projection dû à Kalai et Meshulam, et des applications en géométrie combinatoire. 

Travail en commun avec Grégory Ginot et Xavier Goaoc.

• Filippo Colomo (Istituto Nazionale di Fisica Nucleare, Firenze),
  Limit shapes of large Alternating Sign Matrices.
  3/04/2014.
  Transparents.

Alternating Sign Matrices (ASMs) are square matrices satisfying the following conditions: a) possible entries are 0,1,-1; b) non-zero entries alternate in sign along each row and column; c) the sum of entries of any fiven row or column is equal to 1. In the limit of large dimensions ASMs are known to develop a limit shape, with the appearance of four corner regions containing only 0's, and sharply separated from a central and approximately circular region, containing also non-zero entries. The original derivation of an analytic expression for the curve describing the limit shape is reviewed. The
corresponding expression for the case of weighted enumerations of ASMs is provided as well. An alternative derivation is discussed, which allows for extension of the above results to ASMs of generic shape (more precisely, to generic shape subregions of the square lattice graph, with an entry associated to each vertex, and all entries satisfying ASMs'conditions).

Joint works with Andrei Pronko, Paul Zinn-Justin, Andrea Sportiello

• Robert Cori (Labri-Bordeaux),
  Développements récents dans le modèle combinatoire du tas de sable sur un graphe.
  3/11/2011.
  Transparents. Synthèse.

Dans le modèle combinatoire du tas de sable on affecte à chaque sommet d'un graphe un entier positif ou nul censé représenter un nombre de grains situés sur le sommet en question. Une règle d'éboulement permet de faire passer des grains d'un sommet à ses voisins. Deux généralisations du modèle avec l'affectation d'entiers pouvant être négatifs ont été considérées par différents auteurs. La première peut être interprétée par des particules et anti-particules qui se détruisent mutuellement lors d'un éboulement. La seconde comme des soldes de comptes en banque qui peuvent être redistribués aux voisins ou bien faire l'objet d'un versement collectif. Il sera question dans cet exposé de résultats récents obtenus dans le cadre de ces deux modèles et en particulier d'un article de M. Baker et S. Norine dans Advances in Mathematics datant de 2007 et intitulé Riemann-Roch and Abel-Jacobi theory on a finite graph qui a particulièrement interessé l'orateur.

• Sylvie Corteel (Laboratoire d’Informatique Algorithmique: Fondements et Applications, CNRS),
  Diamants aztèques, Partitions pyramides, Pavages pentus, et Gares de triage.
  4/12/2014.
  Transparents.

Je parlerai de modèles généraux de dimères (ou pavages) sur certains graphes planaires bipartis, dont l'énumération est exactement soluble. Ces modèles appelés «pavages pentus» (pour le réseau carré) et «graphes de gare de triage» (dans le cas général) généralisent à la fois le diamant aztèque, les partitions pyramides, et les partitions planes. Ils se reformulent en termes de modèles de particules, puis de «processus de Schur» via la correspondance Boson-Fermion.

Grâce à une approche par matrice de transfert et à la construction de nouveaux opérateurs de localisation, on obtient non seulement l'énumération mais aussi la matrice Kasteleyn inverse et les corrélations (déterminantales) entre les dimères.

Les deux articles sous-jacents sont communs avec Jérémie Bouttier et Guillaume Chapuy pour le premier, et avec ces deux auteur.e.s plus Cédric Boutillier et Sanjay Ramassamy pour le second.

• Sylvie Corteel (IRIF),
  Combinatoire des modeles de vertex colorés.
  31/03/2022

Des modèles de vertex intégrables ont récemment été utilisés pour étudier diverses familles de polynômes symétriques et non symétriques. Dans cet exposé, nous définirons des modèles colorés, à partir desquels nous construirons une famille de fonctions de partition égales aux polynômes LLT et une famille de fonctions de partition égales aux fonctions super-ruban de Lam. En utilisant le formalisme du modèle de vertex, nous pouvons prouver de nombreuses propriétés de ces polynômes, y compris la (super)symétrie et des identités de Cauchy. Enfin, nous discuterons des applications de nos modèles de vertex aux k-pavages du diamant aztèque.

Ceci est basé sur des travaux avec Andrew Gitlin, David Keating et Jeremy Meza.

• • Julien Courtiel (GREYC, Université de Caen-Normandie),
    Comprendre les équations de Dyson-Schwinger via les diagrammes de cordes.
    1/06/2023

Transparents.

La combinatoire analytique démontre toute sa puissance à l'aune de ses applications, de l'analyse d'algorithmes à la physique statistique, de la bio-informatique aux probabilités. Dans cet exposé, nous allons voir comment la théorie de Philippe Flajolet permet de voir sous un jour nouveau certains travaux en théorie des champs quantiques.
 Nul besoin d'être un physicien nobélisé pour suivre cet exposé : je commencerai par (essayer de) vulgariser (avec des dessins de chats) le contexte physique sous-jacent et ce que sont les équations de Dyson-Schwinger.
En utilisant des travaux de Yeats et al., nous verrons que les solutions à ces équations peuvent se voir comme des séries génératrices d'objets combinatoires : les diagrammes de cordes (décorés de manière un peu bizarre). Nous appliquerons alors la théorie de la combinatoire analytique pour décrire ces objets et donner une estimation asymptotique des coefficients de ces solutions. Quand il s'agira de donner une interprétation physique de ces résultats, nous constaterons une surprenante dichotomie entre les différentes théories des champs quantiques.

• Nicolas Curien (Département de Mathématiques de l’Université Paris-Sud Orsay),
  Épluchage des cartes planaires et applications (On the peeling process of random maps).
  4/12/2014.

The spatial Markov property of random planar maps is arguably one of the most useful properties of these random lattices. Roughly speaking, it says that after exploring a region of the map, the law of the remaining part only depends on the perimeter of the discovered region. It has been first heuristically used by Watabiki in the physics literature under the name of ``peeling process'' but was rigorously defined in 2003 by Angel in the case of the Uniform Infinite Planar Triangulation (UIPT). Since then, it has been used to derive information about the metric, (bernoulli and first passage) percolation, simple random walk and recently about the conformal structure of random planar maps. It is also at the core of the construction of "hyperbolic" random maps. In this talk, we will introduce smoothly the peeling process and present some of its main applications.