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.