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.