Combinatoire énumérative et analytique Jeudi 16 décembre 2021, 14 heures, 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. Combinatoire énumérative et analytique Jeudi 9 décembre 2021, 14 heures, 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. Combinatoire énumérative et analytique Jeudi 2 décembre 2021, 14 heures, 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. Combinatoire énumérative et analytique Jeudi 25 novembre 2021, 11 heures, 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/ Combinatoire énumérative et analytique Jeudi 18 novembre 2021, 14 heures, 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). Combinatoire énumérative et analytique Jeudi 4 novembre 2021, 14 heures, 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 Combinatoire énumérative et analytique Jeudi 21 octobre 2021, 14 heures, 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. Combinatoire énumérative et analytique Jeudi 14 octobre 2021, 14 heures, 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) Combinatoire énumérative et analytique Jeudi 7 octobre 2021, 14 heures, 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. Combinatoire énumérative et analytique Jeudi 30 septembre 2021, 10 heures 30, IHP Seminaire Flajolet (IHP) Valentin Feray, Marc Lelarge, Irene Marcovici http://semflajolet.math.cnrs.fr/ Combinatoire énumérative et analytique Jeudi 23 septembre 2021, 14 heures, 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. Combinatoire énumérative et analytique Jeudi 16 septembre 2021, 14 heures, 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. Combinatoire énumérative et analytique Mercredi 31 mars 2021, 10 heures 30, 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. Combinatoire énumérative et analytique Jeudi 11 mars 2021, 14 heures, 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. Combinatoire énumérative et analytique Jeudi 18 février 2021, 10 heures 30, 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. Combinatoire énumérative et analytique Mercredi 27 janvier 2021, 10 heures 30, Virtuelle Franz Lehner (TU Graz) Non encore annoncé. Combinatoire énumérative et analytique Jeudi 21 janvier 2021, 14 heures, 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. Combinatoire énumérative et analytique Jeudi 14 janvier 2021, 14 heures, 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.