en:seminaires:combi:index

Seminar

Enumerative and analytic combinatorics

Day, hour and place

Thursday at 2pm, room 1007

The calendar of events (iCal format).
In order to add the event calendar to your favorite agenda, subscribe to the calendar by using this link.

Contact(s)

Matthieu Josuat-Vergès

Previous talks

Year 2025

Enumerative and analytic combinatorics
Tuesday April 1, 2025, 2PM, Salle 3071
Fufa Beyene (Université D'Addis Ababa) Familles de partitions d’ensembles de type B comptées par les nombres de Dowling (shiftés)

Notre point de départ a été un résultat de Nabawanda et Rakotondrajao prouvant que les partitions de l’ensemble [n] dans lesquelles aucune fusion de blocs n’est possible sont comptées par B_{n-1}, où B_n désigne le n-ème nombre de Bell, qui compte toutes les partitions de l’ensemble [n]. Ce résultat repose sur une bijection entre l’ensemble des partitions de [n-1] et celui des partitions “sans fusion” de [n]. Nous avons cherché à généraliser ce résultat aux partitions d’entiers de type B, qui sont comptées par les nombres de Dowling D_n.

Buck et al. s’étaient déjà intéressés à cette généralisation. Étant donné que les partitions sans fusion sont équivalentes aux permutations triées par runs, ils ont établi que l’ensemble des permutations de Stirling triées par runs sur n est compté par le nombre de Dowling D_{n-1} .

Dans notre quête d’une généralisation de ce résultat tout en restant dans la famille des partitions d’ensembles, nous avons identifié plusieurs classes de partitions de type B sur ⟨n⟩, toutes de taille D_{n-1}. Nous avons établi des bijections directes entre ces différents ensemble, y compris avec celui des permutations de Stirling triées par runs. Dans certains cas, l’étude de la distribution de certaines statistiques sur ces familles a conduit à des résultats intéressants.

Enumerative and analytic combinatorics
Tuesday March 11, 2025, 11AM, Salle 3071
Hadrien Notarantonio To be announced.

Enumerative and analytic combinatorics
Tuesday March 4, 2025, 11AM, Salle 3071
Mingkun Liu Spectre de longueurs d'une carte métrique aléatoire de grand genre : une approche par la théorie de Teichmüller.

Après une introduction historique, j'expliquerai comment tirer une surface hyperbolique aléatoire (uniforme) de genre g. On se penchera ensuite sur le spectre de longueurs. Plus précisément, on regardera les géodésiques fermées courtes sur une surface hyperbolique aléatoire de genre g. Il se trouve que, lorsque g est grand, les longueurs de ces géodésiques se distribuent exactement de la même manière que les longueurs des cycles courts dans un graphe aléatoire de très grande taille. Il s'agit d'un travail en commun avec Simon Barazer et Alessandro Giacchetto.

Length spectra of random metric map of large genus: a Teichmüller theory approach.

After a brief historical review, I will explain how to pick a (uniform) random hyperbolic surface of genus g. After that, we will focus on the length spectrum. More specifically, we will examine short closed geodesics on a random hyperbolic surface of genus g. It turns out that, when g is big, the lengths of these geodesics are distributed just like the short cycles in a large random graph. This is a joint work with Simon Barazer and Alessandro Giacchetto.

Year 2024

Enumerative and analytic combinatorics
Thursday December 5, 2024, 11AM, IHP
Séminaire Flajolet À L'Ihp Bram Petri, Eleanor Archer, Frédéric Chapoton

https://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Tuesday November 26, 2024, 11AM, Salle 3071
Guillem Perarnau Extremal stationary values for random digraphs

In this talk, we will explore the extremal values of the stationary distribution of random walks on sparse directed random graphs with given degrees. While the stationary distribution in undirected graphs is determined by the degrees, in the directed case, the graph's geometry plays a crucial role. In the first part of the talk, we will discuss the minimum positive stationary value and its implications for the hitting and cover times of such random graphs. In the second part, we will focus on the maximum stationary value, which is intimately connected with the maximum in-degree. We will highlight the case where the in-degrees exhibit power-law behavior and relate it to the power-law hypothesis of the PageRank walk. This talk is based on joint work with Xing Shi Cai, Pietro Caputo, and Matteo Quattropani.

Enumerative and analytic combinatorics
Tuesday November 19, 2024, 11AM, Salle 3071
Clément Chenevière (LISN, Université Paris-Saclay) Une nouvelle description des treillis m-cambriens

Les treillis cambriens, introduits par N. Reading en 2006, sont une généralisation du treillis de Tamari, à tout choix d'élément de Coxeter, dans tout groupe de Coxeter fini. Le treillis de Tamari correspond au “type A linéaire”. Ces ordres partiels admettent plusieurs descriptions, non trivialement équivalentes. Celles-ci donnent lieu à une généralisation commune, comme définie par C. Stump, H. Thomas et N. Williams. Toutefois, aucune de ces descriptions ne fournit de modèle combinatoire pratique.

Dans un travail en cours avec Wenjie Fang et Corentin Henriet, nous proposons une nouvelle définition équivalente des treillis m-cambriens. Nous donnons un critère de comparaison simple et effectif sur des objets simples appelés m-partitions non croisées. Cette définition est obtenue en montrant qu'il existe une unique chaîne c-croissante entre n'importe quelle paire d'éléments comparables, et cette dernière est calculée par un algorithme glouton. Ce faisant, nous introduisons un ordre partiel intéressant sur les intervalles d'un treillis cambriens, qui est nouveau, même pour le cas du treillis de Tamari.

Enumerative and analytic combinatorics
Tuesday November 12, 2024, 11AM, Salle 3071
Relâche relâche

Enumerative and analytic combinatorics
Tuesday November 5, 2024, 2PM, Salle 3071
Hugo Manet Énumération bijective de cartes planaires biparties serrées et irréductibles [heure inhabituelle!]

Les tranches sont une reformulation de la bijection des mobiles (bijection BDG). Sous cette écriture, la géométrie de la carte est plus explicite, et certaines contraintes sont plus faciles à étudier.

Dans cet exposé, je donnerai des formules d'énumération de cartes planaires biparties, dont les faces étiquetées ont pour degrés respectifs 2m_1, 2m_2, … 2m_n. Je présenterai deux types de contraintes étudiées avec des tranches biparties. Une carte est *serrée* si elle ne contient pas de sommet de degré 1, ce qui rend polynomiale la formule d'énumération. Une carte est *2b-irréductible* si tous ses cycles ont longueur au moins 2b, et les cycles de longueur 2b bordent une face. Ces contraintes se formulent naturellement sur les tranches, et peuvent être imposées simultanément.

Basé sur arXiv:2410.08802, travail en commun avec Jérémie Bouttier et Emmanuel Guitter

Enumerative and analytic combinatorics
Thursday October 24, 2024, 2PM, Salle 3071
Mark Skandera [jour et heure inhabituels!] Une généralisation de la formule des défauts de Deodhar pour la multiplication des éléments de base de Kazhdan-Lusztig

Soit H l'algèbre de Hecke d'un groupe de Coxeter (W,S). En étudiant la base Kazhdan-Lusztig de H, Deodhar a considéré les produits C_{w^{(1)} *…* C_{w^{(k)}, où (w^{(1)},… ,w^{(k)}) est une séquence de générateurs dans S. Il a défini et a compté certains “défauts” de telles séquences pour exprimer les produits correspondants dans la base naturelle de H. Nous étendons sa définition à des séquences d'éléments plus généraux de W et exprimons ainsi des produits plus généraux dans la base naturelle de H, dans la cas où W est de type A ou BC. Ce travail a été réalisé en collaboration avec Gavin Hobbs, Tommy Parisi, et Jiayuan Wang.

Enumerative and analytic combinatorics
Thursday October 10, 2024, 11AM, IHP
Séminaire Flajolet À L'Ihp semflajolet.math.cnrs.fr

Enumerative and analytic combinatorics
Tuesday June 18, 2024, 11AM, Salle 3058
Ludovic Morin (LABRI, Université Bordeaux) Probability that n points are in convex position in a convex polygon :
Asymptotic results

\par The study of the probability that $n$ points drawn uniformly and independently in a convex domain of area $1$ (in the plane) are in convex position, meaning, they form the vertex set of a convex polygon, is quite an age-old question. The matter was risen at the end of the $19^{th}$ century with Sylvester's conjecture for $n=4$ points, solved by Blaschke in 1917. Since then, general results for $n$ points came one after the other in the square, the triangle or the disk, as well as other asymptotic results.

\par In this talk I will give an equivalent of the probability $\mathbb{P}_n$ that $n$ points are in convex position in a regular convex polygon to deduce an analogous result for any convex polygon; so far, the most precise formula was due to B\'ar\'any and identified the limit $n^2(\mathbb{P}_n)^{1/n}$ (though B\'ar\'any's formula holds for general convex domains).

\par B\'ar\'any also proved that a convex $n$-gon drawn uniformly in a fixed convex domain $K$ converges to a deterministic domain called the “limit shape”. We briefly present some properties of the limit shape, and in the case where $K$ is a polygon, we present second order results for the fluctuations of the $n$-gon around this domain.

Enumerative and analytic combinatorics
Tuesday June 4, 2024, 11AM, Salle 1007
Pas De Séminaire (Mais Séminaire Flajolet Le Jeudi 6 Juin !) Pas de séminaire

Enumerative and analytic combinatorics
Tuesday May 28, 2024, 11AM, 3058
Viviane Pons Le s-Ordre faible et s-Permutaèdre

Le permutaèdre et le treillis associé de l'ordre faible sur les permutations sont des objets classiques de la combinatoire et géométrie discète. En particulier, les liens géométriques et combinatoires avec l'associaèdre et le treillis de Tamari font l'objet de nombreux travaux. Nous présentons une généralisation de l'ordre faible, le s-ordre faible sur une certaine famille d'arbres et discutons du s-Permutaèdre associé et de sa réalisation possible comme complexe polytopal. En collaboration avec Cesar Ceballos.

Enumerative and analytic combinatorics
Tuesday May 21, 2024, 11AM, Salle 3058
Jang Soo Kim (Sungkyunkwan University (SKKU)) Lecture hall graphs and the Askey scheme

We establish, for every family of orthogonal polynomials in the Askey scheme and the q-Askey scheme, a combinatorial model for mixed moments and coefficients in terms of paths on the lecture hall lattice. This generalizes to all families of orthogonal polynomials in the Askey scheme previous results of Corteel and Kim for the little q-Jacobi polynomials.

This is joint work with Sylvie Corteel, Bhargavi Jonnadula, and Jon Keating.

Enumerative and analytic combinatorics
Tuesday April 30, 2024, 11AM, Salle 3058
Séminaire Reporté Pas de séance

Enumerative and analytic combinatorics
Tuesday April 16, 2024, 11AM, Salle 3058
Relâche (Vacances De Printemps) Relâche

Enumerative and analytic combinatorics
Tuesday April 9, 2024, 11AM, Salle 3058
Relâche (Vacances De Printemps) Relâche

Enumerative and analytic combinatorics
Tuesday April 2, 2024, 11AM, Salle 3058
Relâche Séminaire Flajolet le 4 avril

Enumerative and analytic combinatorics
Tuesday March 26, 2024, 11AM, Salle 3058
Bishal Deb Continued fractions using a Laguerre digraph interpretation of the Foata–Zeilberger bijection

In the combinatorial theory of continued fractions, the Foata–Zeilberger bijection and its variants have been extensively used to derive various continued fractions enumerating several (sometimes infinitely many) simultaneous statistics on permutations (combinatorial model for factorials) and D-permutations (combinatorial model for Genocchi and median Genocchi numbers). We will begin this talk by taking a look at some of these multivariate continued fractions. We will then sketch out the Foata–Zeilberger bijection.

We will then introduce a Laguerre digraph which is a digraph in which each vertex has in- and out-degrees 0 or 1. We then provide a new interpretation of the Foata–Zeilberger bijection in terms of Laguerre digraphs, which enables us to count cycles in permutations. This interpretation enables us to prove some conjectured continued fractions due to Sokal and Zeng (2022) in the case of permutations, and Randrianarivony and Zeng (1996) and Deb and Sokal (2022 arXiv) in the case of D-permutations.

Enumerative and analytic combinatorics
Tuesday March 19, 2024, 11AM, Salle 3058
Victor Nador (IMPAN Krakow) Modèles de tenseurs aléatoires et double limite d’échelle

Le développement perturbatif en graphe de Feynman des matrices Hermitiennes aléatoires s’exprime comme la série génératrice de cartes pondérées, et ce développement est topologique dans la limite des matrices de grande taille N. Les modèles de matrices aléatoires fournissent ainsi un cadre simplifié pour étudier les propriétés d’une théorie de gravité quantique en deux dimensions. Les modèles de tenseurs aléatoires sont une extension de cette idée en dimensions supérieures. Dans cet exposé, après une présentation du cas matriciel, je présenterai les principales propriétés du développement de grande taille pour les tenseurs aléatoires. Je montrerai également comment une méthode combinatoire -la décomposition en schémas- nous permet d’accéder à la double limite d’échelle de ces modèles malgré la méconnaissance de la plupart des ordres du développement en 1/N.

Enumerative and analytic combinatorics
Tuesday March 12, 2024, 11AM, Salle 3052
Pas De Séance : Journées Alea Relâche

Enumerative and analytic combinatorics
Tuesday March 5, 2024, 11AM, Salle 3058
Eleanor Archer Limite d'échelle des arbres couvrants aléatoires

Un arbre couvrant d'un graphe connexe fini G est un sous-graphe connexe de G qui contient chaque sommet et ne contient aucun cycle. Un résultat bien connu d'Aldous énonce que la limite d'échelle de l'arbre couvrant uniforme du graphe complet est l'arbre brownien. En fait cet énoncé est plus général : l'arbre brownien est la limite d'échelle des arbres couvrants uniformes pour un grand ensemble de graphes en grande dimension. Dans cet exposé, nous allons essayer d'expliquer ce phénomène universel, à l'aide des algorithmes d'échantillonnage. Si le temps nous permet, nous allons également discuter des limites d’échelle des arbres couvrants aléatoires non-uniformes. Travaux en collaboration avec Asaf Nachmias et Matan Shalev.

Enumerative and analytic combinatorics
Tuesday February 27, 2024, 11AM, Salle 1007
Gilles Schaeffer From catalytic to algebraic decomposition, bijectively.

A celebrated result of Bousquet-Mélou and Jehanne states that under reasonable combinatorial hypotheses the solutions of polynomial equations with one catalytic variable are algebraic series. We give a combinatorial derivation of this result in the case of order one catalytic equations (those involving only one univariate unkown series), in the form of a recipe to derive systematically an algebraic decomposition or a bijection with a simply generated family of trees from an order one catalytic decomposition.

Join work with Enrica Duchi

Enumerative and analytic combinatorics
Tuesday February 13, 2024, 11AM, Salle 3058
Clément Chenevière Étude énumérative des intervalles dans les treillis de type Tamari

Le treillis de Tamari est un ordre partiel sur les objets Catalan. Il apparaît dans de nombreux domaines de recherche, tissant des liens entre combinatoire, algèbre, représentations, géométrie, et bien d'autres. De nombreuses descriptions de ce treillis donnent lieu à de nombreuses familles de généralisations, notamment les treillis m-Tamari, nu-Tamari et m-Cambriens. Après une “visite guidée” dans ce zoo des généralisations du treillis de Tamari, je présenterai mon travail de thèse. Je parlerai en particulier d'une nouvelle famille d'ordres partiels appelés alt nu-Tamari, généralisant le treillis de Tamari, et de l'étude de leurs intervalles linéaires. J'évoquerai également une conjecture de Stump-Thomas-Williams stipulant que le nombre d'intervalles dans le treillis m-Cambrien en type A linéaire est le même que dans le treillis m-Tamari, et présenterai de mes avancées sur ce sujet.

Enumerative and analytic combinatorics
Thursday February 8, 2024, 10AM, IHP
Séminaire Flajolet À L'Ihp Mylène Maida, Carla Groenland, Carola Doerr, Sanjay Ramassamy

Séminaire de combinatoire bimestriel à l'IHP, voir la page dédiée https://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Tuesday January 23, 2024, 11AM, Salle 1007
Houcine Ben Dali Équations différentielles pour séries de hypercartes avec degrés de sommets, faces et hyperarêtes

On s'intéresse aux séries génératrices de hypercartes orientables et non-orientables dans les quelles on contrôle les degrés des sommets, des faces et des hyperarêtes. On montre que ces séries génératrices sont caractérisées par une famille d'équations différentielles.

Je présenterai une première preuve algébrique qui utilise une déformation des séries de cartes liée aux polynômes de Jack. Cette preuve repose sur un résultat récent obtenu en collaboration avec Maciej Dołęga. Je donnerai également une preuve combinatoire pour le cas orientable.

Enumerative and analytic combinatorics
Tuesday January 16, 2024, 11AM, Salle 1007
Matthieu Josuat-Vergès Fonctions de parking amassées

Les fonctions de parking d'une part, le complexe d'amas d'autre part, sont des objets bien connus en combinatoire algébrique. Ici, nous marions les concepts pour définir les fonctions de parking amassées. Le résultat principal décrit la topologie de ces objets (pour une structure naturelle de complexe simplicial) comme un bouquet de sphères, et décrit aussi la représentation sur leur homologie. Je commencerai par des rappels détaillés sur les fonctions de parking d'une part, sur le complexe d'amas d'autre part. Il s'agit d'un travail commun avec Theo Douvropoulos.

Enumerative and analytic combinatorics
Tuesday January 9, 2024, 11AM, Salle 1007
Pas De Séance (Ag Irif !) Pas De Séance (AG IRIF !)

Year 2023

Enumerative and analytic combinatorics
Tuesday December 19, 2023, 11AM, 3058
Florent Koechlin A canonical tree decomposition for chirotopes (ATTENTION SALLE INHABITUELLE!)

Dans cet exposé, je présenterai une notion d’arbre de décomposition d’un ensemble de points dans le plan (plus précisément de son chirotope, la fonction qui encode l'orientation de tout triplet de point de l'ensemble). Cette décomposition, qui s'appuie sur le concept d'ensembles de points s'évitant mutuellement (“mutually avoiding sets”), s'inspire de la décomposition modulaire des graphes. J'expliquerai pourquoi cette décomposition est canonique, et comment elle peut être utilisée pour calculer le nombre de triangulations d'un chirotope à l'aide de sa décomposition. Il s'agit d'un travail commun avec Mathilde Bouvel, Valentin Féray et Xavier Goaoc.

In this talk, I'll introduce a notion of decomposition tree of a planar point set (more precisely, of its chirotope, that is the function encoding the orientation of any triplet of points in the set). This decomposition relies on the concept of mutually avoiding point sets, and is inspired by the modular decomposition of graphs. I'll explain why this decomposition is canonical, and how it can be used to compute the number of triangulations of a chirotope using its decomposition. This is a joint project with Mathilde Bouvel, Valentin Féray and Xavier Goaoc.

Enumerative and analytic combinatorics
Tuesday December 12, 2023, 11AM, Salle 1007
Philippe Nadeau Mots de Smirnov et conjectures Delta

Je vais décrire une expression combinatoire de la fonction symétrique $SF(n,k,l)=\left.\Theta_{e_k}\Theta_{e_l}\nabla e_{n-k-l}\right|_{t=0}$ en termes de mots de Smirnov, qui sont les mots sur les entiers dont les lettres consécutives sont distinctes. La motivation de ce travail est l'étude d'un anneau de coinvariants avec un jeu de variables commutatives et deux jeux de variables anticommutatives, dont la caractéristique de Frobenius est conjecturée être $SF(n,k,l)$. J'expliquerai aussi en quoi ce résultat constitue un pas vers une version unifiée des “conjectures Delta”. C'est un travail commun avec Alessandro Iraci et Anna Vanden Wyngaerd.

Enumerative and analytic combinatorics
Thursday December 7, 2023, 10AM, IHP
Séminaire Flajolet Et Conférence Ihp: Computer Algebra For Functional Equations In Combinatorics And Physics Du 4 Au 8 Décembre.

Conférence à l'IHP incluant une journée spéciale “Séminaire Flajolet” le jeudi 7.

Inscription obligatoire sur le site de la conférence: https://indico.math.cnrs.fr/event/8115/registrations/

Voir aussi: https://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Tuesday November 28, 2023, 11AM, Salle 1007
Pas De Séance (Évaluation Hceres!) Pas de séance (évaluation HCERES!)

Enumerative and analytic combinatorics
Tuesday November 21, 2023, 11AM, Salle 1007
Théo Lenoir Graphes à décomposition modulaire prescrite et nombre de sous-graphe induits

La décomposition modulaire est un outil bien connu en algorithmique car elle permet de résoudre polynomialement un certain nombre de problèmes complexes. Cependant, son étude d'un point de vue probabiliste a commencé très récemment. L'objectif de cet exposé est de présenter comment, pour une large classe de modèles définies par des contraintes sur la décomposition modulaire, on arrive à connaître la densité de chaque graphe comme sous-graphes induit. Ce résultat implique une convergence au sens des “graphons” : on a la convergence d'un graphe de taille n vers un graphe “continu”.

Enumerative and analytic combinatorics
Tuesday November 14, 2023, 11AM, Salle 1007
Emma Caizergues Exact enumeration of graphs and bipartite graphs with degree constraints

A graph with degree constraints is a graph whose vertices can have degrees only in a certain given subset of N. In particular, the family of graphs with degree constraints contains the k-regular graphs. In this talk, I will present step by step a method to determine the generating function of simple graphs (and simple bipartite graphs) with degree constraints.

Enumerative and analytic combinatorics
Tuesday November 7, 2023, 11AM, Salle 1007
Pas De Séance Pas de séance

Enumerative and analytic combinatorics
Tuesday October 24, 2023, 11AM, Salle 1007
Alice Contat Coeurs critiques sur des graphes aléatoires

Motivés par le désir de construire de grands ensembles indépendants dans les graphes aléatoires, Karp et Sipser ont modifié la construction gloutonne habituelle pour produire un algorithme qui produit un ensemble indépendant avec un grand cardinal, les sommets restants formants un ensemble appelé le coeur de Karp-Sipser. Lorsqu'il est exécuté sur le graphe aléatoire d'Erdös-Rényi $G(n,c/n)$, cet algorithme est optimal tant que $c < \mathrm{e}$. Nous présenterons la preuve d'une conjecture physique de Bauer et Golinelli (2002) affirmant qu'à la criticité, la taille du coeur de Karp-Sipser est de l'ordre de $n^{3/5}$. En cours de route, nous mettrons en évidence les similitudes et les différences avec l'algorithme glouton habituel pour le $k$-coeur. Basé sur un travail commun avec Nicolas Curien et Thomas Budzinski.

Enumerative and analytic combinatorics
Tuesday October 17, 2023, 11AM, Salle 1007
Valérie Berthé Mots de faible discrépance

Le problème de l’affectation du président (the chairman assignment problem) s’énonce comme suit : on suppose que k états forment une union et que, chaque année, un président d’union doit être sélectionné de telle sorte qu’à tout moment, le nombre cumulé de présidents de chaque état soit proportionnel à son poids. La richesse de ce problème réside dans le fait qu’il peut être reformulé à la fois comme un problème d’ordonnancement en recherche opérationnelle, et comme un problème combinatoire de discrépance symbolique ; la discrépance mesure la différence entre le nombre d’occurrences d’une lettre dans un préfixe d’un mot infini et la valeur attendue en termes de fréquence d’apparition de cette lettre. Nous verrons dans cet exposé comment construire des mots infinis à valeurs dans un alphabet fini ayant la plus petite discrépance possible, en revisitant une construction due à R. Tijdeman. Il s’agit d’un travail en collaboration avec O. Carton, N. Chevallier, W. Steiner, R. Yassawi.

Enumerative and analytic combinatorics
Tuesday October 10, 2023, 11AM, Salle 381F du bâtiment Halles aux farines (ATTENTION!)
Vincent Jugé (LIGM, en délégation à l'IRIF) TBA (ATTENTION exceptionnellement en salle 381F bâtiment Halles aux farines!)

Enumerative and analytic combinatorics
Tuesday October 3, 2023, 11AM, Salle 1007
Éric Fusy (CNRS & LIGM, Université Gustave Eiffel) Énumération de rectangulations

Je présenterai des résultats sur l'énumération exacte et asymptotique de rectangulations génériques (partitions d'un rectangle en régions rectangulaires, sans point où 4 rectangles se rencontrent, et considérées selon deux relations d'équivalences, faible ou forte). Ces objets sont en correspondance avec certains modèles de cartes planaires orientées (orientations bipolaires dans le cas faible, structures transverses dans le cas fort), qui peuvent être encodées par certains chemins dans le quart de plan en appliquant une bijection due à Kenyon, Miller, Sheffield et Wilson. Je montrerai également une extension au cas de rectangulations non génériques, donnant un continuum de modèles de cartes planaires aléatoires qui s'approchent asymptotiquement du réseau régulier.

Travaux en commun avec Erkan Narmanli et Gilles Schaeffer

Enumerative and analytic combinatorics
Thursday September 28, 2023, 2PM, IHP
Vincent Bonzom Et Cédric Boutillier Séminaire Flajolet à l'IHP

https://semflajolet.math.cnrs.fr/ Exceptionnellement à 14 heures.

Enumerative and analytic combinatorics
Wednesday July 5, 2023, 2PM, Olympe de Gouges
Anr Combiné TBD

Enumerative and analytic combinatorics
Tuesday July 4, 2023, 9AM, Olympe de Gouges
Journees Du Gt Combalg To be announced.

Enumerative and analytic combinatorics
Monday July 3, 2023, 9AM, Olympes de Gouge
Journees Du Gt Combalg To be announced.

https://jagtcombalg.sciencesconf.org/

Enumerative and analytic combinatorics
Thursday June 29, 2023, 2PM, Salle 147
Writika Sankar (Chennai Institute) Hyperplane arrangements and Fuss-Catalan numbers

Counting regions of hyperplane arrangements has been a traditional topic in enumerative combinatorics. We will start by introducing the basic framework and provide some important definitions, and then discuss some of the general tools and ideas to solve these counting problems. Finally we will introduce Fuss-Catalan numbers and talk about a class of arrangements counted by a special case of these numbers. We will exhibit some bijections and end by discussing a statistic on decorated Dyck paths whose distribution is given by the coefficients of the characteristic polynomial of this arrangement. The latter is joint work with Priyavrat Deshpande and Krishna Menon (Chennai Mathematical Institute).

Enumerative and analytic combinatorics
Wednesday June 28, 2023, 2PM, Olympe de Gouges
Journées Cartes Organisées par M. Albenque, G. Chapuy et E. Duchi

https://indico.in2p3.fr/event/30166/

Enumerative and analytic combinatorics
Thursday June 22, 2023, 2PM, 146, Olympe de Gouges
Balthazar Charles (Université Paris-Saclay) Éléments minimaux des groupes des régions de Shi dans les groupes de Weyl affines

Considérons l'ensemble des hyperplans orthogonaux aux racines d'un groupe de Weyl affine (son arrangement de Coxeter) et gardons seulement les hyperplans associées avec des racines de profondeur 0 et 1 : l'arrangement de Shi. Parmi les bonnes propriétés de l'arrangement de Shi, chacune de ses régions contient une unique alcôve de l'arrangement de Coxeter qui est, dans un sens, minimale. Cette alcôve est encodée par un vecteur d'entiers, son vecteur de Shi, satisfaisant certaines relations. Etant donnée une région de Shi, comment peut-on calculer le vecteur de Shi de son élément minimal ?

Dans cet exposé, on présentera une bijection entre les fonctions de parking au sens de [Armstrong, Reiner, Rhoades ’15] et les vecteurs de Shi des éléments minimaux de chaque région, dans le cas des groupes affines. Pour cela, on étudiera la structure des relations que satisfont les coefficients des vecteurs de Shi. Bien que cette bijection soit “type-free”, on discutera sa spécialisation aux groupes de Weyl classique où elle a une jolie interprétation combinatoire. Finalement, on verra comme application de cette description par les fonctions de parking l'idée d'une preuve pour [Dyer, Hohlweg ’16, Conjecture 2].

Enumerative and analytic combinatorics
Thursday June 15, 2023, 2PM, Salle 147 - Olympe de Gouges
Marc Noy (UPC (Espagne)) Chordal graphs with bounded tree-width

A graph is chordal if its has no chordless cycle of length > 3. The treewidth of a graph G is the minimum k such that G is a subgraph of a k-tree. For fixed t > 0, we find a precise asymptotic estimate for the number of labelled chordal graphs of treewidth at most t. The form of the estimate is n^(-5/2)c^n*n! as for labelled trees.

https://arxiv.org/abs/2301.00194

Enumerative and analytic combinatorics
Thursday June 8, 2023, 2PM, Olympe de Gouges 147
David Forge Généralisation de l'activité des matroides aux arbres

Collaboration avec Rigo Florez. Nous généralisons la définition de l'activité à un cadre plus large contenant les matroides et des arbres enracinés. Ceci était motivé par un problème concernant l'arrangement de Linial.

Enumerative and analytic combinatorics
Thursday June 1, 2023, 11AM, IHP
Seminaire Flajolet Julien Courtiel, Anna Ben-Hamou, Christophe Hohlweg

https://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Thursday May 25, 2023, 2PM, Salle 147 - Olympe de Gouges
Melissa Sherman-Bennett (MIT) The hypersimplex and the m=2 amplituhedron

I'll discuss a curious correspondence between the m=2 amplituhedron, a 2k-dimensional subset of Gr(k, k+2), and the hypersimplex, an (n-1)-dimensional polytope in R^n. The amplituhedron and hypersimplex are both images of the totally nonnegative Grassmannian under some map (the amplituhedron map and the moment map, respectively), but are different dimensions and live in very different ambient spaces. I'll talk about joint work with Matteo Parisi and Lauren Williams in which we give a bijection between decompositions of the amplituhedron and certain matroidal decompositions of the hypersimplex (originally conjectured by Lukowski–Parisi–Williams). We also give a new decomposition of the m=2 amplituhedron into Eulerian-number-many chambers, inspired by an analogous hypersimplex decomposition.

Enumerative and analytic combinatorics
Thursday May 11, 2023, 2PM, 146, Olympes de Gouge
Tia Ruza (Waterloo (Canada)) Multivariate Limit Theorems and Asymptotics via Analytic Combinatorics in Several Variables

Analytic combinatorics in several variables (ACSV) is a field of study focused on the derivation of limit behaviours of multivariate sequences. This talk surveys some of the techniques and applications of ACSV, beginning with an explicit and automated version of a local central limit theorem. The limit theorem, derived by combining the techniques of ACSV with methods for symbolic determinants, applies to combinatorial classes including families of permutations with restricted cycles, integer compositions with tracked summands and n-colour compositions with tracked summands. We also discuss a technique for deriving the asymptotics of coefficients of algebraic series via embeddings into rational series.

Enumerative and analytic combinatorics
Thursday April 20, 2023, 2PM, Salle 3052 et zoom
Jihyeug Jang (Sungkyunkwan University) Negative moments of orthogonal polynomials

If a sequence indexed by nonnegative integers satisfies a linear recurrence without constant terms, one can extend the indices of the sequence to negative integers using the recurrence. Recently, Cigler and Krattenthaler showed that the negative version of the number of bounded Dyck paths is the number of bounded alternating sequences.

In this talk we provide two methods to compute the negative versions of sequences related to moments of orthogonal polynomials. We give a combinatorial model for the negative version of the number of bounded Motzkin paths. We also prove two conjectures of Cigler and Krattenthaler on reciprocity between determinants.

https://cnrs.zoom.us/j/96418479106?pwd=VHo0bC9yaEFNVy9pZm44SmRWOXBrUT09

Enumerative and analytic combinatorics
Thursday April 13, 2023, 11AM, IHP
Seminaire Flajolet SEMINAIRE ANNULE

https://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Friday March 31, 2023, 11AM, Salle 3052
Jorge Alberto Olarte (CUNEF Universidad (Madrid)) Positivity for tropical flag varieties

In this talk we will study different positivity notions that exist for tropical flag varieties. We will start with an introduction to tropical flag varieties and the related polyhedral subdivisions. After explaining what each notion of positivity is and how do they relate to each other, I will provide equations on the Plücker coordinates for each of them. Finally, we discuss the cases where we know that these equations are sufficient.

Enumerative and analytic combinatorics
Thursday March 16, 2023, 2PM, CIRM (Marseille)
Journees Alea du 13 au 17 Mars

https://conferences.cirm-math.fr/2887.html

Enumerative and analytic combinatorics
Thursday March 9, 2023, 2PM, Salle 3052 et zoom
Groupe De Lecture - Eric Fusy (LIGM Gustave Eiffel) Bijections entre intervalles de Tamari et arbres bourgeonnants

Je présenterai un travail récent et en cours avec Wenjie Fang et Philippe Nadeau. Nous y obtenons une manière directe (avec l'aide des interval posets) de mettre en bijection les intervalles de Tamari avec les arbres bourgeonnants de Poulalhon-Schaeffer (qui sont en bijection avec les triangulations simples). Notre construction (différente de celle de Bernardi-Bonichon) étend celle de Baptiste Rognerud entre intervalles de Kreweras et arbres non croisés, elle commute avec l'involution de dualité des intervalles et se spécialise bien aussi aux intervalles synchronisés et aux intervalles modernes.

Enumerative and analytic combinatorics
Thursday February 23, 2023, 2PM, Salle 3052 et zoom
Lucas Gerin (CMAP - Ecole polytechnique) Graphes denses aléatoires : un exemple de limite fractale

Dans les années 2000, une théorie des limites de graphes denses vers des graphes « continus » (aussi appelés « graphons ») a émergé, initiée notamment par Lovasz. Cette théorie a été étendue aux graphes denses aléatoires (sous l'impulsion de Diaconis et Janson), mais il existe très peu d'exemples où la limite est elle-même aléatoire. L'objectif de cet exposé est de présenter un « graphon Brownien » qui est la limite d'une famille de graphes aléatoires uniformes naturels : les cographes. (Basé sur des travaux avec Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Mickaël Maazoun, Adeline Pierrot.)

Enumerative and analytic combinatorics
Thursday February 16, 2023, 2PM, Salle 3052 et zoom
Martin Pépin (LIPN) Directed Ordered Acyclic Graphs, asymptotic analysis and efficient random sampling

Directed Acyclic Graphs (DAGs) are directed graphs in which there is no path from a vertex to itself. They are an omnipresent data structure in computer science and the problem of counting the DAGs of given number of vertices has been solved in the 70's by Robinson. In this talk, I will introduce a new class of DAGs (DOAGs for Directed Ordered Acyclic Graphs), endowed with an independent ordering of the children of each vertex. They offer a new modelisation tool for objects arising from the compaction of tree-like structures.

For this class we obtain a recursive decomposition scheme that is amenable to effective random sampling with control over the number of edges, an optimised sampler for the case when the number of edges is free, and prove an unusual asymptotic behaviour. I will also show that our approach also applies to classical DAGs, thus providing a solution to the problem of sampling DAGs with a prescribed number of edges.

Enumerative and analytic combinatorics
Thursday February 9, 2023, 2PM, Salle 3052 et zoom
Groupe De Lecture - Philippe Biane (CNRS LIGM) A walk through the symmetric group: non-crossing partitions, Tamari lattices, parking functions and Hurwitz graphs

I will cover basic material on non-crossing partitions, the permutahedron and the Tamari lattice, then I will show how these structures play a prominent role in the description of the Hurwitz graph, which is a graph built on the maximal chains in the lattice of non-crossing partitions (or equivalently on parking functions). In particular we will see that the projection from the permutahedron to the Tamari lattice extends to a projection from parking functions to non-crossing trees. I will try to say simple things about simple objects

The slides are in english but, depending on the audience, I will give the talk in english or in french

Enumerative and analytic combinatorics
Thursday February 2, 2023, 11AM, IHP
Seminaire Flajolet (Vincent Juge, Jang Soo Kim, Olya Mandelshtam) IHP

https://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Thursday January 26, 2023, 2PM, Salle 3052 et zoom
Jang Soo Kim (SKKU) Refined canonical stable Grothendieck polynomials and their duals

In this talk we introduce refined canonical stable Grothendieck polynomials and their duals with two infinite sequences of parameters. These polynomials unify several generalizations of Grothendieck polynomials including canonical stable Grothendieck polynomials due to Yeliussizov, refined Grothendieck polynomials due to Chan and Pflueger, and refined dual Grothendieck polynomials due to Galashin, Liu, and Grinberg. We give Jacobi-Trudi-type formulas, combinatorial models, Schur expansions, Schur positivity, and dualities of these polynomials. We also consider flagged versions of Grothendieck polynomials and their duals with skew shapes. This is joint work with Byung-Hak Hwang, Jihyeug Jang, Minho Song, And U-Keun Song.

Enumerative and analytic combinatorics
Thursday January 12, 2023, 2PM, Salle 3052 et zoom
Groupe De Lecture - Philippe Nadeau (CNRS Lyon) Treillis de Tamari et représentations de carquois

Je donnerai une courte introduction aux représentations de carquois, puis étudierai le cas du carquois de type A_n et sa catégorie de représentations rep A_n. On identifiera alors une famille de sous-catégories dites “classes de torsion”, pour finalement esquisser la preuve du résultat suivant: “Les classes de torsion de rep A_n ordonnées par inclusion forment le treillis de Tamaris d'ordre n+1”. L'exposé se veut accessible à tous et toutes, venez nombreux et sans crainte.

Enumerative and analytic combinatorics
Thursday January 5, 2023, 2PM, Salle 3052 et zoom
Jérémie Bouttier (IPHT) Sur les cartes à bords serrés

La formule de Eynard-Collet-Fusy donne une expression simple pour la série génératrice des cartes planaires biparties à trois bords (et comptées selon les degrés des faces internes). Nous verrons qu'une expression encore plus simple est obtenue lorsqu'on impose que les bords sont «serrés», c'est-à-dire de longueur minimale dans leur classe d'homotopie.

Nous discuterons ensuite des généralisations possibles de notre formule à plus de trois bords ou un genre plus élevé. Une limite intéressante est celle des cartes «serrées», c'est-à-dire des cartes dont chaque face est un bord serré. Ceci nous amène à revisiter un problème d'énumération considéré par Norbury, qui a montré que le nombre de cartes serrées est un quasi-polynôme en les degrés des faces. Nous donnons une expression explicite pour ces quasi-polynômes dans le cas planaire.

Cet exposé repose sur des travaux effectués en collaboration avec Emmanuel Guitter et Grégory Miermont.

Year 2022

Enumerative and analytic combinatorics
Thursday December 8, 2022, 2PM, Salle 3052 et zoom
Amanda Burcroff (Harvard) Dyck Path Expansion Formulas for Rank 2 Cluster Algebras

The theory of cluster algebras, introduced twenty years ago by Fomin and Zelevinsky, gives us a combinatorial framework for understanding the previously opaque nature of certain algebras. Each cluster algebra is generated by its cluster variables, which are defined recursively via the process of mutation. In the rank two case, several explicit formulas have been given for the cluster variables in terms of combinatorial, representation theoretic, and tropical objects. We will focus on two such formulas. The first, given by Lee-Schiffler, sums over collections of colored Dyck subpaths, and the second, given by Lee-Li-Zelevinsky, sums over compatible pairs in Dyck paths. We will discuss a correspondence between these two sets of objects, as well as a simplification and quantum generalization of the Lee-Schiffler expansion formula.

Enumerative and analytic combinatorics
Thursday December 1, 2022, 2PM, Salle 1007 et zoom
Groupe De Lecture - Eva Philippe (Eva Philippe (IMJ-PRG)) Nu-Tamari lattice and Nu-associahedron

The goal of this talk is to present the article “Geometry of the $nu$-Tamari lattices in types A and B”, by Cesar Ceballos, Arnau Padrol, Camilo Sarmiento. We will present the nu-Tamari lattice, a generalization of the Tamari lattice where the parameter $nu$ is a lattice path. One incarnation of the nu-Catalan objects is given by the lattice paths weakly above nu. We will explain briefly how certain nu-Tamari lattices partition the usual Tamari lattice. We will focus on the geometric realization of this lattice as a triangulation of a certain polytope. This relies on another incarnation of nu-Catalan objects, the (I, J)-trees introduced by Ceballos-Padrol-Sarmiento.

Enumerative and analytic combinatorics
Thursday November 24, 2022, 11AM, IHP
Seminaire Flajolet TBD

https://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Thursday November 17, 2022, 2PM, Salle 3052 et zoom
Grant Barkley (Harvard University) Extending the weak Bruhat order

The weak (Bruhat) order is a partial order on the elements of a Coxeter group W. Its Hasse diagram describes the 1-skeleton of the permutahedron. For finite Coxeter groups, the weak order has least upper bounds and greatest lower bounds, making it a lattice. But in infinite Coxeter groups, we can fail to have common upper bounds for two elements. Matthew Dyer introduced a poset called extended weak order, motivated by the geometry of the weak order, which contains the usual weak order as a subposet. It is conjectured that the extended weak order is always a lattice, even for infinite Coxeter groups. Recently with David Speyer we have proved this conjecture for the case of affine Coxeter groups. We'll discuss these ideas, focusing on the infinite symmetric group and affine symmetric group.

Enumerative and analytic combinatorics
Thursday November 10, 2022, 2PM, Salle 3052 et zoom
Wenjie Fang, Guillaume Laplante-Anfossi Sous-posets de degré maximal des treillis $\nu$-Tamari

Dans un article récent (arXiv:2208.11417), Aram Dermerjian considère les sous-posets des treillis $\nu$-Tamari constitués par les éléments de degré sortant (resp. entrant) maximal. Il s’intéresse en particulier au cas des treillis $m$-Tamari, et montre que l’un de ces sous-posets est isomorphe à un poset « $m$-Tamari glouton », généralisant l’ordre dextre défini par Frédéric Chapoton sur les chemins de Dyck. Après avoir présenté les définitions et principaux résultats de l’article, nous exposerons une conjecture de Chapoton liant les posets 1-Tamari gloutons à un sous-poset du produit du treillis de Tamari avec lui-même, défini géométriquement à partir d’une approximation cellulaire de la diagonale de l’associaèdre.

Enumerative and analytic combinatorics
Thursday October 27, 2022, 2PM, Salle 3052 et zoom
Eva-Maria Hainzl (TU Wien) Pattern occurences in random maps

In this talk, we will discuss some results and ongoing work concerning central limit theorems for pattern occurences in random planar maps. Based on a toy example ('double glued squares') we discuss our current approach and the challenges to extend it to general patterns of arbitrary size.

Enumerative and analytic combinatorics
Thursday October 20, 2022, 2PM, Salle 1007 et zoom
Jon Boretsky (Harvard) The Nonnegative Flag Variety and its Tropicalization

The flag variety of rank $r=(r_1,\dots,r_k)$ has points corresponding to collections of subspaces $(V_1,\dots, V_k)$ with $V_i$ of dimension $r_i$ such that $V_i$ is contained in $V_{i+1}$. It can be embedded into a multi-projective space, where it is cut out by the incidence Plücker relations. We explore two natural extensions of this variety: First, we study the nonnegative flag variety, which corresponds to a subset of the flag variety consisting of flags that can be represented by totally positive matrices. Second, we study the tropicalization of the flag variety and, more specifically, its nonnegative part. In both cases, we provide equivalent descriptions of these spaces for flag varieties of rank $r=(a,a+1,...,b)$, where $r$ consists of consecutive integers. In the former case, we give a condition in terms of nonnegativity of the multi-projective coordinates. In the latter, we identify the nonnegative tropical flag variety with the nonnegative flag Dressian, even though the tropical flag variety and the flag Dressian differ in general. We also explore descriptions of the nonnegative tropical flag variety in terms of polytopal subdivisions. The supports of points in the nonnegative flag Dressian give a natural notion of a flag positroid. Once again restricting to the consecutive rank case, we give a combinatorial description of flag positroids.

This talk is partially based on joint work with Chris Eur and Lauren Williams.

Enumerative and analytic combinatorics
Thursday October 13, 2022, 12AM, Salle 3052 et zoom
Jiyang “johnny” Gao (Harvard) Balanced Shifted Tableaux

We introduce balanced shifted tableaux, as an analogue of balanced tableaux of Edelman and Greene, from the perspective of root systems of type B and C. We show that they are equinumerous to standard Young tableaux of the corresponding shifted shape by presenting an explicit bijection.

Enumerative and analytic combinatorics
Thursday October 13, 2022, 2PM, Salle 3052 et zoom
Groupe De Lecture - Viviane Pons (LISN) Tamari lattice and Weak order

We present the relation between the weak order / permutohedra on one hand and the Tamari lattice / associahedra on the other hand. In particular, we show how the Tamari lattice can be constructed as a sub lattice and a quotient lattice of the weak order. Finally, we present how this relates to Tamari intervals.

Enumerative and analytic combinatorics
Thursday October 6, 2022, 2PM, IHP
Seminaire Flajolet Jehanne Dousse, Nicolas Bonichon, Thierry Levy

https://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Thursday September 29, 2022, 2PM, Salle 3052
Houcine Ben Dali (IECL (Université de Lorraine), IRIF (Université de Paris)) Integrality in the matching-Jack conjecture

Using Jack polynomials, Goulden and Jackson have introduced a one parameter deformation $τ_b$ of the generating series of bipartite maps. The Matching-Jack conjecture suggests that the coefficients $c^λ_{µ,ν}$ of the function $τ_b$ in the power-sum basis are non-negative integer polynomials in the deformation parameter $b$. Dołega and Féray have proved in 2016 the “polynomiality” part in the Matching-Jack conjecture. In this talk I present a proof for the “integrality” part.

The proof is based on a recent work in which I obtain the Matching-Jack conjecture for marginal sums $c^λ_{µ,m}$ from an analog result for the $b$-conjecture, established in 2020 by Chapuy and Dołega. Jack polynomials orthogonality gives a linear system relating the coefficients $c^λ_{µ,ν}$ to the marginal coefficients $c^λ_{µ,m}$. Using a graded version of the Farahat-Higman algebra we prove that this system is invertible in $\mathbb{Z}$.

Enumerative and analytic combinatorics
Thursday September 22, 2022, 2PM, Salle 3052 et zoom
Groupe De Lecture - Intervalles De Tamari Corentin Henriet et Matthieu Josuat-Verges

Enumerative and analytic combinatorics
Thursday September 15, 2022, 2PM, Salle 3052 et zoom
Doriann Albertin (LIGM, Université Gustave Eiffel) The canonical complex of the weak order

The canonical join complex of a join-semidistributive lattice L is a simplicial complex whose faces are in bijection with the elements of L and record the canonical join representations in L. We introduce the canonical complex of a semidistributive lattice L, another simplicial complex containing both the canonical join and meet complexes, and whose faces are in bijection with intervals of L. Like the canonical join complex, the canonical complex is flag, and behaves well with quotients of L. In 2015, N. Reading introduced the non-crossing complex, a combinatorial model for the canonical join complex of the right weak order on permutations. Its faces are described with non-crossing arc diagrams. We focus in this talk on the example of the weak order, and extend this combinatorial model to a description of the canonical complex of the weak order, the semi-crossing complex, and its faces, the semi-crossing arc bidiagrams. This allows us to compute a generalization of the Kreweras complement on non-crossing partitions to all quotients of the weak order.

Enumerative and analytic combinatorics
Thursday September 8, 2022, 2PM, Salle 3052 et zoom
Khaydar Nurligareev (LIPN Paris Nord) Asymptotic probability of irreducible labeled objects in terms of virtual species

There are various combinatorial structures that admit a notion of irreducibility in a broad sense, including connected graphs, irreducible tournaments, indecomposable permutations and different models of connected surfaces. We are interested in the probability that a random labeled object is irreducible, as its size tends to infinity. The aim of this talk is to show that, in certain cases, the asymptotics for this probability can be obtained in a common manner and the asymptotic coefficients have a combinatorial meaning naturally expressed in terms of virtual species. Moreover, we will explain how to get the asymptotic probability that a random labeled object has a given number of irreducible parts, and we will indicate the combinatorial meaning of the coefficients involved in the corresponding asymptotic expansions. This is a joint work with Thierry Monteil.

Enumerative and analytic combinatorics
Thursday June 30, 2022, 2PM, Salle 1007
Lucia Rossi (Graz) Limit words for $N$-continued fractions

Given $N\geq 1$ and $x \in [0, 1]\backslash \mathbb{Q}$, an $N$-continued fraction expansion of $x$ is defined analogously as the classical continued fraction, but with the numerators being all equal to $N$. We introduce two infinite words $\omega(x, N )$ and $\hat\omega(x, N )$ on a two letter alphabet, which are related to the $N$-continued fraction expansion of $x$ and are obtained as a limit word of a sequence of substitutions. We call them $N$-continued fraction words. When $N=1$, we are in the classical case and find a Sturmian word. We show that these words are $C$-balanced for some explicit values of $C$, and we compute the factor complexity function of both families of words. We relate this to the more general setting of limit words of non unimodular $S$-adic sequences.

This is joint work with Jörg Thuswaldner and Niels Langeveld.

Enumerative and analytic combinatorics
Thursday June 23, 2022, 2PM, Salle 3052 et zoom
Marc Noy (UPC) Counting 3-connected bipartite maps

We provide a solution to the problem of counting rooted 3-connected bipartite planar maps. Our starting point is the enumeration of bicoloured planar maps according to the number of edges and monochromatic edges (Bernardi and Bousquet-Mélou 2011). The decomposition of a map into 2- and 3-connected components allows us to obtain the generating functions of 2- and 3-connected bicoloured maps. Setting to zero the variable marking monochromatic edges we obtain the generating function of 3-connected bipartite maps, which is algebraic of degree 26, from which we deduce from an asymptotic estimate. This is joint work with Clément Requilé and Juanjo Rué.

Enumerative and analytic combinatorics
Thursday June 16, 2022, 2PM, Salle 3052 et zoom
Sandrine Brasseur (Université Catholique de Louvain) The eight-vertex model and combinatorics

We are interested in the eight-vertex (8V) model, an integrable 2D lattice model. We consider a particular sub-family of its parameters, the “supersymmetric” or “combinatorial line”, dubbed so due to its surprising links to enumerative combinatorics.

Our goal, in this talk, is to provide evidence of the fascinating interplay between the 8V model and combinatorial structures, such as alternating sign matrices, plane partitions, 3-colorings,…

To do so, we investigate the row-to-row transfer matrix of the model. For an odd number of columns and horizontal periodic boundary conditions, its largest eigenvalue has been shown to have a remarkably simple expression. Moreover, the associated eigenvector is a key ingredient in the computation of 8V partition functions.

Ultimately, we obtain exact expressions for some components of this eigenvector and 8V partition functions in terms of symmetric polynomials introduced by Rosengren and Zinn-Justin. We then expose the links between our results and the aforementioned combinatorial structures.

This talk is based on joint work with Christian Hagendorf (arXiv:2009.14077 [math-ph]).

Enumerative and analytic combinatorics
Thursday June 9, 2022, 2PM, Salle 3052 et zoom
David Keating (University of Wisconsin) k-tilings of the Aztec diamond

We will study $k$-tilings ($k$-tuples of domino tilings) of the Aztec diamond. We assign a weight to each $k$-tiling, depending on the number of ``interactions“ between the dominos of the different tilings. We will compute the generating polynomials of the $k$-tilings by showing that they can be seen as the partition function of an integrable colored vertex model. These partition functions are related to the LLT polynomials of Lascoux, Leclerc, and Thibon. We will then prove some combinatorial results about $k$-tilings in certain limits of the interaction strength.

Enumerative and analytic combinatorics
Thursday June 2, 2022, 11AM, IHP
Seminaire Flajolet Seminaire Flajolet

Enumerative and analytic combinatorics
Thursday May 19, 2022, 2PM, Salle 3052 et zoom
Valentin Bonzom Hiérarchie intégrable BKP et applications aux cartes non-orientées

Plusieurs familles de cartes comme les triangulations et les cartes biparties comptées par taille et genre admettent des formules de récurrence remarquablement simples qui permettent de générer ces nombres efficacement. De manière intrigante, on ne sait prouver ces récurrences que par des équations issues des systèmes intégrables appelées hiérarchie KP. Dans cet exposé, j'expliquerai en termes de développement sur les fonctions de Schur ce que signifie pour une série génératrice de satisfaire la hiérarchie KP, et je donnerai plusieurs manières de la prouver dans le cas bien connu des factorisations de permutations (qui correspond également aux constellations et aux nombres de Hurwitz pondérés). Je présenterai le défi du passage aux modèles de cartes non-orientées par une tension entre développement sur les fonctions de Schur et sur les polynomes zonaux et j'évoquerai le problème connexe de la b-conjecture de Goulden et Jackson. Enfin je montrerai comment nous avons pu prouver une hiérarchie intégrable dans un cas assez résistant aux méthodes établies, celui de la série génératrice des nombres de Hurwitz monotones non-orientés. Ce sont des travaux en collaboration avec Guillaume Chapuy et Maciej Dolega.

https://cnrs.zoom.us/j/94236281873?pwd=LzIyV3F5Q0JtVzN4ZU0waW84M0pVUT09

Enumerative and analytic combinatorics
Friday May 13, 2022, 2:30PM, Salle 3052 et zoom
Christophe Reutenauer (UQAM, Canada) Le monoïde stylique (seminaire joint Combinatoire et Automates)

Le monoïde stylique Styl(A) est un quotient fini du monoïde plaxique de Lascoux et Schützenberger. Il est obtenu par l'action naturelle (insertion de Schensted à gauche) du monoïde libre A* sur l'ensemble des (tableaux) colonnes sur A. Il est en bijection avec un ensemble de tableaux semi-standards particuliers, appelés N-tableaux; la bijection consiste en une variante de l'algorithme de Schensted. On en déduit une bijection avec les partitions (ensemblistes) des sous-ensembles de A, et la cardinalté de Styl(A) est le nombre de Bell B_{n+1}, n=|A|. Une présentation de ce monoïde est obtenue en ajoutant aux relations de Knuth les relations d'idempotence a^2=a, pour chaque générateur a dans A. L'involution naturelle de A*, qui retourne les mots et renverse l'ordre de l'alphabet, induit un anti-automorphisme de Styl(A); il se calcule directement sur les N-tableaux par une variante de l'évacuation de Schützenberger. Le monoïde stylique apparaît comme le monoïde syntaxique de la fonction qui à un mot associe la longueur de son plus long sous-mot décroissant.

https://u-paris.zoom.us/j/84811442271?pwd=cCtvOVc5dXZFaUErbEpyR2pNUlRCUT09

Enumerative and analytic combinatorics
Thursday May 12, 2022, 2PM, Salle 3052 et zoom
Baptiste Rognerud (IMJ-PRG) Les matrices de Coxeter des ensembles ordonnés de Tamari sont périodiques

La matrice de Coxeter d'un ensemble ordonné fini est une matrice définie combinatoirement à l'aide de sa matrice d'incidence. Au début des années 2000, Chapoton a remarqué que les matrices de Coxeter de certains ensembles ordonnés remarquables sont périodiques. Il démontre, en utilisant la théorie des opérades, que c'est le cas des ensembles de Tamari et il conjecture que c'est le fantôme d'une propriété plus forte liée à la théorie des représentations de ces ensembles ordonnés. Dans cet exposé, j'expliquerai comment la démonstration de cette conjecture permet aussi d'obtenir une démonstration `presque combinatoire' de la propriété périodique des matrices de Coxeter de ces ensembles. https://cnrs.zoom.us/j/94236281873?pwd=LzIyV3F5Q0JtVzN4ZU0waW84M0pVUT09

Enumerative and analytic combinatorics
Thursday April 21, 2022, 2PM, Salle 3052
Jessica Mulpas (Université Libre de Bruxelles) String C-group representations of some almost simple groups

Abstract polytopes are a combinatorial abstraction of convex polytopes. When an abstract polytope is regular, that is when it is rich in symmetries (in a sense we will formalize), one can associate it with a presentation of its automorphism group with involutory generators called 'string C-group representation'.

We present an algorithm to classify string C-group representations of finite groups. This algorithm enabled us to compute all string C-group representations for previously unattainable sporadic groups as well as to complete the classification for the O'Nan group.

If time allows, we'll talk about some ways to obtain a string C-group representation for a given group from another by altering its rank (i.e. its number of involutory generators).

https://u-paris.zoom.us/j/82996433359?pwd=YkJNTEFaRDE1QjMzUXp1a1poL1FRUT09

Enumerative and analytic combinatorics
Thursday April 14, 2022, 2PM, Salle 3052
Alessandro Iraci (UQAM) Delta and Theta operators expansions

Delta and Theta operators are two families of operators on symmetric functions that show remarkable combinatorial properties. Delta operators generalise the famous nabla operator by Bergeron and Garsia, and have been used to state the Delta conjecture, an extension of the famous shuffle theorem proved by Carlsson and Mellit. Theta operators have been introduced in order to state a compositional version of the Delta conjecture, with the idea, later proved successful, that this would have led to a proof via the Carlsson-Mellit Dyck path algebra. We are going to give an explicit expansion of certain instances of Delta and Theta operators when t=1 in terms of what we call gamma Dyck paths, generalising several results including the Delta conjecture itself, using interesting combinatorial properties of the forgotten basis of the symmetric functions.

Enumerative and analytic combinatorics
Thursday April 7, 2022, 2PM, Salle 3052
Ariane Carrance (CMAP) À la recherche du trisp brownien

À quoi ressemble la structure fondamentale de notre espace-temps ? Dans cet exposé, une piste de réponse possible à cette question nous amènera à nous intéresser à des modèles aléatoires sur une famille particulière de complexes cellulaires, les trisps colorés.

Enumerative and analytic combinatorics
Thursday March 31, 2022, 11AM, IHP
Seminaire Flajolet Philippe Biane, Sylvie Corteel, Marie Theret

http://semflajolet.math.cnrs.fr/index.php/Main/HomePage

Enumerative and analytic combinatorics
Thursday March 17, 2022, 2PM, Salle 1007
Pooneh Afshari Joo Identités de partitions des nombres entiers à travers l’Algèbre commutative

Nous allons etudier les identites de partitions en utilisant la relation entre les series generatrices des partitions et les series de Hilbert-Poincare des algebres graduees associees a un objet important de la geometrie algebrique : l’espace des arcs. En utilisant des ideaux differentiels, nous donnons deux nouveaux membres des identites de Rogers-Ramanujan. Ensuite, nous enoncons un theoreme qui nous mene a une nouvelle version des identites de Golnitz-Gordon. Un corollaire de ce theoreme nous donne une identite entre les overpartitons. Enfin, nous presentons un nouveau membre des identites de Gordon.

Enumerative and analytic combinatorics
Thursday March 10, 2022, 2PM, Salle 1007
Dan Betea (Université d'Angers) From Gumbel to Tracy–Widom via random (ordinary, plane, and cylindric plane) partitions

We present a few natural (and combinatorial) measures on partitions, plane partitions, and cylindric plane partitions. We show how the extremal statistics of such measures, i.e. the distributions of the largest parts of the respective random objects, interpolate between the Gumbel distribution of classical statistics and the Tracy–Widom GUE distribution of random matrix theory, and do so in more than one way. These laws usually appear in opposite probabilistic contexts: the former distribution (Gumbel) appears universally in the study of extrema of iid random variables, the latter (Tracy–Widom) appears in the extrema of correlated systems (e.g. for the largest eigenvalue of random Hermitian matrices). All statistics also have a last passage percolation interpretation via the Robinson–Schensted–Knuth correspondence. Proofs rely on an interplay between algebraic combinatorics, mathematical physics, and complex analysis. The results are based on joint works with Jérémie Bouttier and Alessandra Occelli.

Enumerative and analytic combinatorics
Thursday February 24, 2022, 2PM, Salle 3052 et sur zoom
Elba Garcia-Failde (IMJ-PRG Sorbonne Universite) Une dualité triple : symplectique, simple et libre

Dans cet exposé, je présenterai trois transformations qui apparaissent dans des contextes très différents : des cartes combinatoires qui se simplifient, des cumulants qui se libèrent, et des x et y qui s’échangent symplectiquement dans la récurrence topologique. J'expliquerai comment réaliser toutes ces dualités par le biais d’une transformation universelle qui utilise les nombres de Hurwitz monotones doubles. Exprimer la transformation comme l’action d'un opérateur dans l'espace de Fock nous permet d'utiliser les techniques récentes développées par Bychkov, Dunin-Barkowski, Kazarian et Shadrin pour trouver des relations fonctionnelles reliant les séries génératrices des moments d'ordre supérieur et des cumulants libres, ce qui résout un problème ouvert posé par Collins, Mingo, Sniady et Speicher lors du développement de la théorie de second ordre qui généralise la transformée R de Voiculescu. Cela nous conduit à une théorie générale de la liberté qui prend en compte les corrections de genre supérieur qui apparaissent naturellement dans les deux autres contextes. Nous introduisons une notion de cumulants libres surfaciques à partir de la combinatoire du poset de permutations surfaciques (une généralisation des permutations partitionnées) qui capture les développements asymptotiques de tout ordre dans les modèles de matrices aléatoires avec invariance unitaire.

Basé sur un travail en commun avec Gaëtan Borot, Severin Charbonnier, Felix Leid et Sergey Shadrin.

Enumerative and analytic combinatorics
Thursday February 17, 2022, 2PM, Salle 3052 et sur zoom
Anna Vanden Wyngaerd (IRIF) Tiered tiers, polyominoes and Theta operators.

In [Dugan-Glennon-Gunnells-Steingrimsson-2019], the authors introduce tiered trees to define combinatorial objects counting absolutely indecomposable representations of certain quivers, and torus orbits on certain homogeneous varieties. In our work, we use Theta operators, introduced in [D'Adderio-Iraci-VandenWyngaerd-Theta-2021], to give a symmetric function formula that enumerates these trees. We then formulate a general conjecture that extends this result, a special case of which might give some insight about how to formulate a unified Delta conjecture [Haglund-Remmel-Wilson-2018].

Joint work with Michele D'Adderio, Alessandro Iraci, Yvan LeBorgne and Marino Romero.

https://cnrs.zoom.us/j/94236281873?pwd=LzIyV3F5Q0JtVzN4ZU0waW84M0pVUT09

Enumerative and analytic combinatorics
Thursday February 10, 2022, 2PM, Salle 1007
Daniel Tamayo Permutree Sorting

We define permutree sorting which generalizes the stack sorting and Coxeter sorting algorithms respectively due to Knuth and Reading. Given two disjoint subsets U and D of {2,…,n}, it consists of an algorithm that fails for a permutation if and only if there are integers i<j<k in [n] such that the permutation contains the pattern jki (resp. kij) if j is in U (resp. in D). We present this algorithm through automata that read reduced expressions and accept only those that form a specific structure within the weak order. This is joint work with Vincent Pilaud and Viviane Pons.

Enumerative and analytic combinatorics
Wednesday February 9, 2022, 2PM, Salle 3052 et sur zoom
Journées De L'anr Combiné Anna Van Den Wyngaerd, David Wahiche, Corentin Henriet, Philippe Nadeau

[14h-14h30] Tiered tiers, polyominoes and Theta operators. [14h30] Théorèmes de multiplication pour les partitions auto-conjuguées. [15h] Des poissons combattants pour une formule sur la distance dans le treillis de Tamari. [15h30] Algorithme de parking, polynômes quasisymétriques et calcul de Schubert.

https://anr-combine.math.cnrs.fr/event-un.html

Enumerative and analytic combinatorics
Tuesday February 8, 2022, 2PM, Salle 3052 et sur zoom
Journées De L'anr Combiné Andrea Sportiello, Joonas Turunen et Jehanne Dousse

[14h] Many new conjectures on Fully-Packed Loop configurations. [14h45] Joonas Turunen - Combinatorial aspects of random planar triangulations of the disk coupled with an Ising model. [15h15] Partitions cylindriques et identités du type Rogers-Ramanujan.

https://anr-combine.math.cnrs.fr/event-un.html

Enumerative and analytic combinatorics
Thursday February 3, 2022, 2PM, IHP Amphi Darboux
Seminaire Flajolet Jiang Zeng et Marie Albenque

http://semflajolet.math.cnrs.fr/index.php/Main/HomePage

Enumerative and analytic combinatorics
Thursday January 20, 2022, 2PM, Salle 3052 et sur zoom
Noémie Cartier (Université de Paris-Saclay) Lattice properties of acyclic pipe dreams

A pipe dream is a collection of pipes that trace the values of a permutation when passing through a sorting network. By choosing the sorting network and the permutation carefully, the set of reduced pipe dreams gives a realization of the Tamari lattice, a famous lattice quotient of the weak order. The talk will present a generalization of this result: if our sorting network respects a few specific properties, the set of reduced and acyclic pipe dreams of a permutation is a lattice quotient of an interval of the weak order.

https://cnrs.zoom.us/j/94236281873?pwd=LzIyV3F5Q0JtVzN4ZU0waW84M0pVUT09

Enumerative and analytic combinatorics
Thursday January 13, 2022, 2PM, Salle 3052 et sur zoom
Eva Philippe Sweep polytopes and sweep oriented matroids

Consider a configuration of n labeled points in a Euclidean space. Any linear functional gives an ordering of these points: an ordered partition that we call a sweep, because we can imagine its parts as the sets of points successively hit by a sweeping hyperplane. The set of all such sweeps forms a poset which is isomorphic to a polytope, called the sweep polytope. I will present several constructions of the sweep polytope, related to zonotopes, projections of permutahedra and monotone path polytopes of zonotopes.

In a second part, I will present an abstract generalization of this structure in terms of oriented matroids.

This is joint work with Arnau Padrol.

https://cnrs.zoom.us/j/94236281873?pwd=LzIyV3F5Q0JtVzN4ZU0waW84M0pVUT09

Year 2021

Enumerative and analytic combinatorics
Thursday December 16, 2021, 2PM, Salle 1007
Corentin Henriet (IRIF - Université de Paris) Combinatoire des poissons combattants et bijection avec les cartes planaires et les intervalles de Tamari

Dans cet exposé, je présenterai une nouvelle décomposition des cartes planaires enracinées, qui permet de prouver une bijection avec des poissons combattants généralisés qui sont des chemins sur le réseau carré généralisant les poissons combattants introduits en 2016 par Duchi et al. Cette décomposition a la propriété sympathique de se réduire naturellement à la classe des cartes planaires sans boucles, et cette sous-décomposition est isomorphe à une décomposition connue des intervalles du treillis de Tamari. Grâce à l'interprétation de cette décomposition pour une nouvelle classe de poissons, nous pourrons donner une formule nouvelle pour la distance dans le treillis de Tamari. Basé sur un travail en cours avec Enrica Duchi.

Enumerative and analytic combinatorics
Thursday December 9, 2021, 2PM, Salle 1007
Harriet Walsh (IRIF, Université de Paris) Counting maps with random partitions

Hurwitz numbers count ramified coverings of the complex projective line, and a particular family of maps. They can also be interpreted as partition functions for random integer partitions under deformations of the Plancherel measure. The same measures were studied by Diaconis and Shahshahani in the context of random walks on the symmetric group, and were related to tau-functions of the Toda lattice integrable hierarchy by Okounkov. We study these measures in new regimes, finding limit shapes of large random partitions and approximate asymptotics of unconnected Hurwitz numbers. From the corresponding model of random unconnected maps, we consider the asymptotic enumeration of high genus connected maps. Based on ongoing joint work with Guillaume Chapuy and Baptiste Louf.

Enumerative and analytic combinatorics
Thursday December 2, 2021, 2PM, Salle 1007
Ariane Carrance (CMAP, Ecole Polytechnique) Énumération de nouvelles conditions de bord pour les cartes bicolorées

Les cartes bicolorées à bord apparaissent dans de nombreux contextes : elles sont notamment un cas particulier du modèle d'Ising. Ainsi, dans le cas d'un bord monochromatique, très naturel pour le modèle d'Ising, les cartes bicolorées ont été énumérées par plusieurs méthodes, tant analytiques que bijectives. Cependant, pour l'étude de modèles de cartes aléatoires, il est plus naturel de considérer d'autres conditions de bord, comme la condition dite alternante. Dans cet exposé, je présenterai les résultats et les principaux arguments d'un travail en commun avec Jérémie Bouttier, où nous utilisons des outils de combinatoire analytique pour énumérer les cartes bicolorées à bord alternant. Les résultats intermédiaires que je présenterai feront aussi apparaître d'autres motivations pour s'intéresser à ces conditions de bord.

Enumerative and analytic combinatorics
Thursday November 25, 2021, 11AM, IHP
Séminaire Flajolet Maria Chlouveraki, Reza Naserasr, Andrea Sportiello

11h00 - 12h00 : Maria Chlouveraki (UVSQ)

  Le défaut et le poids des multipartitions

14h00 - 15h00 : Reza Naserasr (IRIF),

  Signed projective cubes

15h00 - 16h00 : Andrea Sportiello (LIPN),

  Many new conjectures on Fully-Packed Loop configurations

Les résumés sont disponibles sur la page web http://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Thursday November 18, 2021, 2PM, Salle 1007
Rado Rakotonarivo (IRIF) On the number of (d,k)-polytopes

This talk will be about two computational methods that output the exact number of lattice polytopes of R^d that are contained in the [0,k]^d hypercube, denoted (d,k)-polytopes. Recall that a convex polytope is the convex hull of a finite set of points in an euclidean space; and a lattice polytope is a polytope whose vertices have integer coordinates.

The question is: for fixed values of d and k, how many different (d,k)-polytopes one can have? In order to answer to this question, I will describe two different methods that output the exact number of (d,k)-polytopes: when k = 1 and when k >= 2.

The first method can be described as follow: first compute all the polytopes contained in the unit cube that are not full-dimensional, then substract their number from the total number of subsets of vertices of the unit cube. Using this method we reach the exact number of (d,1)-polytopes up to dimension 6 (a computation that was believed to be out of reach). The second method is an iterative computation based on a local operation performed on a lattice polytope: first exhaustively generate all the d-simplices contained in [0,k]^d, then each (d,k)-polytope of d+2 vertices is obtained in a unique way by adding a single vertice to a d-simplex. In turn, each (d,k)-polytope of d+3 vertices is is obtained in an unique manner by adding a single vertice to a (d,k)-polytope of d+2 vertices. We repeat this procedure until all the (d,k)-polytopes are all computed.

Work in progress with Lionel Pournin (Université Sorbonne Paris Nord) and Julien David (Université de Caen Normandie).

Enumerative and analytic combinatorics
Thursday November 4, 2021, 2PM, Salle 1007
Matthieu Josuat-Verges Et Berenice Delcroix-Oger (IRIF) Journees du GDR-IM Combalg

4 et 5 Novembre a Strasbourg https://irma.math.unistra.fr/~guoniu/journee2021.html

Enumerative and analytic combinatorics
Thursday October 21, 2021, 2PM, Salle 1007
Florent Koechlin (IRIF, Université de Paris) Séries génératrices et preuves d'intrinsèque ambiguïté

Un langage algébrique est intrinsèquement ambigu si toute grammaire qui le reconnaît est ambiguë, c'est-à-dire qu'elle génère un même mot de deux façons différentes. Décider l'intrinsèque ambiguïté d'un langage algébrique est un problème difficile, indécidable en général. Dans les années 70-80, les preuves d'intrinsèque ambiguïté reposaient essentiellement sur des raisonnements subtils et difficiles sur les arbres de dérivation des grammaires. En 1987, Philippe Flajolet a proposé une nouvelle approche pour montrer que certains langages algébriques sont intrinsèquement ambigus, en montrant que leur série génératrice n'est pas algébrique. Cette approche s'est avérée très efficace : en utilisant cette méthode, Philippe Flajolet a démontré ou redémontré dans son article l'intrinsèque ambiguïté d'une dizaine de langages, dont plusieurs étaient des conjectures de son époque. Dans cet exposé, je propose quelques extensions qui étendent le lien entre la non-ambiguïté des langages et les séries génératrices, et apportent notamment quelques pistes de réponses à deux questions posées par Philippe Flajolet à la fin de son article.

Enumerative and analytic combinatorics
Thursday October 14, 2021, 2PM, Salle 1007
Elie De Panafieu Algorithmes de partitionnement par comparaison de paires

On cherche à reconstruire une partition d'un ensemble donné en envoyant des paires d'éléments à un oracle qui nous indique s'ils appartiennent à la même partie de la partition. Nous cherchons les algorithmes qui retrouvent la partition en un minimum de questions à l'oracle. Ce problème est similaire au problème classique du tri : on reconstruit une partition au lieu d'une permutation. Dans le cas où la partition est tirée aléatoirement uniformément parmi celles d'une taille donnée, nous caractérisons les algorithmes de complexité moyenne optimale, prouvons qu'ils partagent la même distribution sur le nombre de questions et analysons cette distribution. Nous étudions également un modèle de partitions aléatoires où chaque élément choisit sa partie indépendamment suivant la même loi de support fini. Ce travail est motivé par l'annotation de données d'entraînement par des experts humains pour l'apprentissage supervisé.

Travail en cours avec Quentin Lutz (Nokia Bell Labs), Maya Stein (Université du Chili) et Alex Scott (université d'Oxford)

Enumerative and analytic combinatorics
Thursday October 7, 2021, 2PM, Salle 1007
Anna Vanden Wyngaerd (IRIF) Two Delta conjecture implications

The famous shuffle theorem is a combinatorial formula for a Schur positive symmetric function, nabla(e_n). Since its formulation, a number of variations and generalisations of the shuffle formula have been proposed, many of which remain open problems today. In this talk we present some of these conjectures and discuss two logical implications between them we recently established (joined work with Alessandro Iraci). The relevant combinatorial objects are decorated labelled lattice paths.

Enumerative and analytic combinatorics
Thursday September 30, 2021, 10:30AM, IHP
Seminaire Flajolet (IHP) Valentin Feray, Marc Lelarge, Irene Marcovici
http://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Thursday September 23, 2021, 2PM, Salle 1007
Séverin Charbonnier (IRIF) Weighted enumeration of ciliated maps and applications

Some models of ribbon graphs can be interpreted as Feynman graphs of matrix models. In this manner, the graphs used by Kontsevich in his proof of Witten's conjecture – about the generating function of intersection numbers of psi-classes satisfying the KdV hierarchy – are Feynman graphs of a cubic hermitian matrix model with external field. Ciliated maps arise as generalisations of those graphs.

I will first describe the ciliated maps and their weighted enumeration. Second, I will detail Tutte's equation and state how the generating functions are computed via topological recursion. Last, I will discuss applications of this result to intersection theory of Witten's class, to the enumeration of fully simple maps and to free probabilities.

In collaboration with Raphaël Belliard, Gaëtan Borot, Bertrand Eynard and Elba Garcia-Failde.

Enumerative and analytic combinatorics
Thursday September 16, 2021, 2PM, Salle 1007
Etienne Bellin (École polytechnique) Factorisations minimales de cycles

Une factorisation minimale est une factorisation du n-cycle (1 2 … n) en produit de n-1 transpositions. Nous verrons comment construire une bijection de l'ensemble des factorisations minimales vers l'ensemble des arbres de Cayley à n sommets. Une application de cette bijection sera présentée ce qui mènera à l'étude de certaines fonctions génératrices multivariées. Les factorisations minimales sont liées à d'autres objets combinatoires tels que les fonctions de parking ou les partitions non croisées.

Enumerative and analytic combinatorics
Wednesday March 31, 2021, 10:30AM, Virtuelle
Samuele Giraudo (Université Gustave Eiffel) Some combinatorial aspects of combinatory logic Quelques aspects combinatoires de la logique combinatoire

La logique combinatoire est un formalisme introduit par Schönfinkel dans les années 1920 dans le but de supprimer la nécessité des variables dans les expressions. Ce formalisme donne également lieu à un modèle de calcul très proche du $\lambda$-calcul basé sur la réécriture de termes et donc sur la réécriture d'arbres. Malgré son nom, ce domaine a été assez peu étudié d'un point de vue combinatoire. Je propose donc dans cet exposé d'approcher ainsi quelques systèmes de logique combinatoire. L'exposé commencera par des rappels généraux sur les systèmes de réécriture de termes. Je vais ensuite parler de logique combinatoire et lister quelques questions qui me motivent dans ce contexte. Je terminerai par une première étude (encore en cours) d'un nouveau treillis qui émerge naturellement de l'un de ces systèmes.

Enumerative and analytic combinatorics
Thursday March 11, 2021, 2PM, https://bbb.lri.fr/b/jer-k22-eqk
Franz Lehner (TU Graz) Sommes de cotangentes

Les sommes des puissances de la cotangente de la sorte ∑cot(mα+kπn) pour k de 0 à n-1 apparaissent dans diverses domaines, dont théorie des nombres, topologie et récemment dans l'étude d'un théorème limite central des commutateurs des matrices aléatoires. On donne une évaluation explicite de ces sommes à l'aide de la méthode de la trace et il en résulte des polynômes à coéfficients positifs à valeurs entières dont l'interprétation combinatoire reste a découvrir. Travail en collaboration avec W. Ejsmont.

Enumerative and analytic combinatorics
Thursday February 18, 2021, 10:30AM, Virtruelle
Samuele Giraudo (Université Gustave Eiffel) Rewrite systems on free clones and realizations of algebraic structures

Some interactions between combinatorics and universal algebra through rewrite systems and clone theory are presented. Given a variety $V$ of algebras (presented by generating operations and relations between some of their compositions), a natural question consists in building a combinatorial realization of $V$. This consists in encoding the operations of $V$ in such a way that two equivalent ones have the same representation, and in providing an algorithm to compute the representation of the functional composition of several operations. In particular, we present a class of clones obtained from monoids. This gives rise among other to realizations of varieties of various classes of semigroups (commutative, left/right-regular bands, semilattices, etc.).

Joint session with the PPS seminar.

Enumerative and analytic combinatorics
Wednesday January 27, 2021, 10:30AM, Virtuelle
Franz Lehner (TU Graz) To be announced.

Enumerative and analytic combinatorics
Thursday January 21, 2021, 2PM, Virtuelle
Oswin Aichholzer (TU Graz) Crossing Numbers of complete graphs for Geometric and Topological Drawings

In the area of crossing numbers we ask for minimizing the number of edge intersections in a drawing of a graph. There is a rich variety of crossing number problems: Which graphs do we consider, what exactly is a drawing of a graph and on which surface is it drawn, and how are intersections counted? In this talk we will concentrate on the crossing number of complete graphs drawn in the plane, including their rich history around Hill's conjecture.

We will have a look at geometric drawings (vertices are points in the plane and edges of the graph are straight line segments), and simple drawings (edges are simple Jordan arcs with at most one pairwise intersection), which are also called simple topological graphs. Our results ar based on a representation of the complete graph with order types (for geometric graphs) and rotation systems (for simple drawings). We will presen recent developements, as well as (old and new) open questions.

Enumerative and analytic combinatorics
Thursday January 14, 2021, 2PM, Virtuelle
Jean Fromentin (LMPA et Université du Littoral Côte d'Opale) Expérimentations sur les séries génératrices des groupes des tresses

Dans cet exposé, je présenterai de nouveaux outils algorithmiques pour étudier les séries génératrices sphériques et géodésiques des groupes des tresses relativement aux générateurs d'Artin ou de Birman-Ko-Lee. Je finirai par une présentation des résultats obtenus et par la formulation de conjectures pour les groupes des tresses à 3 et 4 brins relativement aux générateurs de Birman-Ko-Lee.

Year 2020

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.

Year 2019

Enumerative and analytic combinatorics
Thursday November 28, 2019, 11AM, IHP, Amphi Hermite
Tba Séminaire Flajolet

Enumerative and analytic combinatorics
Thursday November 21, 2019, 2PM, Salle 1007
Luis Fredes (Université Paris-sud) Bijections for tree-decorated maps and applications to random maps

In this talk, we introduce a new family of maps: the (not necessarily spanning) tree-decorated maps. To study this class of maps, we introduce a bijection which allows us to deduce combinatorial results, recovering as a corollary some results about spanning-tree decorated maps, and to understand local limits. Finally, we discuss the possible metric scaling limit of this map: the shocked map. We give certain properties and give the conjectured continuum construction. This is a work in progress with Avelio Sepúlveda.

Enumerative and analytic combinatorics
Thursday November 14, 2019, 2PM, Salle 1007
Wenjie Fang (Université Paris-Est Marne-la-Vallée) Arbres binaires compactés possède une exponentiel étiré

Un arbre binaire compacté est un graphe acyclique dirigé qui représente un arbre binaire de façon sans redondances, dans le sens que tous les sous-arbres isomorphes sont partagés. Nous montrons que le nombre des arbres binaires compactés de tailles n croît asymptotiquement en

\Theta(n! 4^n e^{3 a_1 n^{1/3}} n^{3/4}).

Ici, a_1 ≈ -2,338 est la plus grande racine de la fonction d'Airy. Ce résultat est obtenu à partir d'une nouvelle récurrence des nombres de ces arbres compactés, avec une nouvelle méthode qui, inspirée par des estimations empiriques suffissament précises, prouve des bonnes bornes par induction. Ce travail donne aussi des nouvelles bornes sur le nombre d'automates minimaux qui reconnaissent un langage fini d'un alphabet binaire, qui possède aussi un exponentiel étiré. Par sa simplicité, notre méthode s'applique potentiellement aux autres objets.

Enumerative and analytic combinatorics
Thursday November 7, 2019, 2PM, Salle 1007
Vonjy Rasendrahasina On the Sparse Random Acyclic Digraphs

In this talk, we consider the probability space of random digraphs defined as follow. We generate a random undirected graph by taking the classical Erdös-Rényi model G(n,p). Thereafter, each edge is given a direction, where each of the two directions has probability 1/2 and all choices are made independently. The result is a simple digraph on n vertices. We will study the the probability that a random digraph is acyclic when p = O(1/n), i.e. it does not contain a directed cycle when the number of edges is linear in the number of vertices. This is a joint work with Dimbinaina Ralaivaosaona and Stephan Wagner.

Enumerative and analytic combinatorics
Thursday October 17, 2019, 2PM, Salle 1007
Mark Skandera (Lehigh university) Non négativité et traces de l'algèbre de Hecke

La recherche de Gantmacher sur les matrices totalement non négatives dans les années 1930 - 1940 a influencé plusieurs domaines des mathématiques. Par exemple, nous avons les polynômes totalement non négatifs, ces polynômes en n^2 variables dont l'évaluation sur chaque matrice totalement non négative est un nombre non négatif. Ces polynômes sont liés à certaines traces de l'algèbre de Hecke dont les évaluations sur certaines éléments de la base de Kazhdan-Lusztig sont des polynômes dans N[q]. Dans tous les cas, il serait intéressant d'interpréter de manière combinatoire les entiers non négatifs qui apparaissent dans les évaluations. Nous verrons un nouveau résultat sur certaines traces qui améliore notre compréhension des polynômes non négatifs.

Ce travaille a été réalisé avec Adam Clearwater.

Enumerative and analytic combinatorics
Thursday October 10, 2019, 2PM, Salle 1007
Baptiste Louf (IRIF) Hiérarchies KP/2-Toda et cartes biparties

Les hiérarchies intégrables (des ensembles infinis d'EDPs en une infinité de variables) sont étudiées depuis longtemps en physique mathématique. De manière assez surprenante, la série génératrice des cartes est une solution des hiérarchies KP et 2-Toda (qui est une généralistation de la précédente), ce qui permet d'obtenir des formules de récurrences exactes et très simples sur les coefficients (Goulden—Jackson, Carrell—Chapuy, Kazarian—Zograf). Je décrirai un peu la théorie derrière la hiérarchie 2-Toda et la preuve que la série des cartes en est solution (qui implique entre autres, des fonctions symétriques), et je dériverai une formule permettant de compter les cartes biparties à degrés des faces prescrits.

Enumerative and analytic combinatorics
Thursday October 3, 2019, 11AM, IHP, Amphi Hermite
Éric Fusy, Brigitte Vallée, Omidi Amini Séminaire Flajolet

Voir http://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Thursday September 19, 2019, 2PM, Salle 1007
Philippe Biane (CNRS et Université Paris-Est Marne-la-Vallée) Partitions non-croisées et ordre de Bruhat

Les partitions non-croisées, dans un groupe de Coxeter fini, peuvent être définies à l'aide d'une relation d'ordre sur le groupe, l'ordre absolu. Cet ordre possède des relations remarquables avec l'ordre de Bruhat et avec les complexes d'amas, provenant de la théorie des algèbres amassées, que nous explorerons durant l'exposé. Travail en commun avec Matthieu Josuat-Vergès

Enumerative and analytic combinatorics
Thursday September 12, 2019, 2PM, Salle 1007
Matthieu Josuat-Vergès (CNRS et Université Paris-Est Marne-la-Vallée) Un poset de fonctions de parking

Edelman a défini dans un article de 1980 un poset sur ce qu'il appelle 2-partitions non-croisées. Ces objets sont en fait en bijection avec les fonctions de parking. On donnera quelques nouvelles propriétés de ce poset, d'une part sur des énumérations de chaînes, d'autre part sur la topologie du poset. Plus précisément, on démontre une propriété d'épluchabilité du poset. J'expliquerai les conséquence sur la topologie et l'homologie du poset, et on finira par quelques éventuelles généralisations. Il s'agit d'un travail en commun avec Bérénice Delcroix-Oger et Lucas Randazzo.

Enumerative and analytic combinatorics
Monday June 24, 2019, 11AM, Salle 3052
Carola Doerr (CNRS, LIP6 Sorbonne University) Evolutionary Algorithms – From Theory to Practice and Back

Most real-world optimization problems do not have an explicit problem formulation, but only allow to compute the quality of selected solution candidates. Solving such black-box optimization problems requires iterative procedures which use the feedback gained from previous evaluations to determine the strategy by which the next solution candidates are generated. Many black-box optimization algorithms, such as Simulated Annealing, Evolutionary Algorithms, Swarm Intelligence Algorithms, are randomized – making it very difficult to analyze their performances mathematically.

In the last 15 years, the theory of randomized black-box optimization has advanced considerably, and has contributed to efficient optimization by providing insights into the working principles of black-box optimization which are hard or impossible to obtain by empirical means. On the other hand, empirically-guided benchmarking has opened up new research directions for theoretical investigations.

In this presentation we will discuss the state of the art in the theory of randomized black-box optimization algorithms. As part of this critical survey we will also mention a number of open questions and connections to other fields of Computer Science.

Enumerative and analytic combinatorics
Thursday June 20, 2019, 11:45AM, Salle 1007
Vincent Jugé (Université Paris-Est Marne-la-Vallée) To be announced.

Enumerative and analytic combinatorics
Thursday June 13, 2019, 11:45AM, Salle 1007
Nathan Williams (University of Texas at Dallas) Reflexponents

Certain classical generating functions for elements of reflection groups can be expressed using fundamental invariants called exponents. We give new analogues of such generating functions that accommodate orbits of reflecting hyperplanes using similar invariants we call reflexponents. Our verifications are case-by-case.

Enumerative and analytic combinatorics
Thursday June 6, 2019, 11AM, IHP, salle 201
Cécile Mailler, Juanjo Rué, François Bergeron Séminaire Flajolet

Enumerative and analytic combinatorics
Thursday May 23, 2019, 11:45AM, Salle 1007
Cyril Banderier (LIPN (Paris 13)) Analytic combinatorics, urn models, and limit surface of random Young tableaux

Pólya urns are urns where at each unit of time a ball is drawn and, according to its colour, is then replaced with some other balls. We introduce a more general model: the replacement rule depends on the colour of the drawn ball and the value of the time (mod p). We extend the work of Flajolet et al. on Pólya urns: the generating function encoding the evolution of the urn is studied by methods of analytic combinatorics. We show that the initial partial differential equations lead to ordinary linear differential equations which are related to hypergeometric functions (giving the exact state of the urns at time n). When the time goes to infinity, we prove that these periodic Pólya urns have asymptotic fluctuations which are described by a product of generalized gamma distributions. With the additional help of what we call the density method (a method which offers access to enumeration and random generation of poset structures), we prove that the law of the south-east corner of a triangular Young tableau follows asymptotically a product of generalized gamma distributions. This allows us to tackle some questions related to the continuous limit of large random Young tableaux and links with random surfaces. Joint work with Philippe Marchal and Michael Wallner.

Enumerative and analytic combinatorics
Thursday April 18, 2019, 11:45AM, Salle 1007
Axel Bacher (LIPN (Paris 13)) Algorithmes de rattrapage pour la génération aléatoire de chemins

Cet exposé concerne la génération aléatoire de familles classiques de chemins (Dyck, Motzkin et Schröder et leurs préfixes). Le point de départ est l'algorithme florentin (Barcucci, Pinzani et Sprugnoli 1994+), qui utilise une méthode de rejet anticipé pour engendrer les préfixes. Je montrerai comment on peut raffiner cet algorithme en utilisant une fonction de « rattrapage » qui permet de fortement réduire, voire d'éliminer, la probabilité de rejet. Les algorithmes obtenus sont asymptotiquement optimaux en termes d'entropie utilisée et significativement plus rapides que les algorithmes florentins.

Enumerative and analytic combinatorics
Thursday April 11, 2019, 11:45AM, Salle 1007
Theodosios Douvropoulos (IRIF) Coxeter factorizations and the Matrix Tree theorem with generalized Jucys-Murphy weights

One of the most far reaching proofs of Cayley's result on the number of vertex-labeled trees is via Kirchhoff's Matrix Tree theorem, where the enumeration is reduced to the determinant calculation of the Laplacian L(K_n). After Denes, there is a now well-exploited correspondence between trees and minimal factorizations of long cycles (of S_n) in transpositions.

Many of the latter results have been transferred to the setting of (complex) reflection groups, which include S_n, and for which the long cycles are replaced by a Coxeter element c. Notably there is the Chapuy-Stump product formula for the generating function of arbitrary length reflection factorizations of c. At the same time, Burman and Zvonkine have given a different generalization of the Matrix Tree theorem, enumerating arbitrary length factorizations of long cycles, where each transposition (ij) is weighted by its own variable w_ij.

In joint work with Guillaume Chapuy, we consider a (partial) analog of the weighted Laplacian for complex reflection groups. The weights are specified via a flag of parabolic subgroups, generalizing the definition of Jucys-Murphy elements. We prove a product formula for the enumeration of weighted reflection factorizations of Coxeter elements, that subsumes the Chapuy-Stump formula and in part the Burman-Zvonkine formula.

Enumerative and analytic combinatorics
Friday April 5, 2019, 11AM, Salle 3052
Henri Mühle (Dresde) Parabolic Cataland – A Type-A Story

In this talk we embark on a journey through Parabolic Cataland. We first visit the various families inhabiting the currently explored part of Parabolic Cataland and study their interactions. We then introduce certain natural orders for each of these families and describe how these are related. We highlight certain beautiful structural and enumerative aspects of this story, specializations of which are well known from good old Cataland. In parts, this is joint work with Cesar Ceballos, Wenjie Fang and Nathan Williams

Horaire inhabituel

Enumerative and analytic combinatorics
Thursday April 4, 2019, 11AM, IHP, salle 201
Lionel Pournin, Victoria Lebed, Jérémie Bouttier Séminaire Flajolet

Enumerative and analytic combinatorics
Thursday March 14, 2019, 11:45AM, Salle 1007
Éric Fusy (LIX, école Polytechnique) Relations bijectives entre familles de chemins

Dans la combinatoire des chemins on observe fréquemment une équi-énumération entre (pour un même ensemble de pas et même longueur) une contrainte plus forte de domaine et une contrainte plus forte sur le point d'arrivée (un exemple classique en 1D est le fait que les chemins positifs de longueur 2n sont en bijection avec les ponts de longueur 2n). Nous montrerons que certaines telles relations pour des chemins 2D peuvent s'expliquer bijectivement en utilisant des cartes orientées telles que les Schnyder woods ou les orientations bipolaires.

Enumerative and analytic combinatorics
Thursday March 7, 2019, 11:45AM, Salle 1007
Christophe Cordero (Université Paris-Est Marne-la-Vallée) Une exploration de la conjecture du triangle

On dit qu'un code est commutativement préfixe s'il est équivalent à un code préfixe, lorsque que l'on autorise les lettres de ses éléments à commuter. Perrin et Schützenberger ont conjecturé qu'un code dont les éléments sont de la forme a^iba^j est commutativement préfixe ou non inclus dans un code maximal fini. Shor a trouvé en 1984 un code non commutativement préfixe dont les éléments sont de la forme a^iba^j. C'était le seul code de ce type que nous connaissions et nous ne savons toujours pas s'il est inclus ou non dans un code maximal fini. Nous verrons durant l'exposé d'autres codes de ce type que nous obtiendrons grâce à une exploration informatique. Nous discuterons de la possibilité qu'un de ces codes soit inclus dans un code maximal fini. En particulier, nous calculerons des bornes sur la taille des codes maximaux finis susceptibles de les contenir.

Enumerative and analytic combinatorics
Thursday February 28, 2019, 11:45AM, Salle 1007
Sylvie Hamel (Université de Montréal) Médiane de permutations: réduction d’espace et lien avec le 3-Hitting Set Problem

Le problème de la médiane d’un ensemble de permutations est un problème d’optimisation combinatoire qui consiste à trouver une permutation, appelée médiane, qui minimise la somme des distances de celle-ci aux permutations de l’ensemble. Dans cet exposé, c’est la distance de Kendall-tau qui sera utilisée. Cette distance compte le nombre de paires d’éléments dont l’ordre relatif est en désaccord entre deux permutations. Sous cette distance, le problème de la médiane a été démontré NP-difficile, même pour de petits ensembles ne contenant que 4 permutations. Je parlerai dans cet exposé de méthodes efficaces de réduction d’espace pour le problème général de même que d’un lien intéressant avec le 3-Hitting Set Problem dans le cas spécial où on s’intéresse à la médiane d’un ensemble 3 permutations. Les travaux présentés dans cet exposé ont été réalisés en collaboration avec Robin Milosz (Université de Montréal) et Adeline Pierrot (LRI, Université Paris-Sud).

Enumerative and analytic combinatorics
Tuesday February 19, 2019, 11AM, Salle 3052
Danupon Nanongkai (KTH) Distributed Shortest Paths, Exactly

This talk concerns the problem of quickly computing distances and shortest paths on distributed networks (the CONGEST model). There have been many developments for this problem in the last few year, resulting in tight approximation schemes. This left open whether exact algorithms can perform equally well. In this talk, we will discuss some recent progress in answering this question. Most recent works that this talk is based on are with Sebastian Krinninger (FOCS 2018) and Aaron Bernstein (ArXiv 2018).

Enumerative and analytic combinatorics
Thursday January 31, 2019, 11:45AM, Salle 1007
Alexander R. Miller (Université de Vienne) Orthogonal polynomials and Smith normal form

Several Smith normal form evaluations will be discussed. They include Hankel matrices of q-Catalan numbers, q-Motzkin numbers, q-Schröder numbers, q-Stirling numbers, q-matching numbers, q-factorials, and q-double factorials. Similar results will be given for Toeplitz matrices and Gram matrices, along with some open conjectures. This work is with Dennis Stanton.

Enumerative and analytic combinatorics
Thursday January 17, 2019, 11:45AM, Salle 1007
Philippe Nadeau (Institut Camille Jordan (Lyon)) La symétrisation divisée

La symétrisation divisée est un opérateur linéaire sur les polynômes multivariés. Il a été introduit pour exprimer le volume des permutoèdres généralisés, et apparaît également dans le contexte du calcul de Schubert pour la variété de drapeaux. Nous expliquerons ces termes et décrirons divers aspects combinatoires et algébriques de la symétrisation divisée, notamment son action sur diverses familles de polynômes. Travail en commun avec V. Tewari (UPenn)

Enumerative and analytic combinatorics
Thursday January 10, 2019, 11:45AM, Salle 1007
Pierre-Guy Plamondon (Université d'Orsay) Triangulations de surfaces, algèbres amassées et applications

Pour toute surface avec bord et points marqués, il est possible d'associer à chaque arc une variable, de sorte que les arcs se croisant respectent une certaine “relation de Ptolémée”. L'algèbre engendrée par ces éléments est un exemple d'algèbre amassée (“cluster algebra”) au sens de Fomin et Zelevinsky. Dans cet exposé, nous ferons un survol des applications de la combinatoire des triangulations de surfaces aux algèbres amassées, et terminerons par une idée de la démonstration de la conjecture d'unistructuralité pour ces algèbres amassées.

Year 2018

Enumerative and analytic combinatorics
Thursday December 20, 2018, 11:45AM, Salle 1007
Cyrille Chenavier (INRIA (Lille)) Quotients of the magmatic operad: lattice structures and convergent rewrite systems

In this talk, we study quotients of the magmatic operad, that is the free nonsymmetric operad generated by one binary generator. We equip the set of these quotients with a lattice structure, defined in terms of operad morphisms, and provide an analog of the Grassmann formula for the dimensions of these operads. We study a subset of this lattice, formed by operads that we call comb associative operads. The latter are not stable for the lattice operations of magmatic quotients, however, we define new operations making comb associative operads a lattice, isomorphic to the lattice of integers, equipped with the division relation and gcd, lcm operations. Finally, we study the existence of a finite convergent presentation for comb associative operads using the Knuth-Bendix completion procedure. In particular, the comb associative operad corresponding to 3 admits a finite convergent presentation, from which we deduce a complete description of its Hilbert series.

Enumerative and analytic combinatorics
Monday December 3, 2018, 11AM, Salle 3052
Cédric Boutillier (LPSM, Sorbonne Université) Statistical mechanics on isoradial graphs

Isoradial graphs are embedded planar graphs in such a way that every face is inscribed in a circle of radius 1. They are a perfect ground to develop a theory of discrete complex analysis and to define integrable models in statistical mechanics. In this talk, we will describe combinatorial and geometric aspects of these graphs, and their impact on locality of some models of statistical mechanics (dimer models, random walk, spanning trees…)

ASD seminar, co-organized by Combi and Graph

Enumerative and analytic combinatorics
Thursday November 29, 2018, 11AM, Institut Henri Poincaré, salle 314
Mireille Bousquet-Mélou, Charles Bordenave, Vincent Delecroix Séminaire Flajolet
http://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Thursday November 22, 2018, 11:45AM, Salle 1007
Arthur Nunge (IRIF) An algebraic refinement of the 2-PASEP probabilities.

The Partially asymmetric exclusion process (PASEP) is a physical model viewed as a Markov chain representing the displacement of particles over a finite line. The steady-state probabilities of this chain can be computed by enumerating permutations according to certain statistics. These probabilities have a natural connexion with some transition matrices, in the algebra of noncommutative symmetric functions, which implies a refinement of the probabilities of the PASEP using statistics on permuations. We place ourself in the context of the 2-PASEP, the PASEP with two kind of particles, and exhibit a connexion with the free algebra indexed by segmented compositions using statistics on partially signed permutations.

Enumerative and analytic combinatorics
Thursday November 15, 2018, 11:45AM, Salle 1007
Frédéric Meunier (ENPC) Envy-free division of a cake: the poisoned case, and other variations

Given a cake (identified with the interval [0,1]) and players with different tastes, the envy-free cake-cutting problem asks for a partition of the cake into connected pieces so that it is possible to assign the pieces to the players without making any of them jealous. The Stromquist-Woodall theorem ensures the existence of such an envy-free division under mild conditions. Recently, Segal-Halevi asked whether these conditions could be even further relaxed by allowing that some players dislike the cake (e.g., they know the cake has been poisoned). In the traditional setting, all players are “hungry”, and always prefer to get something instead of nothing. We provide a partial answer to that question and propose also other extensions, e.g., when suddenly one player disappears.

Based on joint work with Florian Frick, Kelsey Houston-Edwards, Francis E. Su, Shira Zerbib.

Enumerative and analytic combinatorics
Thursday November 8, 2018, 11:45AM, Salle 1007
Nicolas Curien (Université d'Orsay) Critical parking on a random tree… and random planar maps!

Imagine a plane tree together with a configuration of particles (cars) at each vertex. Each car tries to park on its node, and if the latter is occupied, it moves downward towards the root trying to find an empty slot. This model has been studied recently by Bruner and Panholzer as well as Goldschmidt and Przykicki where is it shown that parking of all cars obeys a phase transition ruled by the density of cars. We study the annealed critical model of random plane tree together with a parking configuration of cars. Surprisingly this object is connected to stable looptree of parameter 3/2 and to processes encountered in the theory of random planar maps!

The talk is based on ongoing work with Olivier Hénard.

Enumerative and analytic combinatorics
Thursday October 25, 2018, 11:45AM, Salle 1007
Erik Slivken (Université Paris 7, LPSM) Large random pattern-avoiding permutations

A pattern in a permutation is a subsequence with a specific relative order. What can we say about a typical large random permutation that avoids a particular pattern? We use a variety of approaches. For certain classes we give a geometric description that relates these classes to other types of well-studied concepts like random walks or random trees. Using the right geometric description we can find the the distribution of certain statistics like the number and location of fixed points.

Enumerative and analytic combinatorics
Thursday October 18, 2018, 11:45AM, Salle 1007
Isaac Konan (IRIF) Combinatoire autour des identités de type Rogers-Ramanujan

“Pour un entier positif n donné, on dénombre autant de partitions de n en parts distinctes que de partitions de n en parts impairs”.

Cette identité, attribuée à Euler, résume bien ce qu'est une identité du type Rogers-Ramanujan: une égalité entre cardinaux d'ensembles de partitions, qui pour l'un vérifient des conditions de congruences sur ses parts, et l'autre des conditions sur les différences entre parts consécutives.

Nous présenterons certaines méthodes utilisées pour établir ces égalités, telles que la méthode des mots pondérés, les équations de q-différence, ainsi que des bijections directes. On étudiera entre autre l'identié Alladi-Gordon qui généralise celle de Schur, et si le temps nous le permet, l'identité de Siladic issue de la théorie des représentations des algèbres de Lie.

Enumerative and analytic combinatorics
Thursday October 11, 2018, 11:45AM, Salle 1007
Cyril Marzouk (Uniersité Paris-sud) Limite d’échelle d’arbres et cartes à degrés prescrits

Dans cet exposé (basé sur un travail en cours), nous considérons le modèle d’arbres aléatoires suivant: étant donné n nombres entiers strictement positifs, on choisit un arbre (planaire enraciné) uniformément au hasard parmi ceux possédant n noeuds internes, dont les degrés sortants sont donnés par ces nombres ; par exemple, un arbre d-aire uniforme correspond à prendre tous ces n nombres égaux à d. Nous donnons une condition (très simple !) optimale sur les degrés pour que cette suite d’arbres, correctement mis à l’échelle, converge en loi vers le célèbre arbre continu brownien d'Aldous. En particulier, pour n'importe quelle suite (d_n)_n, les arbres d_n-aires uniformes à n noeuds internes convergent vers cet arbre brownien. De la même manière, nous considérons (plus brièvement) le modèle de cartes planaires biparties à degrés (des faces) prescrits et nous montrons que la même condition sur les degrés entraîne la convergence vers la carte brownienne ; en particulier, pour n’importe quelle suite (p_n)_n, les 2p_n-angulations à n faces convergent vers la carte brownienne.

Enumerative and analytic combinatorics
Thursday October 4, 2018, 11:45AM, Salle 1007
Baptiste Louf (IRIF) Bijections, cartes planaires et hiérarchie KP

La hiérarchie KP est un ensemble d’EDP provenant originellement de la physique mathématique. Il s’avère qu’elle s’applique aussi aux cartes combinatoires et aux objets similaires (constellations, nombres de Hurwitz) : Goulden et Jackson en ont tiré une formule de récurrence pour les triangulations, puis Carrell et Chapuy ont trouvé une formule s’appliquant aux cartes en général. Ces différentes formules ont été prouvées à l’aide de la théorie des représentations du groupe symétrique, et il est naturel de chercher des bijections les expliquant. La restriction de ces formules aux cartes à une face — la formule d’Harer Zagier — a été prouvée bijectivement par Chapuy Féray et Fusy. Je présenterai une preuve bijective de la restriction de ces formules aux cartes planaires.

Enumerative and analytic combinatorics
Thursday September 27, 2018, 11:45AM, Salle 1007
François Bergeron (Université du Québec à Montréal) Positivité, fonctions symétriques, et énumération

La théorie des fonctions symétriques est une source particulièrement fertile d'identités combinatoires importantes. Pour ce faire, il faut bien entendu des expressions positives (avec coefficients entiers). Après avoir illustré les mécanismes qui permettent d'obtenir de belles identités combinatoires à partir des fonctions symétriques, nous allons montrer qu'il y a à la fois une rareté de ces phénomènes, et d'autre part une forte invariance de la positivité pour toutes les opérations importantes du contexte. On mentionnera au passage des liens avec une version algébrique du problème P vs NP.

Enumerative and analytic combinatorics
Thursday September 20, 2018, 11AM, Institut Poincaré, salle 314
Arnaud De Mesmay, Frédéric Jouhet, Bénédicte Haas (-) Séminaire Flajolet

Enumerative and analytic combinatorics
Thursday July 5, 2018, 11:45AM, Salle 1007
Arnaud Le Ny (Université Paris-Est Créteil, LAMA) Mesures de Gibbs pour modèles d’Ising proche-voisins et à longue portée

Au cours de cet exposé, nous décrirons le formalisme DLR de description des états d’équilibre en mécanique statistique mathématique tel qu’il a été établi par Georgii (1988), après avoir été introduit par Dobrushin (1968) et Lanford/Ruelle (1969). Nous décrirons tout d’abord l’ensemble des mesures de Gibbs dans le cadre de modèles d’Ising aux proches voisins en insistant sur l’absence ou l’existence d’états extrémaux non-invariant par translation (Etats de Dobrushin). Tandis qu’en dimension 2 l’absence de tels états est reliée à la fluctuations d’interfaces microscopique et à la coexistence de phases à basse température, leur présence en dimension supérieure est interprétée comme la manifestation d’interfaces macroscopiques séparant des phases dites pures. Nous décrirons ensuite des résultats plus récents concernant des modèles d’Ising à longues portées obtenus en collaboration avec R. Bissacot, E. Endo et A. van Enter (en dimension 1) et avec L. Coquille, A. van Enter et W. Ruszel (en dimension 2).

Enumerative and analytic combinatorics
Tuesday June 26, 2018, 11AM, Salle 1007
Juanjo Rué (Universitat Politècnica de Catalunya) Enumeration of labelled 4-regular planar graphs

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 discuss how to obtain asymptotic results.

This is based on joint works with Marc Noy (UPC) and Clément Réquile (TU Wien)

Enumerative and analytic combinatorics
Thursday June 21, 2018, 11:45AM, Salle 1007
Laurent Viennot (IRIF et INRIA) Revisiting Radius, Diameter, and all Eccentricity Computation in Graphs through Certificates

We introduce notions of certificates allowing to bound eccentricities in a graph. In particular , we revisit radius (minimum eccentricity) and diameter (maximum eccentricity) computation and explain the efficiency of practical radius and diameter algorithms by the existence of small certificates for radius and diameter plus few additional properties. We show how such computation is related to covering a graph with certain balls or complementary of balls. We introduce several new algorithmic techniques related to eccentricity computation and propose algorithms for radius, diameter and all eccentricities with theoretical guarantees with respect to certain graph parameters. This is complemented by experimental results on various real-world graphs showing that these parameters appear to be low in practice. We also obtain refined results in the case where the input graph has low doubling dimension, has low hyperbolicity, or is chordal.

Enumerative and analytic combinatorics
Thursday June 14, 2018, 11:45AM, Salle 1007
Arnau Padrol (IMJ - Paris 6) Counting polytopes

This talk will be an introduction to the enumeration of combinatorial types of convex polytopes, and the contrast between low and high dimensions. While in dimensions up to 3 we have a very good understanding on the asymptotic growth of the number of polytopes with respect to the number of vertices, in higher dimensions we only have coarse estimates. There is a family for which precise enumeration is possible, d-polytopes with d+3 vertices, thanks to Gale duality. I will finish with open problems and partial results concerning the enumeration of d-polytopes in terms of their number of vertices and facets.

Enumerative and analytic combinatorics
Thursday June 7, 2018, 10:30AM, Institut Henri Poincaré, Amphi Darboux
Matjaz Konvalinka Et Vlady Ravelomanana (Université de Ljubljana, Université Paris 7) Séminaire Flajolet

Enumerative and analytic combinatorics
Thursday May 31, 2018, 11:45AM, Salle 1007
Matthieu Josuat-Vergès (LIGM Marne-la-Vallée) Polynômes d'Ehrhart et énumération de permutations cycliques

Le calcul de volume de polytopes est un problème combinatoire classique, et peut se ramener à un problème d'énumération une fois qu'on a triangulé le polytope. Plus généralement, le comptage de points entiers dans les polytopes permet de raffiner le calcul du volume (via le polynôme d'Ehrhart). Ici on s'intéresse à une famille de polytopes bien particulières, et le problème d'énumération associé fait apparaître des permutations cycliques satisfaisant certaines conditions.

Il s'agit d'un travail en commun avec A. Ayyer et S. Ramassamy (mais l'exposé sera relativement indépendant de celui donné par Sanjay dans un précédent séminaire !).

Enumerative and analytic combinatorics
Thursday May 24, 2018, 12:10AM, Salle 1007
Pablo Rotondo (IRIF et GREYC) Continued Logarithm Algorithm: A probabilistic study

Introduced by Gosper in 1978, the Continued Logarithm Algorithm computes the gcd of two integers efficiently, performing only shifts and subtractions. Shallit has studied its worst-case complexity in 2016, showing it to be linear. Here, we perform the average-case analysis of the algorithm: we study its main parameters (number of iterations, total number of shifts) and obtain precise asymptotics for their mean values, with explicit constants. Our analysis involves the dynamical system underlying the algorithm, which produces continued fraction expansions whose quotients are powers of 2. Even though studied by Chan in 2005, this system from an Ergodic Theory perspective, the presence of powers of 2 in the quotients gives a dyadic flavour which cannot be analysed only with Chan's results. Thus we introduce a dyadic component and deal with a two-component dynamical system. With this new mixed system at hand, we provide a complete average-case analysis of the algorithm.

Enumerative and analytic combinatorics
Thursday May 3, 2018, 11:45AM, Salle 1007
Frédéric Chyzak (INRIA) Bijections par automates pour des variantes de marches tandem sur le réseau carré

Dans cet exposé, nous nous intéressons à plusieurs modèles de marches sur le réseau~${\mathbb Z}^2$, pour obtenir, à longueur~$n$ fixée et pour certains ensembles de pas bien choisis, des bijections entre, d'une part, des modèles de marches du demi-plan supérieur terminant sur l'axe des abscisses, et d'autre part, des modèles de marches du quart de plan.

Une première bijection tout à fait explicite est classique pour les marches tandem, c'est-à-dire entre les marches du demi-plan empruntant les pas Nord, Ouest et Sud-Est, et les marches du quart de plan empruntant les mêmes pas. Nous donnons d'abord un nouveau calcul de cette bijection et de son inverse, exprimé à l'aide d'automates réalisant des transductions. L'analyse de ce calcul permet un suivi de paramètres sur la position finale des marches, raffinant ainsi la bijection initiale.

Le résultat se généralise d'abord en une bijection entre une bicoloration du modèle précédent à trois pas confiné au demi-plan et le modèle du quart de plan obtenu en complétant l'ensemble de pas par symétrie, de sorte à autoriser les six pas Nord, Nord-Ouest, Ouest, Sud, Sud-Est et Est. Cette nouvelle bijection fournit une explication bijective au facteur~$2^n$ observé par Bousquet-Mélou et Mishna pour le modèle à six pas.

Une autre généralisation fournit une bijection entre modèles à grands pas. Plus précisément, pour chaque~$p$ donné, en conservant le pas Sud-Est et en remplaçant les pas Nord et Ouest par les $p+1$ pas de longueur~$p$ dans le quadrant Nord-Ouest. Ce modèle est proche, mais distinct, des modèles de chemins tandems généralisés étudiés par Bousquet-Mélou, Fusy et Raschel.

(Exposé sur la base de travaux en cours avec A.~Bostan, A.~Mahboubi et K.~Yeats.)

Enumerative and analytic combinatorics
Thursday April 12, 2018, 10:30AM, Institut Henri Poincaré, Amphi Hermite
Cesar Ceballos, Hugo Duminil-Copin, Bérénice Delcroix-Oger Séminaire Flajolet
http://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Tuesday April 10, 2018, 2PM, 3052
Sanjay Ramassamy (ENS Lyon) Extensions of partial cyclic orders, boustrophedons and polytopes

While the enumeration of linear extensions of a given poset is a well-studied question, its cyclic counterpart (enumerating extensions to total cyclic orders of a given partial cyclic order) has been subject to very little investigation. In this talk I will introduce some classes of partial cyclic orders for which this enumeration problem is tractable. Some cases require the use of a multidimensional version of the classical boustrophedon construction (a.k.a Seidel-Entringer-Arnold triangle). The integers arising from these enumerative questions also appear as the normalized volumes of certain polytopes.

This is partly joint work with Arvind Ayyer (Indian Institute of Science) and Matthieu Josuat-Vergès (LIGM / CNRS)

Enumerative and analytic combinatorics
Thursday April 5, 2018, 11:45AM, Salle 1007
Dan Betea Finite temperature Plancherel random partitions

We analyze a certain finite temperature generalization of the Plancherel measure on partitions using the cylindric (periodic) Schur process. The measure, introduced by Borodin and which interpolates between Plancherel and uniformly random partitions, counts standard Young tableaux of skew shape. A simple modification becomes determinantal with kernel the finite temperature Bessel kernel. Edge fluctuations are governed by the one-third exponent and the finite temperature Tracy–Widom distribution of Johansson, itself interpolating between the Tracy–Widom distribution and the Gumbel distribution of extreme statistics. If time permits, we mention semi-speculative relations to longest increasing subsequences. Our results are discrete analogues of finite temperature random matrix results of Forrester, Johansson, and more recently, of Majumdar–Schehr and Cunden–Mezzadri–O'Connell. This is joint work with Jeremie Bouttier.

Enumerative and analytic combinatorics
Thursday March 29, 2018, 11:45AM, Salle 1007
Melissa Sherman-Bennett (Berkeley) Combinatorics of X-variables in finite type cluster algebras

Cluster algebras were introduced by Fomin and Zelevinsky in the early 2000s, with the intent of establishing a general algebraic structure for studying dual canonical bases of semisimple groups and total positivity. A cluster algebra is a commutative ring determined by an initial “seed,” which consists of A-variables, X-variables, and some additional data. One then applies a combinatorial process called mutation to this seed to obtain another seed. The cluster algebra is generated by the variables obtained from all possible sequences of mutations. In this talk, we will focus on cluster algebras of finite type, which are those with finitely many A- and X-variables. There is a complete classification of finite type cluster algebras due to Fomin and Zelevinsky, which coincides with the classification of reduced crystallographic root systems. For classical types, the combinatorics of the A-variables and their mutations are encoded by triangulations of marked surfaces associated to each type. In particular, seeds are in bijection with triangulations, and A-variables are in bijection with the arcs of the triangulations. In this talk, we will discuss new results on the combinatorics of the X-variables in finite type cluster algebras. We will show that in classical types, the X-variables are in bijection with the quadrilaterals (with a choice of diagonal) appearing in triangulations of the surface of the appropriate type. Using this bijection, we can then count the number of X-variables in each type, as well as obtain some corollaries regarding the structure of finite type cluster algebras.

Enumerative and analytic combinatorics
Thursday March 22, 2018, 11:45AM, Salle 1007
Andrea Sportiello (LIPN, Université Paris 13) The tangent method for the determination of Arctic Curves: the simplest rigorous application

In the paper “Arctic curves of the six-vertex model on generic domains: the Tangent Method” [J. Stat. Phys. 164 (2016) 1488, arXiv:1605.01388], of Filippo Colomo and myself, we pose the basis for a method aimed at the determination of the “arctic curve” of large random combinatorial structures, i.e. the boundary between regions with zero and non-zero local entropy, in the scaling limit.

In this paper many things are claimed, and few are proven. In particular a few questions remain only vaguely answered: * how rigorous is this method? * in which cases does it apply, rigorously or heuristically? * in the cases where other methods exist, how does it compare?

We will try to answer to this partially, by giving a “top-to-bottom” rigorous derivation for the simplest and oldest case: the arctic circle phenomenon for “domino tilings of the aztec diamond”, first discovered by Jockusch, Propp and Shor [arXiv:math/9801068, but in fact from 1995]. We suppose that, of the nowadays many possible derivations of the arctic circle phenomenon, those coming from the tangent method (and restricted to the rigorous versions of it) are the fastest and cheapest ones. The audience will judge…

Enumerative and analytic combinatorics
Thursday March 8, 2018, 11:45AM, Salle 1007
Samuele Giraudo (Université Paris-Est Marne-la-Vallée) Séries d'arbres, motifs exclus et opérades

Les arbres syntaxiques sont des structures de données adaptées pour représenter des expressions de toutes sortes (algébriques, arithmétiques, logiques, etc.). Une notion d'arbres à motifs exclus apparaît alors naturellement dans ce contexte et apporte de belles propriétés combinatoires. Nous parlerons ici de séries formelles d'arbres, généralisant les séries génératrices habituelles. Une façon de dénombrer les arbres évitant un ensemble de motifs sera présentée. Nous nous intéresserons ensuite aux inverses de ces séries d'arbres vis-à-vis d'un produit de composition. Tout ceci entretient des liens très forts avec la théorie des opérades, point qui fera l'objet de la dernière partie de l'exposé.

Enumerative and analytic combinatorics
Tuesday February 27, 2018, 2PM, 1007
Dieter Mitsche (Université de Nice Sophia-Antipolis) Aspects des graphes aléatoires

Dans cet exposé j'expliquerai plusieurs de mes travaux sur différents modèles de graphes aléatoires : en particulier, je vais expliquer les périodes de connexité d'un modèle dynamique des graphes géométriques Euclidiens, la rigidité et l'orientabilité du graphe G(n,p), et je parlerai (de résultats sur) des graphes aléatoires hyperboliques et d'applications pour des grands réseaux.

Joint seminar

Enumerative and analytic combinatorics
Thursday February 22, 2018, 11:45AM, Salle 1007
Justine Falque (LRI, université Paris-sud 11) Algèbre des orbites des groupes à profil polynomial, théorèmes de Cameron et de Macpherson

Étant donné un groupe de permutation infini G, on définit la fonction qui à tout entier naturel n associe le nombre d'orbites de sous-ensembles de cardinal n, pour l'action induite de G sur les sous-ensembles d'éléments. Cameron a conjecturé que cette fonction de comptage (le profil de G) est un quasi-polynôme dans le cas où sa croissance est polynomiale. Une autre conjecture, plus forte, a été émise plus tard par un de ses étudiants, Macpherson. Elle concerne une certaine structure d'algèbre graduée sur les orbites de sous-ensembles, créée par Cameron, et suppose que si le profil de G est polynomial, alors son algèbre des orbites est de type fini. L'exposé présentera ces deux conjectures et leur contexte, ainsi que les idées de la preuve de la conjecture de Macpherson, fruit d'un travail commun de Nicolas Thiéry et Justine Falque (avec les conseils précieux de Peter Cameron lui-même).

Enumerative and analytic combinatorics
Thursday February 15, 2018, 10:30AM, Institut Henri Poincaré, Amphi Darboux
Bruno Vallette, Marthe Bonamy, Igor Kortchemski Séminaire Philippe Flajolet

Voir : http://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Thursday February 8, 2018, 11:45AM, Salle 1007
Jérémie Bettinelli (LIX, école Polytechnique) Convergence of uniform noncrossing partitions toward the Brownian triangulation

We give a short proof that a uniform noncrossing partition of the regular n-gon weakly converges toward Aldous's Brownian triangulation of the disk, in the sense of the Hausdorff topology. This result was first obtained by Curien & Kortchemski, using a more complicated encoding. Thanks to a result of Marchal on strong convergence of Dyck paths toward the Brownian excursion, we furthermore give an algorithm that allows to recursively construct a sequence of uniform noncrossing partitions for which the previous convergence holds almost surely. In addition, we also treat the case of uniform noncrossing pair partitions of even-sided polygons.

Enumerative and analytic combinatorics
Thursday February 1, 2018, 11:45AM, Salle 1007
Guillem Perarnau (University of Birmingham) Critical percolation on random regular graphs

We show that for all d in {3,…,n-1} the size of the largest component of a random d-regular graph on n vertices at the percolation threshold p=1/(d-1) is of order n^(2/3), with high probability. This extends known results for fixed d and for d=n-1, confirming a prediction of Nachmias and Peres on a question of Benjamini. In contrast to previous approaches, our proof is based on a simple application of the switching method. This is joint work with Felix Joos.

Guillem's visit is sponsored by the ERC CombiTop.

Enumerative and analytic combinatorics
Thursday January 25, 2018, 11:45AM, Salle 1007
Cécile Mammez (Université du Littoral Côte d'opale) Etude combinatoire des diagrammes de dissection de Dupont

Dans sa thèse de doctorat, Dupont s’intéresse au problème du calcul du coproduit de l’algèbre de Hopf fondamentale dans la catégorie des structure de Hodge-Tate mixte pour la famille des polylogarithmes motiviques de dissection. Pour cela, il introduit une famille d’algèbres de Hopf combinatoires de diagrammes de dissection, dont le produit est donné par l’union disjointe et le coproduit par un procédé d’extraction-contraction à paramètre. Ces outils lui permettent de définir, pour tout entier naturel n, des n-formes méromorphes de C^n et de définir par la suite des intégrales absolument convergentes (périodes).

Pour tout scalaire x, nous notons HD l’algèbre de Hopf graduée connexe des dia- grammes de dissection de paramètre x. Nous nous sommes intéressés au problème de l’étude de sa coliberté. Pour cela nous avons considéré son dual gradué HD*. Il possède une structure pré-Lie. Nous construisons l’unique morphisme pré-Lie entre l’algèbre pré-Lie des arbres enracinés à un générateur et l’algèbre pré-Lie des diagrammes de dissection. Ceci nous permet d’étudier l’algèbre pré-Lie engendrée par le diagramme de dissection de degré 1. Nous obtenons que cette dernière est une sous-algèbre pré-Lie non triviale non libre de l’algèbre pré-Lie des diagrammes de dissection.

Enumerative and analytic combinatorics
Tuesday January 16, 2018, 2:30PM, Salle 3014
Nicolas Thiéry (Université Paris-sud) Computing huge subspaces of diagonal harmonic polynomials: symmetries to the rescue!

Last spring, I visited François Bergeron and we worked on his favorite objects: the spaces H(n,k) of diagonal harmonic polynomials in k sets of n variables. Those spaces connect to many areas of algebraic combinatorics, representation theory and beyond, and the case H(n,2) became famous a decade ago with the n! conjecture and its proof by Haiman.

To fuel his ongoing studies François needed to compute the structure of H(5,6). This is a space of dimension 6.10^5 made of polynomials in 30 variables of degree up to 15, each having thousands of terms.

In this talk, I'll explain how the calculation can now be completed in 45 minutes with a dozen cores and ~15Go of memory. This exploits a combination of strategies (symmetries, representation theory of the symmetric and general linear group, …), each of which reduces the complexity in time and memory by one or two orders of magnitude.

There will be little prerequisites and it's my hope that some strategies (and maybe the code!) could be used in other contexts.

Joint seminar

Year 2017

Enumerative and analytic combinatorics
Thursday December 21, 2017, 11:45AM, Salle 1007
Pierre-Loïc Méliot (Université Paris-sud) Fluctuations des mesures centrales sur les partitions

On s’intéresse aux fluctuations en grande dimension de modèles de partitions aléatoires introduits dans les années 80 par Kerov et Vershik. On montrera que pour tout modèle de ce type, une observable générique des partitions aléatoires est asymptotiquement gaussienne, et que l’on peut compléter ce résultat par une estimée de la vitesse de convergence et par une inégalité de concentration. La structure qui émerge pour ces mesures centrales sur les partitions est celle d’espace de modules mod-gaussien ; c’est une structure que l’on retrouve également pour les modèles de graphons et de permutons.

Enumerative and analytic combinatorics
Tuesday December 12, 2017, 2PM, Salle 3052
Jean Krivine (IRIF) Incremental Update for Graph Rewriting

Graph rewriting formalisms are well-established models for the representation of biological systems such as protein-protein interaction networks. The combinatorial complexity of these models usually prevents any explicit representation of the variables of the system, and one has to rely on stochastic simulations in order to sample the possible trajectories of the underlying Markov chain. The bottleneck of stochastic simulation algorithms is the update of the propensity function that describes the probability that a given rule is to be applied next. In this talk we present an algorithm based on a data structure, called extension basis, that can be used to update the counts of predefined graph observables after a rule of the model has been applied.

Reference: Boutillier P., Ehrhard T., Krivine J. (2017) Incremental Update for Graph Rewriting. In: Yang H. (eds) Programming Languages and Systems. ESOP 2017. Lecture Notes in Computer Science, vol 10201. Springer, Berlin, Heidelberg

Séminaire commun du pole Algorithmes et Structures Discrètes

Enumerative and analytic combinatorics
Thursday December 7, 2017, 10:30AM, Institut Henri Poincaré, Amphi Hermite
Enrica Duchi, Riccardo Biagioli, Louis Esperet Séminaire Philippe Flajolet

Enumerative and analytic combinatorics
Thursday November 30, 2017, 11:45AM, Salle 1007
Thomas Fernique (LIPN, Université Paris 13) Plans discrets et règles locales

Discrétiser un plan irrationnel est un moyen générique d'obtenir un pavage non périodique. On s'intéresse ici à la question de savoir quand un tel pavage est, malgré son apériodicité, caractérisé par un ensemble fini de configurations locales (en termes plus savant : quand son enveloppe forme-t-elle un sous-shift de type fini ou sofique). On commencera par quelques exemples simples en dimension un, puis on introduira le formalisme de la discrétisation de plan (certes un peu abstrait en dimensions supérieures à 3, mais qui donne pourtant des pavages très visuels) et on proposera survol des résultats obtenus ces dernières années (notamment en collaboration avec Mathieu Sablik et Nicolas Bédaride). Il y aura des simulations de machine de Turing et de la géométrie algébrique de bas niveau.

Enumerative and analytic combinatorics
Thursday November 23, 2017, 11:45AM, Salle 1007
Mathias Lepoutre (École Polytechnique (LIX)) A bijective proof of the enumeration of maps in higher genus

Bender and Canfield proved in 1991 that the generating series of maps in higher genus is a rational function of the generating series of planar maps. In this talk, I will give the first bijective proof of this result. Our approach starts with the introduction of a canonical orientation that enables us to construct a bijection between $4$-valent bicolorable maps and a family of unicellular blossoming maps.

Enumerative and analytic combinatorics
Tuesday November 14, 2017, 2PM, Salle 3052
Laurent Maussoulie (MSR-Inria) Rapid Mixing of Local Graph Dynamics

Graph dynamics arise naturally in many contexts. For instance in peer-to-peer networks, a participating peer may replace an existing connection with one neighbour by a new connection with a neighbour's neighbour. Several such local rewiring rules have been proposed to ensure that peer-to-peer networks achieve good connectivity properties (e.g. high expansion) in equilibrium. However it has remained an open question whether there existed such rules that also led to fast convergence to equilibrium. In this work we provide an affirmative answer: We exhibit a local rewiring rule that converges to equilibrium after each participating node has undergone only a number of rewirings that is poly-logarithmic in the system size. The proof involves consideration of the whole isoperimetric profile of the graph, and may be of independent interest.

This is joint work with Rémi Varloot.

Joint seminar

Enumerative and analytic combinatorics
Thursday November 9, 2017, 11:45AM, Salle 1007
Marie Albenque (École Polytechnique (LIX)) Convergence locale de triangulations munies d’un modèle d’Ising

En 2003, Angel et Schramm ont montré que la loi uniforme sur les triangulations planaires convergeait au sens de la limite locale lorsque l’on faisait tendre leur taille vers l’infini. La loi limite, appelée UIPT (pour Uniform Infinite Planar Triangulation) a été depuis très étudiée et est maintenant un objet bien compris. Dans mon exposé, je montrerai un résultat analogue à celui d'Angel et Schramm mais pour des triangulations échantillonnées selon la loi correspondant à un modèle d’Ising et non à la loi uniforme. La principale difficulté est d’étendre au modèle d’Ising les résultats combinatoires et énumératifs connus dans le cadre des triangulations « sans matière ». En utilisant les techniques développées par Bernardi et Bousquet-Mélou, nous parvenons à montrer que la série génératrice des triangulations avec une condition de bord fixée est algébrique. Je donnerai dans mon exposé, les principales idées des techniques qui permettent d’obtenir ces nouveaux résultats.

Je finirai par des questions ouvertes. L’objet limite est pour le moment très mal compris et pourrait servir à confirmer (ou non !) les fameuses prédictions de Watabiki.

Il s’agit d’un travail commun avec Laurent Ménard et Gilles Schaeffer.

Enumerative and analytic combinatorics
Tuesday October 17, 2017, 2PM, Salle 3052
Claire Mathieu (École Normale Supérieure - DI) Online k-compaction

Given, at each time t = 1, 2, …, n, a new file of length l(t) and a read rate r(t), an online k-compaction algorithm must maintain a collection of at most k files, choosing (at each time t, without knowing future inputs) some of the files to merge into one, thereby incurring a merge cost equal to the total length of the merged files and a read cost equal to the read rate r(t) times the number of files present at time t. The goal is to minimize the total cost over time. K-compaction algorithms are a key component of log-structured merge trees, the file-based data structure underlying NoSQL databases such as Accumulo, Bigtable, Cassandra, HBase,and others. We initiate the theoretical study of k-compaction algorithms. We formalize the problem, consider worst-case, average-case and competitive analysis (per-instance optimality), and propose new algorithms that are optimal according to these metrics.

This is joint work with Carl Staelin, Neal E. Young, and Arman Yousefi.

Séminaire du pôle algorithmique/combinatoire

Enumerative and analytic combinatorics
Thursday October 12, 2017, 11:45AM, Salle 1007
Béatrice De Tilière (Université Paris-Est Créteil, LAMA) Le modèle d'Ising Z-invariant via les dimères

Introduit par Baxter, le modèle d'Ising Z-invariant est un modèle d'Ising en dimension 2 défini sur un graphe plongé satisfaisant la condition d'isoradialité. Les constantes de couplages satisfont aux équations de Yang-Baxter; elles dépendent d'un paramètre k, interprété comme la température extérieure au système. Pour la valeur particulière k=0, le modèle d'Ising est critique.

Dans un premier temps, nous allons introduire ces notions. Nous expliquerons comment le modèle d'Ising peut être étudié au travers du modèle de dimères. Ensuite, nous parlerons de résultats obtenus avec Cédric Boutillier et Kilian Raschel sur ce modèle. Nous démontrerons une expression explicite ne dépendant que de la géométrie locale du graphe pour les probabilités du modèle de dimères. Nous prouverons une expression explicite et locale pour l'énergie libre du modèle d'Ising. Nous montrerons une transition de phase d'ordre 2 en k=0 pour le modèle d'Ising et établirons qu'il s'agit de la même transition de phase que celle des forêts couvrantes Z-invariantes.

Enumerative and analytic combinatorics
Thursday October 5, 2017, 11:45AM, Salle 1007
Philippe Marchal (LIPN) Surfaces aléatoires associées à un tableau de Young et lois limites

Un tableau de Young de forme fixée et dont on choisit un remplissage standard aléatoire peut être vu comme une surface aléatoire. L'étude de celle-ci est liée à des modèles de systèmes de particules. Cependant on ne sait pas bien étudier cette surface aléatoire. Je m'intéresserai à ce qui se passe sur le bord d'un tableau rectangulaire ou dans les coins d'un tableau de forme générale.

Enumerative and analytic combinatorics
Thursday September 28, 2017, 11:45AM, Salle 1007
Eric Fusy (LIX) Intervalles de Tamari et cartes planaires

La combinatoire des intervalles de Tamari, initiée par Chapoton, est une domaine très actif depuis une dizaine d'années. Nous présenterons ici un survol des liens bijectifs avec des familles de cartes planaires, en particulier avec les triangulations (pour les intervalles classiques) et avec les cartes biparties (pour les intervalles dits “nouveaux”), en mettant l'accent sur des symétries de distribution de paramètres que ces bijections révèlent (la partie sur les intervalles nouveaux est basée sur des discussions récentes avec Frédéric Chapoton).

Enumerative and analytic combinatorics
Thursday June 29, 2017, 11AM, Salle 1007
Wolfgang Steiner (IRIF) Développements en base réelle et permutations

Elizalde (2011) a caractérisé les permutations qu'on obtient en ordonnant des éléments consécutifs dans une trajectoire d'une $\beta$-transformation, avec une base $\beta$ positive. Le cas d'une base $\beta$ entière correspond au full shift sur $\beta$ lettres, qui a été étudié par Amigó, Elizalde et Kennel (2008). Nous considérons les bases négatives. Travail en commun avec Émilie Charlier.

Enumerative and analytic combinatorics
Thursday June 22, 2017, 11AM, Salle 1007
Luca Lionni (Paris Sud) Cartes combinatoires généralisées en dimensions supérieures

Je parlerai d'espaces discrets obtenus en collant des polytopes en dimensions trois et plus, comme des tétraèdres ou des octaèdres. En dimension 2, les collages de polygones qui maximisent le nombre de sommets à nombre fixé de polygones sont les configurations planaires, et la classe d'universalité ne dépend pas du type de polygone. En dimensions supérieures, on cherche à identifier les collages de polytopes qui maximisent le nombre de D-2 cellules à nombre fixé de polytopes. On trouve plusieurs classes d'universalité selon le type de polytope, et la situation semble donc plus riche. Je détaillerai l'étude de plusieurs exemples.

Enumerative and analytic combinatorics
Thursday June 15, 2017, 10:30AM, Salle 3052
Samuele Giraudo (LIGM CNRS Universite Paris Est) Découpage d'associativité généralisé

Les algèbres dendriformes sont des structures algébriques introduites par Loday. Elle offrent un moyen de découper un produit associatif en deux produits non nécessairement associatifs. L'étude de ces algèbres, réalisée avec le point de vue fourni par la théorie des opérades, fait apparaître la combinatoire des arbres binaires et des mélanges d'arbres. Nous définissons ici une opérade à un paramètre entier généralisant l'opérade diassociative. Par dualité de Koszul, nous obtenons des généralisations de l'opérade dendriforme. Les algèbres sur ces opérades permettent de découper un produit associatif en plusieurs parties, avec certaines relations de compatibilité. Les propriétés combinatoires et algébriques de ces structures sont passées en revue.

Enumerative and analytic combinatorics
Thursday June 8, 2017, 11AM, Salle 1007
Arthur Nunge (LIGM CNRS Universite Paris Est) Processus d'exclusion a deux especes et algebres combinatoires

Nous nous intéresserons une l'étude algébrique des coefficients apparaissant dans le calcul des probabilités stationnaire du ASEP à deux particules. Ces travaux généralisent ce qui a été fait dans le cas a un type de particule. Pour cela nous étudierons une sous-classe des permutations signées pour lesquelles nous définirons des statistiques permettant d'interpréter ces coefficients du 2-ASEP. Notre étude portera également sur une algèbre généralisant l'algèbre des fonctions symétriques non commutatives : l'algèbre des compositions segmentées.

Enumerative and analytic combinatorics
Thursday June 1, 2017, 10:30AM, Institut Henri Poincare
Irène Marcovici, Elie De Panafieu, Jean-Christophe Aval (Universite de Lorraine, Nokia (Bell Labs), CNRS Labri) Seminaire Flajolet

http://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Thursday May 18, 2017, 11AM, Salle 1007
Matthieu Josuat-Verges (LIGM CNRS) Ordre de Belinschi et Nica sur les partitions non croisees

In the context of noncommutative probabilty theories, Belinschi and Nica introduced an order on noncrossing partitions, which is stronger than the usual refinement order. Our goal is to investigate its generalization to finite Coxeter groups. The motivation is that a generating function of its intervals is related with the Möbius function of the usual order. Via Chapoton's ex-conjectures F=H and H=M, it connects this enumeration of intervals with that of faces in the cluster complex and antichains in the root poset.

Enumerative and analytic combinatorics
Thursday May 4, 2017, 11AM, Salle 1007
Svetlana Puzynina (IRIF) Combinatoire additive basée sur les mots uniformémement récurrents

Un sous-ensemble des entiers strictement positifs est appelé un ensemble IP s'il contient toutes les sommes finies d'une suite infinie croissante d'entiers naturels. Nous étudions les ensembles IP et certaines autres propriétés additives des ensembles d'entiers naturels, avec comme point de vue celui de la combinatoire des mots. Nous utilisons diverses familles bien connues de mots infinis, comme par exemple les mots Sturmiens ou les points fixes de substitution, afin de construire divers ensembles IP possédant une multitude de propriétés additives différentes qui reflètent la richesse de la structure combinatoire du mot sous-jacent.

Enumerative and analytic combinatorics
Thursday April 27, 2017, 10:30AM, Salle 3052
Bérénice Delcroix-Oger (IMT) Des arbres sans ambiguités

Seminaire PPS https://www.irif.fr/seminaires/pps/index

Enumerative and analytic combinatorics
Thursday April 20, 2017, 11AM, Salle 1007
Sergey Dovgal (LIPN et IRIF) Phase Transition Threshold for Random Graphs and 2-SAT using Degree Constraints

We show that by restricting the degrees of the vertices of a graph to an arbitrary set Δ, the threshold α(Δ) of the phase transition for a random graph with n vertices and m = α(Δ).n edges can be either accelerated (e.g., α(Δ) approx 0.38 for Δ = {0,1,4,5}) or postponed (e.g., α(Δ) approx 0.95 for Δ={1,2,50}) compared to a classical Erdős–Rényi random graph where α(N)=1/2. We investigate different graph statistics inside the critical window of transition (planarity, diameter, longest path…). We apply our results to a 2-SAT model with restricted literal degrees: the number of clauses that each literal is incident to belongs to the set Δ. We prove a lower bound for the probability that a formula with n variables and m=2.α(Δ) n clauses is satisfiable. This probability is close to 1 for the subcritical regime m=2.α.n.(1-μ.n-1/3), μ to ∞ and improves/generalizes the lower bound of Bollobás, Borgs, Chayes, Kim, and Wilson. This shows how the phase transition threshold for 2-SAT moves if we change the degrees of the literals. Joint work with Vlady Ravelomanana.

Enumerative and analytic combinatorics
Thursday January 26, 2017, 2PM, Amphi Darboux - IHP
Sanjay Ramassamy Et Eric Fusy (Brown University et LIX) “Miquel dynamics for circle patterns” et “Bijections for planar maps with boundaries”

Year 2016

Enumerative and analytic combinatorics
Wednesday December 21, 2016, 11AM, Salle 3052
Victoria Lebed (Trinity College, Dublin) Que savent les tresses sur les tableaux de Young ?

Les tableaux de Young portent une multiplication associative, décrite par l'algorithme de Schensted. Le monoïde ainsi obtenu est appelé plaxique. Il joue un rôle fondamental dans de nombreuses applications combinatoires et algébriques. On montrera que cette multiplication sur les tableaux est entièrement déterminée par un tressage sur l'ensemble (bien plus simple !) des colonnes. Ici un tressage est une solution ensembliste de l'équation de Yang-Baxter. Notre tressage s'inscritégalement dans le cadre de la réécriture. Comme application, on identifiera la cohomologie de Hochschild du monoïde plaxique, quirésiste à toutes les approches classiques, à la cohomologie tressée des tableaux-colonnes, beaucoup plus accessible. Toutes les notions et constructions seront rappelées.

Enumerative and analytic combinatorics
Monday December 12, 2016, 11AM, Salle 2014
Francois Nunzi (IRIF) Soutenance de these: Autour de quelques chaines de Markov Combinatoires

Rapporteurs: M. Dukes et J.F. Marckert. Examinateurs: F. Bassino, J. Bouttier, P. Chassaing, S. Corteel, A. Sportiello, V. Ravelomanana

Enumerative and analytic combinatorics
Wednesday December 7, 2016, 11AM, Salle 1007
Cedric Boutillier (UPMC) ??

Enumerative and analytic combinatorics
Thursday December 1, 2016, 10:30AM, Salle des these Halle aux farines 580F
Christina Goldschmidt, Jean-Christophe Novelli And Guilem Perarnau (Oxford, Marne et Birmingham) Parking on a tree, Promenade autour de l'inversion de Lagrange, A switching approach to random graphs with a fixed degree sequence

http://semflajolet.math.cnrs.fr/

Enumerative and analytic combinatorics
Wednesday November 23, 2016, 11AM, Salle 1007
Alexander Moll (IHES) A New Spectral Theory for Jack Polynomials

The classical Benjamin-Ono equation v_t + v v_x = e_1 J[v_{xx}] with periodic boundary conditions is a completely integrable system for v: T → R on the unit circle T, where J is the Hilbert transform. Let H denote the Hardy space on the circle, |0> in H the vacuum, and L(v) the Toeplitz operator with symbol v. Building on the work of Nazarov-Sklyanin (2013), we show that the infinitely-many \ell=0,1,2,3,… conservation laws T_{\ell}(v|e_1) of the classical Benjamin-Ono system are moments of a conserved density given by the spectral shift function of L(v) + e_1 d/dx and its (0,0) minor. Moreover, Nazarov-Sklyanin (2013) also treat the canonical quantization of this system, associating to classical conservation laws T_{\ell}(v|e_1) an infinite hierarchy of commuting operators \hat{T}_{\ell}(v|e_2,e_1) with \hbar = - e_1 e_2 simultaneously diagonalized on Jack polynomials with parameter \alpha = - e_1 / e_2. Their eigenvalues on Jacks depend only on the profile of the *anisotropic* Young diagram built from rectangles of size (e_2, e_1). Just like in the classical case, we realize the slopes of a profile of an anisotropic Young diagram as a spectral shift function in the sense of Krein (1953). The talk will begin with the general framework of Kerov’s Markov-Krein correspondence (1998). These constructions are new even for Schur polynomials e_1 + e_2 = 0 that relies on the first Szegö theorem (1915). As time permits, we introduce a family of combinatorial objects called ``ribbon paths” that are for random partitions what ribbon graphs are for random matrices at general \beta /2 = -(e_2/e_1) >0.

Enumerative and analytic combinatorics
Wednesday November 16, 2016, 11AM, Salle 1007
Yves Guiraud (IRIF equipe PPS) Introduction à la réécriture algébrique

La réécriture est une théorie des présentations d'objets algébriques (comme les monoïdes) par générateurs et relations orientées. Elle sert traditionnellement à répondre à des questions liées à la formalisation : comment représenter les éléments d’un monoïde, ou encore comment calculer son produit ? Elle possède aussi des applications moins connues, en algèbre homotopique, en permettant de classifier les différentes preuves d'une même égalité. Cet exposé proposera une introduction à ces différents concepts et problèmes, illustrés sur le cas des monoïdes d'Artin.

Enumerative and analytic combinatorics
Wednesday November 2, 2016, 11AM, Salle 1007
Dan Betea (IRIF (postdoc projet Emergences)) RSK geometrique

Enumerative and analytic combinatorics
Wednesday October 19, 2016, 11AM, Salle 1007
Gaetan Borot (Max Planck) Counting maps with simple boundaries

Maps are discretization of a given surface obtained by glueing a finite collection of polygonal faces along pair of edges. In this definition, the faces in the map can be quite singular, due to self-glueings. Although geometrically puzzling, this convention dates back to Tutte and simplifies the enumeration. It is also natural from the point of view of matrix model techniques, in which maps arise as Feynman diagrams.

Maps with n ordinary boundaries are just maps with n distinguished marked faces. I introduce a notion of maps with simple boundaries – this roughly means that the edges along the boundaries are not allowed to touch each other so as to form a “singular” face. I will explain how planar maps with ordinary boundaries can be retrieved bijectively from maps with simple boundaries, and the functional relations between their generating series determining one in terms of the other. This provides a map interpretation of the notion of free cumulants of Voiculescu and second order free cumulants of Speicher and Collins.

For arbitrary topologies, the enumeration of maps with ordinary boundary is governed by the topological recursion of Eynard and Orantin. I will present a conjecture to enumerate maps with simple boundaries in terms of the topological recursion which would give a combinatorial interpretation of the “symplectic invariance property” of the topological recursion.

This is work in progress with Elba Garcia-Failde.

Enumerative and analytic combinatorics
Wednesday October 12, 2016, 11AM, Salle 1007
Courtiel Julien (LIPN Paris Nord) Comprendre les marches dans le quart de plan à travers les pondérations centrales

Depuis une décennie maintenant, de nombreux progrès ont été réalisés quant à l'énumération des marches confinées dans un quart de plan. De ces travaux on observe différents comportements asymptotiques, variant selon le modèle étudié. La question est donc de savoir à quel moment un comportement spécifique cesse pour laisser place à un autre ; autrement dit, comment apparaissent les transitions de phase.

Dans cet exposé, nous proposons un cadre d'étude qui permet d'avoir une vision globale de ces transitions de phase, à savoir les pondérations centrales. Cela revient à assigner un poids à chaque pas de notre modèle, selon une contrainte raisonnable qui permet de couvrir l'intégralité des drifts possibles (i.e. direction générale de la marche - grossièrement).

Nous donnerons ainsi plusieurs propriétés de ces pondérations centrales, à la fois élémentaires et porteuses de sens. Nous étudierons en particulier un modèle spécifique, celui de Gouyou-Beauchamps, avec des estimées asymptotiques précises, qui nous sont fournies par la theorie de l'analyse combinatoire à plusieurs variables. Travail en commun avec S. Melzcer, M. Mishna, K. Raschel.

Enumerative and analytic combinatorics
Wednesday October 5, 2016, 11AM, Salle 1007
Yann Chiffaudel (LPMA) Approche macroscopique de la diffusion dans le modèle des miroirs

Dans la littérature mathématique, le mot diffusion fait référence à plusieurs définitions différentes. Je m'intéresse à la diffusion dite “macroscopique” caractérisée par l'existence d'une densité de particules évoluant selon la loi de Fick. Je porterai mon attention sur le modèle des miroirs en dimension 2 et sur sa généralisation en dimension quelconque. Ce modèle de gaz de Lorentz sur réseau permet un énoncé clair et rigoureux de la loi de Fick. Une approche analytique nous a permis de simplifier le problème et de réaliser une étude numérique qui permet de conjecturer la validité de la loi de Fick en dimension 3. Je présenterai l'étude complète de façon très visuelle et abordable.

Enumerative and analytic combinatorics
Wednesday September 28, 2016, 11AM, Salle 1007
Guillaume Chapuy (IRIF) Graphes aléatoires dans les classes ajoutables et la conjecture deMcDiarmid-Steger-Welsh.

Soit G_n un graphe aléatoire uniforme à n sommets, choisi dans votre classe de graphes favorite (graphes planaires, graphes sans triangles,graphes 7-coloriables, etc…). Quelle est la probabilité que G_n soit connexe? Sans hypothèse sur la classe on ne peut, bien sûr, rien dire sur cette question. Mais si la classe de graphe est *ajoutable*, àsavoir stable par l'ajout d'arêtes entre composantes connexes, McDiarmid-Steger-Welsh (2005) ont conjecturé que P(G_n connexe) est au moins exp(-1/2)=0.60… asymptotiquement. Cette borne est optimale (car elle est atteinte pour la classe des forêts) et aussi assez étonnante (car de nombreuses classes sont ajoutables, y compris des classes très bizarres sur lesquelles on penserait ne rien pouvoir dire). Je parleraide notre démonstration de cette conjecture. Je commencerai par expliquer la très jolie et simple technique dedouble-comptage due à McSW et qui permet de démontrer la borne exp(-1). Puis j'essaierai de donner les idées principales de notre technique nouvelle, le «double-comptage local». Cette technique débouche sur un problème d'optimisation non convexe dont les fonctionnelles sont par miracle des séries génératrices d'arbres enracinés pondérés par des fonctionnelles supermultiplicatives. L'adaptation d'outils de combinatoire classique (le théorème de disymétrie!) permet de résoudre le problème. Travail commun avec Guillem Perarnau (Birmingham)

Enumerative and analytic combinatorics
Thursday September 8, 2016, 11AM, Salle 1007
Michael Wheeler (University of Melbourne) Structure constants of Hall–Littlewood/Grothendieck polynomials,

Joint work with P. Zinn Justin.

Enumerative and analytic combinatorics
Thursday June 9, 2016, 11:30AM, Salle 1007
Vlady Ravelomanana (IRIF) Some extremal properties of critical random graphs

As witnessed by several authors (see for example Nachmias, Peres [2008], Riordan-Wormald [2010]), Addagio-Berry, Broutin, Goldschmidt [2010]) studying extremal properties (diameter, circumference, longuest path, maximum block size, …) of Erd\H os-Rényi random graphs $G(n, M)$ (resp. $G(n, p)$) appear to be extremely difficult inside its critical window of transition. That is as the number of edges satisfies $M=n/2+x n^{2/3}$ (resp. $p=1/n + x/n^{4/3}$) for $x=O(1)$. In this talk, I will show how generating function approach can capture the maximum block size and give explicit bounds for the other parameters (as functions of $x$).

Enumerative and analytic combinatorics
Thursday June 2, 2016, 10:30AM, IHP Amphi Hermite
Lucas Gerin, Lenka Zbeborova, Nicolas Thiery (Polytechnique, CEA et Orsay) Seminaire Flajolet Séminaire Flajolet

10h30 - 11h30 Lucas Gerin (CMAP, Ecole Polytechnique) “Processus d’Hammersley discret et sous-suites croissante”

13h45 - 14h45 Lenka Zbedorova (Institut de Physique Theorique, CEA/SACLAY) “Clustering of sparse graphs: From phase transitions to optimal algorithms”

14h45 - 15h45 Nicolas Thiéry (LRI, Université Paris 11) “Nombre moyen de tresses dans les mots réduits et tableaux justifiés à droite”

Séminaire Flajolet

Enumerative and analytic combinatorics
Thursday May 26, 2016, 11:30AM, Salle 1007
Arnau Padrol (IMJ-PRG) Tropical Catalan Subdivisions

We revisit the associahedral subdivision of the Pitman-Stanley polytope to provide geometric realizations of the v-Tamari lattice of Préville-Ratelle and Viennot as the dual of a triangulation of a polytope, as the dual of a mixed subdivision, and as the edge-graph of a polyhedral complex induced by a tropical hyperplane arrangement. The method generalizes to type B. This is joint work with Cesar Ceballos and Camilo Sarmiento.

Enumerative and analytic combinatorics
Thursday May 19, 2016, 11:30AM, Salle 1007
Gregory Chatel (LIGM) Treillis de relations binaires.

Nous définissons une structure de treillis sur les relations binaires qui peut être vue comme une généralisation de l'ordre faible sur les permutations. Puis, en utilisant des surjections et des quotients, nous redécouvrons plusieurs treillis liés à l'ordre faible et à l'ordre de Tamari. La motivation de ce travail est l'étude de ces treillis qui peuvent souvent être interprétés comme des algèbres de Hopf et des polytopes.

Enumerative and analytic combinatorics
Thursday May 12, 2016, 11:30AM, Salle 1007
Anna Ben-Hamou (LPMA, Universite Paris-Diderot) Phénomène de cutoff pour des marches aléatoires sur des graphes aléatoires

On dit qu'une chaîne de Markov ergodique à espace d'états fini présente le phénomène de cutoff lorsque sa distance à l'équilibre reste très proche de 1 jusqu'au temps de mélange, puis chute abruptement vers 0 en une période de temps bien plus petite, appelée la fenêtre du cutoff. Dans cet exposé, nous considérerons des marches aléatoires “non-backtracking” (sans marche arrière) sur des graphes aléatoires à degrés prescrits. Sous une condition générale de sparsité, nous établirons le cutoff, sa fenêtre, et montrerons que le profil de la distance converge vers une forme universelle, celle de la fonction de queue gaussienne. Il s'agit d'un travail en collaboration avec Justin Salez.

Slides

Enumerative and analytic combinatorics
Thursday April 14, 2016, 10:30AM, IHP Amphi Hermite
Justin Salez, Carine Pivoteau, Salvatore Stella (LPMA, IGM et Roma) Seminaire Flajolet
Séminaire Flajolet

Enumerative and analytic combinatorics
Thursday April 7, 2016, 11:30AM, Salle 1007
Thomas Wong (LIPN (Postdoc projet IDEX USPC ALEA Sorbonne)) Enumeration Problems in directed walk models

Self-avoiding walks appear ubiquitously in the study of linear polymers as it naturally captures their volume exclusion property. However, self-avoiding walks are very difficult to analyse with few rigourous results available. In 2008, Alvarez et al. determined numerical results for the forces induced by a self-avoiding walk in an interactive slit. These results resembled the exact results for a directed model in the same setting by Brak et al. in 2005, suggesting the physical consistency of directed walks as polymer models. Via the kernel method, we extend the directed walk model to a series of models involving two directed walks as a way to find exact enumerative results for studying the behaviour of ring polymers near an interactive wall, or walls. In the final model we considered, we are unable to find exact solutions via the kernel method. Instead, we use transfer matrices to obtain numerical results that are qualitatively similar to those presented by Alvarez et al.

Enumerative and analytic combinatorics
Thursday March 31, 2016, 11:30AM, Salle 1007
Roberto Mantaci (IRIF) Mobiles equilibres

Un mobile est un arbre binaire dont chaque feuille est associée à un poids. Des exemples concrets peuvent être trouvés dans l'art moderne (Calder) ou au dessus des berceaux et des lits d'enfant.

Pour chaque nœud interne $u$ d'un mobile, on peut définir le déséquilibre de $u$ comme la différence $\delta(u)$ (en valeur absolue) entre la somme des poids des feuilles du sous-arbre gauche de $u$ e la somme des poids des feuilles du sous-arbre droit de $u$.

Le déséquilibre $\Delta(M)$ d'un mobile $M$ est alors la somme des désequilibres de tous ses nœuds. Si $\Delta(M)=0$, le mobile est parfaitement équilibré (comme c'est le cas pour les oeuvres de Calder et pour les mobiles pour distraire les bébés).

Le problème MobilesEquilibrés consiste à détérminer, pour un (multi-)ensemble de poids $p_1, p_2, \ldots, p_n$, le mobile $M$ dont les feuilles portent les poids $p_1, p_2, \ldots, p_n$ (dans un ordre quelconque) et dont les déséquilibre $\Delta(M)$ est le plus petit possible.

Ce problème est, dans un certain sens, la généralsation du problème bien connu qui consiste à déterminer le meilleur parenthesage pour calculer le produit ligne par colonne d'une suite de matrices (resolu polynomialement par programmation dynamique).

Bien que la question sur la complexité du problème reste ouverte (on ne sait pas s'il est NP ou si une solution polynomiale existe), nous présenterons certains algorithmes pour sa résolution, dont certains à complexité polynomiale qui résolvent le problème dans des cas particuliers, ainsi que d'autres ayant complexité exponentielles (dont un basé sur la programmation linéaire à variables entières) et qui résolvent le problème dans tous les cas. Les approches adoptées sont souvent fortément combinatoires.

Travail avec Yacine Hamoudi et Sophie Laplante.

Enumerative and analytic combinatorics
Thursday March 24, 2016, 11:30AM, Salle 1007
Clement Dervieux (IRIF) Le nombre de graphes de polyèdres en coin

Eppstein et Mumford (2014) ont récemment défini l'ensemble des polyèdres en coin comme l'ensemble des polyèdres 3D dont les sommets sont à coordonnées entières positives, les arêtes sont parallèles aux axes de coordonnées et tous les sommets sont visibles depuis l'infini dans la direction (1,1,1). Ils décrivent l'ensemble des graphes de polyèdres en coin, i.e. l'ensemble des graphes qui peuvent être squelette d'un polyèdre en coin : vus comme cartes planaires, il s'agit exactement des graphes duaux de certaines triangulations bicoloriées particulières, que nous appelons triangulations en coin enracinées. Nous comptons les graphes de polyèdres en coin en déterminant la série génératrice des triangulations en coin enracinées selon leur nombre de sommets : nous en obtenons une expression explicite en fonction de la série génératrice des nombres de Catalan. Nous montrons tout d'abord que ce résultat découle de la méthode classique de décomposition de Tutte. Ensuite, pour expliquer l'apparition des nombres de Catalan, nous donnons une décomposition algébrique directe des triangulations en coin~: en particulier nous mettons en évidence une famille de triangulations en amande qui admet une décomposition structurellement équivalente à celle des arbres binaires. Pour finir nous présentons rapidement une bijection directe entre les arbres binaires et ces triangulations en amande.

Enumerative and analytic combinatorics
Thursday March 17, 2016, 11:30AM, Salle 1007
Loick Lhote (IRIF et GREYC) Analyses en moyenne d'algorithmes en Fouille de Données: cas des motifs et des hypergraphes

L’extraction de connaissances à base de motifs (Pattern Mining) s'appuie sur de nombreux algorithmes ou structures de données pour extraire de l'information sous forme de motifs des bases de données. Les analyses dans le pire des cas conduisent très souvent à des complexités exponentielles mais les instances ne correspondent pas à des cas “réels”. Afin de décrire plus finement la complexité générique des problèmes issus du Pattern Mining, il convient de réaliser des analyses en moyenne. Dans cet exposé, nous introduirons quelques problèmes liés à l'extraction de motifs dits fréquents et nous montrerons leurs liens avec le calcul des traverses minimales d'hypergraphes. Ensuite, nous présenterons plusieurs résultats d'analyses en moyenne liés à ces objets. En particulier, nous montrons que sous certains modèles aléatoires de bases de données, l'extraction de motifs fréquents peut être de complexité polynomiale. Nous apporterons aussi un éclairage en moyenne sur la complexité d'extraction des traverses minimales d'hypergraphes. Ceci est un travail en commun avec Julien David, Arnaud Mary et François Rioult.

Enumerative and analytic combinatorics
Thursday February 18, 2016, 11AM, Salle 1007
Valentin Bonzom (LIPN) To be announced.

Enumerative and analytic combinatorics
Thursday February 11, 2016, 11AM, Salle 1007
Elie De Panafieu (Bell Labs) Énumération des graphes connexes par la combinatoire analytique

Enumerative and analytic combinatorics
Thursday February 4, 2016, 11AM, Salle 1007
Séminaire Flajolet Iii Programme

Enumerative and analytic combinatorics
Thursday January 21, 2016, 11AM, Salle 1007
Jang Soo Kim (Sungkyunkwan University (SKKU)) On q-integrals over order polytopes

Enumerative and analytic combinatorics
Thursday January 14, 2016, 11AM, Salle 1007
Karola Meszaros (Cornell University (Invitée Paris 7)) Realizing subword complexes via triangulations of root polytopes

Enumerative and analytic combinatorics
Thursday January 7, 2016, 11AM, Salle 1007
Julien Courtiel (UBC, Vancouver) Cordes terminales dans les diagrammes connexes de cordes