2018 – 2019

Le séminaire a eu lieu les jeudis 20 septembre 2018, 29 novembre 2018, 7 février 2019, 4 avril 2019, et 6 juin 2019.

20 septembre 2018

• Arnaud de Mesmay (CNRS, Gipsa-Lab, Université Grenoble),
  Allers-retours entre les graphes plongés et la géométrie des surfaces.
  Transparents.

Dans cet exposé, nous expliquerons à l'aide de problèmes précis comment la géométrie continue (riemannienne) des surfaces peut éclairer la combinatoire des graphes plongés et vice-versa. Nous dresserons des parallèles entre du premier côté les géodésiques, les homotopies optimales et les balayages, et de l'autre côté les cycles non-triviaux (edge-width), l'algorithmique d'un problème de recherche de graphes planaires (hauteur d'homotopie) et les décompositions arborescentes des graphes planaires. L'exposé ne présuppose aucune connaissance en géométrie différentielle ou en topologie.

Basé sur des travaux réalisés avec Erin Chambers, Gregory Chambers, Eric Colin de Verdière, Alfredo Hubard, Francis Lazarus, Tim Ophelders et Regina Rotman.

• Frédéric Jouhet (ICJ, Universite Claude Bernard Lyon 1),
  Congruences modulo des polynômes cyclotomiques et indépendance algébrique de $q$-séries.
  Transparents.

De nombreuses $G$-fonctions ont des coefficients satisfaisant des congruences modulo des nombres premiers. Ces congruences sont de même nature que celles découvertes par Lucas pour les coefficients binomiaux, qui se généralisent à des congruences modulo des polynômes cyclotomiques pour les coefficients $q$-binomiaux. Je donnerai une congruence générale pour des quotients multidimensionnels de $q$-factorielles qui, via un processus de spécialisation, généralise de nombreux résultats de ce type. En termes de séries génératrices, de telles congruences relient des séries entières combinatoires classiques à leurs $q$-analogues. En me focalisant sur le cas des séries à coefficients dans $\mathbb{Z}[q]$, je décrirai un phénomène de propagation de l'indépendance algébrique : lorsque de telles séries sont algébriquement indépendantes sur le corps des complexes pour $q=1$, c'est aussi le cas de leurs $q$-analogues. 

Cet exposé est basé sur des travaux communs avec Boris Adamczewski, Jason Bell et Eric Delaygue.

• Bénédicte Haas (LAGA, Université Paris 13),
  Quelques propriétés géométriques des graphes stables.

Considérons un graphe $G_n$ uniformément choisi dans l'ensemble des graphes à $n$ noeuds étiquetés avec des degrés $D_1,\ldots,D_n$ donnés, eux-mêmes aléatoires i.i.d. tels que $\mathbb E[D^2]<\infty$ et $\mathbb P(D=2)<1$. Molloy et Reed 95 ont montré l'existence d'une composante géante si et seulement si $E[D(D-1)]>E[D]$. On se place ici dans le cas critique $E[D(D-1)]=E[D]$ et on suppose que $\mathbb P(D=k) \sim c k^{-2-\alpha}$, $1<\alpha<2$. Des travaux de Joseph 14, Riordan 12 et Conchon-Kerjan et Goldschmidt (à paraître), il résulte que le graphe $G_n$, après normalisation, converge alors vers un graphe continu aléatoire appelé \emph{graphe stable} d'indice $\alpha$. Nous présenterons ici quelques propriétés géométriques de ce graphe limite.

Basé sur un travail en collaboration avec C. Goldschmidt et D. Sénizergues.

29 novembre 2018

• Mireille Bousquet-Mélou (CNRS, LaBRI, Université Bordeaux),
  Sur les orientations bipolaires des cartes planaires.
  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.

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

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).

• Vincent Delecroix (CNRS, LaBRI, Université Bordeaux),
  Polynomialité dans les méandres.

Les méandres sont les configurations de deux cercles plongés dans la sphère. Le paramètre principal est leur nombre d'intersection. C'est un problème ouvert de déterminer l'exposant de croissance exponentielle du nombre de méandres lorsque l'on fait croître le nombre d'intersection (Di Francesco-Golinelli-Guitter conjecturent que c'est $\sqrt{29}(\sqrt{29}+\sqrt{5})/12)$. Le but de mon exposé sera de présenter deux résultats de polynomialité pour un comptage bi-varié d'une sous classe de méandres. Le premier démontre un équivalent asymptotique lorsque la second paramètre est fixé et le second démontre la polynomialité à partir d'un certain rang lorsque le premier paramètre est fixé.

7 février 2019

• Anne-Laure Basdevant (Université Paris Nanterre),
  Plus longue sous suite croissante avec contraintes.

É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.

• Samuele Giraudo (IGM, Paris-Est Marne-la-Vallée),
  Some combinatorial structures related to operads.
  Transparents.

Operads are devices intended to study algebraic structures by providing an abstraction of the notion of operation, their compositions, and the relations they satisfy. We introduce some elementary notions about operads and review some interactions between this theory and combinatorics. For this purpose, we shall explore how operads are linked with rewrite systems of trees and how to handle them as tools to enumerate families of combinatorial objects. We shall also present analogs of the Young lattice and a notion of dual pairs of graded graphs obtained from operads.

