Enumerative and analytic combinatorics Thursday December 17, 2020, 2PM, Virtuel Clément Réquilé (Université d'Uppsala) Du modèle d'Ising sur les cartes à l'énumération de certaines classes de graphes planaires Un graphe est étiqueté quand son ensemble de sommets est {1,…,n}, et planaire s'il admet un plongement sur la sphère. Une carte (planaire) est définie comme un plongement particulier. Dans ce contexte, le modèle d'Ising représente l'ensemble des 2-coloriages des sommets d'une carte. Ces coloriages ne sont pas nécessairement propres dans le sens où on autorise les arêtes monochromes. En termes combinatoires, on s'intéresse à la fonction génératrice d'Ising, associée à une famille de cartes, qui compte toutes les cartes 2-coloriées de la famille avec un poids u^m, où m est le nombre d'arêtes monochromes. Bernardi et Bousquet-Mélou ont (entre autres) prouvé en 2011 que la fonction génératrice d'Ising est algébrique pour la famille des cartes et pour celle des triangulations. Dans cet exposé, on va discuter comment on peut appliquer ce résultat à l'énumération de certaines classes de graphes planaires. En premier lieu les graphes planaires bipartis étiquetés. Puis si le temps le permet, les graphes planaires cubiques étiquetés enrichis d'un couplage parfait. Ce dernier point s'avère instrumental pour dériver l'espérance du nombre de couplages parfaits dans un graphe planaire cubique aléatoire. Ce travail est en collaboration avec Marc Noy et Juanjo Rué. Enumerative and analytic combinatorics Wednesday December 9, 2020, 10:30AM, Virtuel Helen Jenne (Université de Tours et Institut Denis Poisson) Combinatorics of the dP3 Quiver For the past several years, Tri Lai, Gregg Musiker, and others have studied the quiver associated to the del Pezzo 3 surface and its associated cluster algebra, with the goal of providing combinatorial interpretations for toric cluster variables. They proved that in most cases the Laurent expansions of toric cluster variables agree with generating functions for dimer configurations of certain subgraphs of the dP3 lattice. Their proof uses the fact that the generating function for dimer configurations of a planar bipartite graph satisfies a recurrence called Kuo condensation, named for its resemblance to Dodgson condensation. However, in some cases, the question of how to combinatorially interpret the toric cluster variables remained unanswered. In this talk, I discuss ongoing joint work with Lai and Musiker which shows that in these cases, the Laurent expansions agree with generating functions for tripartite double-dimer configurations. Enumerative and analytic combinatorics Thursday December 3, 2020, 10AM, Virtuel Marni Mishna, Laurent Viennot Séminaire Flajolet http://semflajolet.math.cnrs.fr/ Enumerative and analytic combinatorics Thursday November 12, 2020, 2PM, En ligne Fufa Beyene (Université d'Addis Ababa) Building bridges between permutations and set partitions using subexceedant functions Mantaci and Rakotondrajao introduced a way to code permutations using subexceedant functions, that is, functions $[n] \rightarrow [n]$ such that $f(i) \leq i$ for all $i$. On the other hand, set partitions of $[n]$ can be coded using subexceedant functions too, for instance by using what Mansour calls the “canonical form” of a set partition (each integer is associated with number of its block). Orlov for instance shows how to use the characterisation of subexceedant functions that are the code of set partitions (Restricted Growth Function) to implement an efficient exhaustive generation algorithm. Using these different codes, we make a bridge between the set of set partitions of $[n]$ and the set of permutations over $[n]$ and we relate statistics over the former to statistics over the latter. In particular : - we define a class of permutations (Bell permutations of the second kind) in bijection with set partitions and we give its characterisation; - we characterise the codes of ‘flattened’ partitions (permutations obtained by flattening a set partition) - we give an enumeration of flattened partitions by number of run and provide a combinatorial proof of this result. - we give a number of combinatorial proofs of some identities satisfied by these objects. Enumerative and analytic combinatorics Thursday October 15, 2020, 2PM, Salle 3052 Philippe Biane (CNRS et Université Gustave Eiffel) Marches dans le quart de plan et triangulations je présente une construction très simple de triangulations à partir de marches dans le quart de plan, qui permet de retrouver de façon unifiées plusieurs bijections connues. Enumerative and analytic combinatorics Thursday October 8, 2020, 2PM, Salle 3052 Valérie Berthé (IRIF) Autour de la numération d’Ostrowski Le système de numération d’Ostrowski est intimement lié à l’algorithme d’Euclide et à l’algorithme des fractions continues. Il s’agit de représenter des entiers et des réels selon une base donnée par les convergents d’un réel donné. Cette numération a de nombreuses applications allant de l’approximation diophantienne non homogène à la combinatoire des mots. Nous considérons ici cette numération selon une approche probabiliste et ergodique, en établissant en particulier l’existence de lois normales pour les propriétés statistiques des chiffres. Il s’agit d’un travail en collaboration avec Jungwon Lee. Enumerative and analytic combinatorics Thursday June 25, 2020, 2PM, Virtuel Henri Derycke (Université de Caen) Une restriction pour un polynôme de Tutte sur la grille infinie Dans le cas des graphes finis, le polynôme de Tutte est un invariant bivarié se spécialisant en plusieurs autres invariants de graphe comme le polynôme chromatique. Il peut se définir par une somme sur les arbres couvrants du graphe pondérée par deux statistiques : les activités interne et externe au sens de Tutte du graphe. En s'intéressant à des arbres couvrants dont la racine serait placée à l'infini dans une direction, je propose dans cet exposé un analogue (sommable) de cette définition sur le graphe infini $Z^2$: la série génératrice pour une période donnée des forêts couvrantes périodiques selon cette période, d'une généralisation des activités des arêtes du domaine fondamental. Les marginales du polynôme ont alors le bon goût d'être égales et invariantes au changement de direction des racines bien que leur loi jointe en dépende. Ce travail est notamment motivé par l'étude de configurations bipériodiques récurrentes dans le modèle du tas de sable sur la grille $Z^2$ qui sont en bijection avec ces forêts périodiques. Il s'agit d'un travail en commun avec Yvan Le Borgne. Enumerative and analytic combinatorics Thursday June 18, 2020, 2PM, On line Hugo Mlodecki (Université Paris-Saclay) Un isomorphisme bidendriforme de WQSym Grâce aux travaux de Foissy, on sait que l'algèbre de Hopf WQSym est isomorphe à sa duale car bidendriforme. Cependant, le seul isomorphisme explicite connu ne respectait pas la structure bidendriforme. Cette structure est entièrement déterminée par les éléments totalement primitifs (annulés par les demi co-produits). Nous avons construis deux bases indexées par une nouvelle famille combinatoire appelée forêt biplanes, en bijection avec les mots tassés. Dans ces base, les éléments primitifs sont indexés par les arbres et les totalement primitifs par un certain sous-ensemble d'arbres. Ainsi, nous obtenons les premières bases explicites des éléments totalement primitifs dans WQSym et WQSym*. Enumerative and analytic combinatorics Thursday June 4, 2020, 2PM, On line Éric Fusy (LIX) Cartes de genre non fixé et arbres bourgeonnants Les bijections à l'aide d'arbres étiquetés ou arbres bourgeonnants impliquent que la fonction à 2 points R_i(g) des quadrangulations planaires satisfait le système récursif R_i(g)=1+g*R_i(g)*(R_{i-1}(g)+R_i(g)+R_{i+1}(g)), et en particulier R_1(g) est la série génératrice des quadrangulations planaires (enracinées), ou dualement des cartes tétravalentes planaires. Par ailleurs la méthode des polynômes orthogonaux permet de montrer que la série génératrice des cartes tétravalentes de genre non fixé est la première composante r_1(g) de la séquence r_i(g) de séries formelles satisfaisant le système récursif r_i(g)=i+g*r_i(g)*(r_{i-1}(g)+r_i(g)+r_{i+1}(g)). Nous en donnerons une interprétation bijective à l'aide d'arbres bourgeonnants, qui explique aussi la grande ressemblance avec la récurrence pour les R_i(g). Une extension de la construction donne également une interprétation des r_i(g) comme comptant certaines cartes avec marquages multiples. Cette interprétation permet ensuite d'établir une equi-énumération (dont une preuve bijective reste à trouver) entre les cartes avec poids N par face (permettant un contrôle sur le genre) et certaines cartes avec marquages multiples. Travail en commun avec Emmanuel Guitter Enumerative and analytic combinatorics Thursday May 7, 2020, 2PM, On line Baptiste Louf (IRIF) Limites locales de cartes de grand genre et universalité La notion d'universalité est un concept important dans l'étude des cartes combinatoires : on observe des phénomènes similaires pour différents modèles de cartes. L'exemple le plus célèbre est la convergence d'échelle de nombreux modèles de cartes planaires aléatoires vers la carte brownienne. En 2012, Benjamini et Curien ont formulé une conjecture sur la limite locale des triangulations de grand genre, que nous avons démontrée en 2019 avec Thomas Budzinski.. Dans un deuxième travail, nous étendons l'étude des limites locales en grand genre à une vaste classe de cartes (plus précisément les cartes biparties à degrés prescrits). Cet exposé sera une introduction à nos techniques, qui reposent à la fois sur des arguments probabilistes et sur des récurrences énumératives que j'ai obtenues dans un travail indépendant via la hiérarchie de 2-Toda. Enumerative and analytic combinatorics Thursday April 30, 2020, 2PM, BBB Guillaume Chapuy (Université de Paris) Polynômes de Jack, cartes non-orientables, et b-positivité Je parlerai du papier arXiv:2004.07824 que l'on vient de mettre sur l'arxiv avec Maciek Dołęga (bien connu de l'IRIF!). Il est classique en combinatoire qu'il existe un lien entre cartes (orientables), permutations, et via la théorie des représentations, fonctions de Schur. En 1996 Goulden et Jackson on formulé la “b-conjecture” qui dit que ce lien subsiste si l'on remplace les fonctions de Schur par des polynômes de Jack, qui en sont une déformation à un paramètre (appelé “b”). Cette conjecture est ouverte et difficile, car la théorie des représentations ne marche plus! Dans ce travail avec Maciek, nous faisons un progrès substantiel vers la b-conjecture, et en fait on fait un peu plus, en étudiant la “fonction tau” des constellations sur des surfaces non-orientables, et sa b-déformation. Notre preuve utilise, d'un côté, des équations “à la Tutte”, de l'autre de la combinatoire des tableaux type “règles de Pieri”, et aussi beaucoup de travail. Le but de l'exposé sera au moins d'énoncer et de situer le résultat, et de donner une idée de ce qui intéressant dans ce qu'on a fait, voire dans la preuve. Enumerative and analytic combinatorics Thursday April 16, 2020, 2PM, Online Viviane Pons (Université Paris-sud) Involution “Montée - Contacts” sur les intervalles de Tamari Nous présentons une involution sur les intervalles de Tamari qui échange deux séries de statistiques : les “montées” et les “contacts”. Cette involution fait intervenir de nombreux objets combinatoires : chemins de Dyck, arbres, intervalles-posets. Enumerative and analytic combinatorics Thursday April 9, 2020, 2PM, Online Camille Combe (IRMA) Three interacting families of Fuss-Catalan posets We introduce Three families of posets depending on a nonnegative integer parameter $m$. The underlying sets of these posets are enumerated by the $m$-Fuss Catalan numbers. Among these, one is a generalization of Stanley lattices and another one is a generalization of Tamari lattices. We will see that these three families of posets are related. Indeed, they fit into a chain for the order extension relation and they share some properties. Furthermore, we will see that two associative algebras are constructed as quotients of generalizations of the Malvenuto-Reutenauer algebra. Their products describe intervals of our analogues of Stanley lattices and Tamari lattices. In particular, one is a generalization of the Loday-Ronco algebra. This is a joint work with Samuele Giraudo. Enumerative and analytic combinatorics Thursday April 2, 2020, 2PM, Online Andrew Elvey Price (LaBRI) Counting lattice walks by winding angle using Jacobi theta functions We count lattice walks by winding angle around the origin on four different lattices including the square lattice and the triangular lattice. The method uses a decomposition of each lattice, which allows us to write functional equations characterising generating functions for these walks. We then solve these equations in terms of Jacobi theta functions, allowing us to extract information about the (differential) algebraicity of these generating functions, as well as asymptotic information about the associated counting sequences. For each of the four lattices, we then use the reflection principle to count walks confined to cones such as the quarter plane and three quarter plane. On the square lattice, most of our results were derived by Timothy Budd in 2017 using a very different method, based on an explicit eigenvalue decomposition of certain matrices counting paths in the lattice. Enumerative and analytic combinatorics Thursday March 12, 2020, 2PM, Salle 1007 Marie Albenque (LIX - École Polytechnique) Énumération bijective bivariée des cartes en genre supérieur En 1991, Bender et Canfield ont montré que la série génératrice des cartes en genre supérieur (énumérées par leur nombre d’arêtes) admettait une paramétrisation rationnelle faisant intervenir une série d’arbres décorés. Ce résultat a été raffiné en 1993 par Bender, Canfield et Richmond qui ont prouvé un résultat similaire pour la série génératrice bivariée des cartes (énumérées par leur nombre de sommets et de faces). La preuve de leur résultat est essentiellement calculatoire et n’explique pas de manière combinatoire l’apparition de cette série d’arbres. Pour expliquer le résultat en genre 0, en 1997, Gilles Schaeffer a construit une bijection entre cartes planaires et arbres décorés. Je présenterai dans mon exposé une généralisation de cette construction au genre supérieur due à Mathias Lepoutre et expliquerai comment cette construction permet aussi de donner une preuve bijective du résultat d’énumération bivariée. Enumerative and analytic combinatorics Friday March 6, 2020, 11AM, Salle 1007 Jérémie Bouttier (CEA / ENS Lyon) Sur l'énumération des hypercartes planaires Une hypercarte est une carte munie d'un bicoloriage propre des faces. On associe à chaque face un poids dépendant de sa couleur et de son degré, et on définit le poids de Boltzmann d'une hypercarte comme le produit des poids de ses faces. La série génératrice des hypercartes planaires, munies de leurs poids de Boltzmann, généralise celle des cartes planaires et donne, après une simple transformation, la fonction de partition du modèle d'Ising (recuit) sur les cartes planaires. Les physiciens théoriciens ont beaucoup étudié cette série par le biais du «modèle à deux matrices», et observé que ses singularités sont beaucoup plus riches que celle des cartes planaires. Des approches bijectives, par le biais des arbres bourgeonnants et des mobiles, ont été proposées dans les années 2000 par Bousquet-Mélou–Schaeffer, et Bouttier–Di Francesco-Guitter respectivement. Ces approches ne sont pas complètement satisfaisantes, car elles ne permettent par exemple pas de compter bijectivement les hypercartes avec une face externe de degré prescrit. J'expliquerai comment résoudre ce problème, par une adaptation de la méthode de la décomposition en tranches. Il s'agit d'un travail en cours avec Marie Albenque, notre objectif étant de donner des preuves bijectives des nombreux résultats énumératifs qu'on trouve dans le dernier chapitre du livre _Counting surfaces_ de Bertrand Eynard. Je mentionnerai aussi un autre travail en cours avec Ariane Carrance, dans lequel nous considérons l'énumération des hypercartes planaires à bord alternant. Enumerative and analytic combinatorics Thursday February 27, 2020, 2PM, Salle 1007 Sandro Franceschi (Université Paris-sud) Invariants de Tutte et Brownien réfléchi dans un cône Dans les années 1970, William Tutte développa une approche algébrique, basée sur des « invariants », pour résoudre une équation fonctionnelle qui apparait dans le dénombrement de triangulations colorées. La transformée de Laplace de la distribution stationnaire du mouvement brownien réfléchi dans des cônes satisfait une équation similaire. Pour être applicable, cette méthode requiert l’existence de deux fonctions appelées respectivement invariant et fonction de découplage. Tous les modèles ont des invariants mais on démontre que l’existence de fonctions de découplage équivaut à une condition géométrique simple sur les angles de réflexion. Pour les modèles qui ont une fonction de découplage, on obtient une expression explicite sans intégrale de la transformée de Laplace en fonction des invariants. En particulier, on obtient à nouveau une formule pour la transformée de Laplace de plusieurs cas bien connus, comme la skew symétrie, les réflexions orthogonales ou le résultat de Dieker et Moriarty qui caractérise les densités stationnaires qui s’écrivent sous la forme d’une somme d’exponentielles. Cette méthode permet de plus de caractériser la nature algébrique de la transformée de Laplace en fonction des modèles. Cet exposé est issu d’un travail en collaboration avec M. Bousquet-Mélou, A. Elvey Price, C. Hardouin et K. Raschel. Enumerative and analytic combinatorics Thursday February 13, 2020, 2PM, Salle 1007 Marni Mishna (Simon Fraser University) Analytic Algebraic Combinatorics A theme in algebraic combinatorics is the search for natural interpretations of quantities arising in representation theory. The Kronecker coefficients are an important example, as they remain mysterious despite study since the 1930s. The Kronecker coefficients are the structure constants for the decomposition into irreducibles of the tensor product of representations of the symmetric group, although in this talk we will start from a definition in terms of a coefficient extraction of a rational generating function. From this vantage point we can examine computational questions, and consider things like the piecewise quasipolynomial nature of the Kronecker function using tools from analytic combinatorics and polyhedral geometry. By bounding the lengths of the partitions, we write the Kronecker function in terms of coefficients of vector partition functions. I will discuss some of the associated computational challenges in addition to the results that we have already obtained and the other insights on the coefficients that our point of view has obtained. Work in collaboration with Mercedes Rosas and Sheila Sundaram Enumerative and analytic combinatorics Thursday January 30, 2020, 2PM, IHP, salle 314 Tba Séminaire Flajolet Enumerative and analytic combinatorics Thursday January 23, 2020, 2PM, Salle 1007 Sergey Dovgal (Université Paris 13) The critical point of phase transition in random objects We will discuss the emerging substructures in graphs with degree constraints, digraphs, acyclic digraphs, and 2-CNF below the point of their respective phase transitions. While long time ago, probabilistic method allowed to establish the location of the transition points, sometimes without establishing the fine structure inside the window, more and more refined methods gradually become available. With analytic combinatorics as a main tool, we will see what exactly is happening when a random structure approaches its boiling point. Based on joint works with Elie de Panafieu and Vlady Ravelomanana. Enumerative and analytic combinatorics Thursday January 16, 2020, 2PM, Salle 1007 Vincent Pilaud (LIX, Ecole Polytechnique) Quotientopes Cet exposé présentera certains aspects combinatoires et géométriques des quotients de treillis de l'ordre faible sur les permutations (le prototype est le treillis de Tamari). En particulier, Nathan Reading a montré que pour toute congruence de l'ordre faible, les cones obtenus en recollant les régions de l'arrangement de Coxeter dans une même classe d'équivalence forment un éventail complet. Je montrerai que cet éventail est l'éventail normal d'un polytope que j'appelle quotientope, et je m'intéresserai au cas où un tel polytope peut s'obtenir en retirant des facettes du permutaèdre (comme dans la construction classique de l'associaèdre). Si le temps le permet, je présenterai aussi ce que l'on sait sur les quotients du treillis des régions d'autres arrangements d'hyperplans, en particulier du groupe de Coxeter de type B. Adapté de différents travaux en commun avec Francisco Santos, Doriann Albertin, et Julian Ritter.