• Wenjie Fang (TU Graz),
  La transformation zeta steep-bounce dans le Cataland parabolique.
  Transparents.

Le treillis de Tamari se définit comme l'ordre faible sur $S_n$ restreint aux permutations qui évitent le motif $231$. Mühle et Williams (2018+) ont généralisé cette construction aux quotients paraboliques de $S_n$, qui donne le treillis de Tamari parabolique. Il s'avère que la somme de tailles de tous les treillis de Tamari parabolique d'ordre $n$ correspond à la dimension de la composante homogène de degré $n$ d'une certaine algèbre de Hopf des pipe dreams, étudiée par Bergeron, Ceballos et Pilaud (2018+). Nous trouvons une explication bijective de ces relations d'équi-énumération reliant ces familles d'objets, en passant par une famille d'arbres coloriés. Muni des bijections trouvées, nous pouvons en déduire des résultats structurels intéressants, certains concernant la transformation zeta sur les chemins de Dyck, qui est centrale dans l'étude combinatoire de l'espace diagonal des coinvariants. 

Ce travail en cours est joint avec Cesar Ceballos et Henri Mühle.

4 avril 2019

• Lionel Pournin (LIPN, Université Paris 13),
  Questions géométriques et combinatoires sur les polytopes en nombres entiers.
  Transparents.

Plusieurs questions et résultats seront présentés sur les polytopes en nombres entiers de dimension $d$ contenus dans un hypercube de côté $k$. La première question abordée portera sur le plus grand diamètre possible pour leur graphe en fonction de $d$ et de $k$, et en particulier dans le cas des zonotopes primitifs. La deuxième question portera sur le nombre de sommets des zonotopes primitifs, qui apparait en physique théorique et en optimisation combinatoire. La troisième question sera celle de la structure des polytopes en nombre entiers en tant qu'ensemble. Les propriétés de connexité d'un graphe dont ils sont les sommets seront présentées et discutées.

Cet exposé repose sur des résultats obtenus en collaboration avec Antoine Deza (McMaster University), Rado Rakotonarivo (Université Paris 13) et Noriyoshi Sukegawa (Tokyo University of Science).

• Victoria Lebed (Université de Caen),
  Du triangle au carré.

Derrière quelque chose d'aussi simple que la relation d'associativité se cache une combinatoire extrêmement riche, qui fait intervenir les triangles, les tétraèdres, les arbres binaires, les réseaux de Tamari, les associaèdres. On s'en inspirera pour parler de la combinatoire de l'équation de Yang-Baxter, et l'on verra apparaître les carrés, les cubes, les tresses, les ordres de Bruhat supérieurs, et une mystérieuse série de polytopes qui commence par un octogone. On esquissera les liens entre cette combinatoire et les théories homologique et homotopique des solutions de l'équation de Yang-Baxter.

• Jérémie Bouttier (IPhT, ENS Lyon),
  De la mesure uniforme à la mesure de Plancherel sur les partitions d'entiers.
  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]).

6 juin 2019

• Cécile Mailler (The University of Bath),
  La marche aléatoire du singe.

Dans ce modèle de marche aléatoire non Markovienne, le marcheur effectue une marche aléatoire simple sauf à des temps exceptionels où il se téléporte à un site qu’il a déjà exploré dans le passé ; il choisit ce site aléatoirement, avec probabilité proportionelle au nombre de temps passé à ce site dans le passé. Les durées des `runs’’ entre deux ``téléportations'’ sont tirées au hasard de façon i.i.d. indépendamment du reste du processus. Dans ce travail en collaboration avec Gerónimo Uribe Bravo (UNAM), nous montrons comment l’étude de ce modèle peut être réduite à celle d’un arbre aléatoire récursif pondéré. Cette approche nous permet de montrer, entre autres, un théorème limite pour la position du marcheur, et ce dans le cas plus général où le processus sous-jacent (i.e. l’évolution du marcheur entre deux téléportations) est n’importe quel processus de Markov vérifiant lui-même un théorème limite de type théorème de la limite central.

• Juanjo Rué (U. Politècnica de Catalunya),
  Enumeration and asymptotic counting of 4-regular planar graphs.

Enumeration of quadrangulations (or equivalently, 4-regular maps) has been known since Tutte's seminal works on map enumeration. However, the similar problem in the graph setting (namely, without a graph embedding) is more complex.

We present the first combinatorial scheme for counting labelled 4‐regular planar graphs through a complete recursive decomposition. More precisely, we show that the exponential generating function of labelled 4‐regular planar graphs can be computed effectively as the solution of a system of equations, from which the coefficients can be extracted. As a byproduct, we also enumerate labelled 3‐connected 4‐regular planar graphs, and simple 4‐regular rooted maps. Finally, we can use techniques from complex analysis to obtain asymptotic estimates for the previous counting problems.

This talk is based on joint works with Marc Noy (UPC) and Clément Requilé (TUW).

• François Bergeron (Université du Québec à Montréal),
  Autour de la conjecture de Foulkes.

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.