Séminaire de l'Équipe Modèles Combinatoires

Mercredi 10 février Élie de Panafieu (LIP6) Énumération des graphes connexes par la combinatoire analytique Nous considérons les graphes connexes dont le nombre d'arêtes croît linéairement avec le nombre de sommets. Ils apparaissent notamment dans les graphes aléatoires sur-critiques, et sont alors nommés « composante géante ». Trois preuves de leur asymptotique existent déjà, basées sur des techniques très variées [Bender Canfield McKay 1990, Pittel Wormal 2005, van der Hofstad Spencer 2005]. Nous présentons une nouvelle formule exacte pour leur énumération, ainsi qu'une nouvelle preuve de leur asymptotique.
Notre démonstration est la première basée sur la combinatoire analytique. Les principaux ingrédients sont :

l'étude des multigraphes (boucles et arêtes multiples autorisées) au lieu des graphes, car leurs séries génératrices sont plus naturelles,
l'énumération des multigraphes et graphes de degré minimal au moins 2 (étape également cruciale de la démonstration de Pittel et Wormald),
l'emploi de l'inclusion-exclusion pour supprimer boucles et arêtes multiples, transformant ainsi les multigraphes en graphes.

Nous pensons que ces techniques permettront de résoudre d'autres d'autres problèmes d'énumération de graphes.
Ce résultat ouvre la voie à de nombreuses extensions, notamment :

l'étude de la structure des graphes aléatoires (retrouver et préciser les résultats d'Erdös et Rényi 1959)
l'extension à d'autres modèles de graphes (hypergraphes, graphes inhomogènes, graphes à degrés contraints, graphes à motifs exclus).

Mercredi 24 février Henri Mühle (LIX) Tamari Lattices for Parabolic Quotients of the Symmetric Group We present a generalization of the Tamari lattice to parabolic quotients of the symmetric group. More precisely, we generalize the notions of \(231\)-avoiding permutations, noncrossing set partitions, and nonnesting set partitions to parabolic quotients, and show bijectively that these sets are equinumerous. Furthermore, the restriction of the weak order on the parabolic quotient to the parabolic \(231\)-avoiding permutations is a lattice quotient. We then suggest how to extend these constructions to parabolic quotients of any finite Coxeter group. The main ingredient is a certain aligned condition of inversion sets, and this concept can in fact be generalized to any reduced expression of any element in any (not necessarily finite) Coxeter group.

Mercredi 2 mars Séance participative

Mercredi 30 mars Anne Micheli (LIAFA) Coxeter Hyperplane arrangements and trees Stanley et Postnikov ont étudié les arrangements de Coxeter d'hyperplans et leurs déformations dans leur papier « Deformations of Coxeter hyperplane arrangements » en 2000. Gessel a par ailleurs montré en 2014 lors d'une communication le lien entre certains arrangements (resp. Shi, Braid, Catalan) et des familles d'arbres (resp. arbres de Cayley, décroissants, binaires et étiquetés). Je présenterai de nouvelles familles d'arbres en bijection avec les régions des arragements d'hyperplans de \(\mathbb{R}^n\) définis par le système \(x_i-x_j = g\), \(1 \leq i, j \leq n\) et \(g \in \{-a, -a+1, \ldots, a+b-1\}\). Ces bijections ont été obtenues en utilisant des techniques venant de la combinatoire énumérative et bijective, ainsi que de la théorie des matroids avec les graphes à gain de Zavlasky. Ce travail a été réalisé en commun avec Sylvie Corteel (IRIF, Paris 7) et David Forge (LRI, Orsay).

Mercredi 30 mars Antoine Deza (McMaster University) Euler Polytopes and Convex Matroid Optimization We introduce a novel family of polytopes strengthening bounds relevant to combinatorial optimization and convex matroid optimization. Del Pia and Michini recently improved the upper bound of kd due to Kleinschmidt and Onn for the largest possible diameter of the convex hull of a set of points in dimension \(d\) whose coordinates are integers between \(0\) and \(k\). We introduce Euler polytopes which include a family of lattice polytopes with diameter \((k+1)d/2\), and thus reduce the gap between the lower and upper bounds. In addition, we highlight connections between Euler polytopes and a parameter studied in convex matroid optimization, and strengthen the lower and upper bounds for this parameter. Based on joint work with George Manoussakis, Orsay, and Shmuel Onn, Technion.

Mercredi 13 avril Salvatore Stella (Università di Roma La Sapienza) Coefficients in the exchange relations of finite type cluster algebras Cluster algebras of finite type are among the most understood examples of cluster algebras. In particular, through the work of several authors, they come equipped with a combinatorial model (a generalized associahedron) defined in terms of weights for the associated Weyl group. Unfortunately this model, while describing completely the cluster variables, is only able to reproduce the coefficient-free version of the exchange relations.
After recalling the required background, we will explain how to extend the construction and explicitly compute the coefficient part of each exchange relation. No knowledge of cluster algebras will be assumed, in particular this talk can be used as an example on how to think of cluster algebras from a purely combinatorial perspective.

Mercredi 20 avril Francisco Santos (Universidad de Cantabria) Lattice polytopes: threshold width and enumeration Lattice polytopes, that is, polytopes with integer vertices arise in algebraic geometry, statistics, optimization, mathematical physics besides, of course, discrete geometry. In particular, in recent years some effort has been put to classifying different classes of them (reflexive ones, canonical or terminal ones, hollow ones, etc). Our starting point for a new classification scheme is the existence of a « threshold width » \(w(d)\) depending only on the dimension such that for each number \(n\) there are only finitely many lattice \(d\)-polytopes with \(n\) lattice points and width larger than \(w(d)\). Here, the width of a lattice polytope \(P\) is the minimum over all integer linear functionals \(f\), of the difference between the maximum and minimum values of \(f\) on \(P\).
The existence of the threshold width combines results of Hensley [1983], Lagarias–Ziegler [1991] and Nill–Ziegler [2011]. We show the bounds \(w_H(d-2) \le w(d) \le w_H(d-1)\), where \(w_H(d)\) is the maximum width of a lattice polytope with no interior lattice points, which implies \(d-3 \le w(d) \le O(d^{3/2})\). (Finiteness of \(w_H(d)\) follows from Kannan-Lovász [1988] general results on lattice free convex bodies).
In dimensions three and four we prove \(w(3)=1\) and \(w(4)=2\). In particular, this suggests the following way of classifying lattice \(3\)-polytopes with few lattice points: those of width one are infinitely many but easy to understand (they consist of two lattice polygons placed in consecutive parallel lattice hyperplanes) and those of larger width are finitely many for each number of lattice points. We have implemented this approach and, in particular, obtained the full enumeration of lattice \(3\)-polytopes of width larger than one and with at most \(11\) lattice points.
This is joint work with Mónica Blanco and, partially, Christian Haase and Jan Hofmann.

Mercredi 27 avril Cesar Ceballos (Universität Wien) 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 (which generalizes the m-Tamari lattice) 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 Arnau Padrol and Camilo Sarmiento.

Mercredi 4 mai Séance participative (Thibault Manneville et Joël Gay)

Mercredi 11 mai Séance participative (Thibault Benjamin)

Mercredi 18 mai Valentin Bonzom (LIPN) Une généralisation des cartes en dimensions supérieures Les cartes combinatoires sont des discrétisations de surfaces. C'est un enjeu important de les généraliser aux dimensions supérieures. Je présenterai une approche fondée sur l'utilisation de graphes aux arêtes colorées. J'expliquerai comment ceux-ci permettent de géneraliser les \(p\)-angulations en représentant des complexes simpliciaux de dimensions \(d \geq 2\). On cherche alors à les classifier selon le nombre de cellules de dimension \(d-2\) à nombre de simplexes fixés. Dans cette optique, j'introduirai une bijection avec des cartes colorées dites farcies, qui s'inspire d'une part de la bijection de Tutte entre quadrangulations biparties et cartes quelconques et d'autre part de la représentation de Walsh des hypercartes comme cartes biparties. Cette bijection permet dans certains cas d'identifier les complexes simpliciaux qui maximisent le nombre de cellules de dimension \(d-2\), d'en calculer les fonctions génératrices et d'analyser leurs singularités.

Mercredi 25 mai Yann Palu (LAMFA, Université de Picardie) Algèbres amassées et représentations de carquois S. Fomin et A. Zelevinski ont introduit les algèbres amassées dans le but d'offrir une approche combinatoire à l'étude des bases canoniques de Lusztig, dans les anneaux de coordonnées homogènes de certaines variétés (Grassmanniennes, variétés de drapeaux...). La définition d'une algèbre amassée est quelque peu inhabituelle : ses générateurs et relations sont construits récursivement à partir d'une « graine initiale » selon un processus de « mutation ». Très rapidement, la combinatoire des mutations a été réinterprétée dans d'autres domaines : Systèmes intégrables, géométrie de Poisson, représentations de carquois, géométrie algébrique... Cet exposé est une introduction aux algèbres amassées et à leur lien avec la théorie des représentations de carquois.

Mercredi 1 juin Wenjie Fang (IRIF) Des intervalles de Tamari généralisé aux cartes planaires non-séparables Soit \(v\) un chemin arbitraire constitué de pas Nord et Est. Le treillis \(\mathrm{Tam}(v)\), basé sur tous les chemins faiblement au dessus de \(v\) avec les mêmes extrémités que \(v\), a été introduit par Préville-Ratelle et Viennot (2014) et correspond au treillis de Tamari classique dans le cas \(v=(NE)^n\). Ils ont démontré que \(\mathrm{Tam}(v)\) est isomorphe au treillis dual de \(\mathrm{Tam}(\overleftarrow{v})\), où \(\overleftarrow{v}\) est \(v\) renversé avec \(N\) et \(E\) échangés. Notre contribution principale est une bijection entre les intervalles de \(\mathrm{Tam}(v)\) et les cartes planaires non-séparables. Il s'ensuit que le nombre d'intervalles dans \(\mathrm{Tam}(v)\) sur tous les chemins \(v\) de longueur \(n\) est donné par \(\frac{2 (3n+3)!}{(n+2)! (2n+3)!}\). Cette formule a été obtenue par Tutte (1963) pour les cartes planaires non-séparables. Nous démontrons aussi que l'isomorphisme entre \(\mathrm{Tam}(v)\) et le dual de \(\mathrm{Tam}(\overleftarrow{v})\) est équivalent à la dualité des cartes par notre bijection. Travail joint avec Louis-François Préville-Ratelle.

Mercredi 8 juin Xavier Allamigeon (CMAP) Long and winding central paths We disprove a continuous analogue of the Hirsch conjecture proposed by Deza, Terlaky and Zinchenko, by constructing a family of linear programs with \(3r+4\) inequalities in dimension \(2r+2\) where the central path has a total curvature in \(\Omega(2^r)\). Our method is to tropicalize the central path in linear programming. The tropical central path is the piecewise-linear limit of the central paths of parameterized families of classical linear programs viewed through logarithmic glasses. The lower bound for the classical curvature is obtained by developing a combinatorial concept of a tropical angle.

Mercredi 21 septembre Anna Ben-Hamou (LPMA) Temps de mélange de marches aléatoires sur des graphes aléatoires Dans cet exposé, nous nous intéresserons à des marches aléatoires sur des graphes aléatoires à degrés prescrits. Dans un premier temps, nous considérerons la marche aléatoire sans rebroussement (« non-backtracking »), décrirons précisément son temps de mélange et établirons le phénomène de « cutoff ». Dans un deuxième temps, nous présenterons une comparaison entre les temps de mélange de la marche sans rebroussement et de la marche simple. Ces travaux ont été effectués en collaboration avec Justin Salez pour la première partie, Eyal Lubetzky et Yuval Peres pour la deuxième.

Mercredi 28 septembre Kilian Raschel (Univ. Tours) Fonctions discrètes harmoniques dans des cônes Nous nous intéresserons dans cet exposé à la notion de fonction discrète harmonique (dans des cônes). Omniprésentes en théorie des probabilités (nous évoquerons de problèmes de probabilités d'absorption, la transformation de Doob, la théorie de la frontière de Martin), elles trouvent aussi des applications en combinatoire : génération aléatoire de marches, asymptotique de nombres de marches, théorie du potentiel combinatoire. L'exposé sera articulé autour de ces différents concepts.

Mercredi 5 octobre Julien Courtiel (LIPN) Cordes terminales dans les diagrammes connexes de cordes Bien que marginalement étudiés, les diagrammes de cordes et leur énumération apparaissent dans de nombreux domaines mathématiques, tels que la théorie des champs quantiques, la théorie des noeuds, la génération aléatoire de graphes, ou la bio-informatique. Les résultats présentés dans cet exposé, qui proviennent d'une collaboration avec Karen Yeats (anciennement à SFU, Vancouver), s'inscrivent dans le cadre de la théorie quantique des champs. En effet, certaines équations de Dyson-Schwinger admettent des solutions pouvant être définies en termes de diagrammes connexes de cordes couplés avec un paramètre particulier : les cordes terminales.
Nous étudierons quelques statistiques liées à ces cordes terminales : leur nombre asymptotique, la position de leur première apparition, etc. Nous établirons les lois limites de ces variables et montrerons les applications physiques. Nous expliquerons également pourquoi les techniques classiques de combinatoire ne peuvent être directement appliquées et quelle approche nous avons empruntée pour contourner ce problème.

Mercredi 12 octobre Séance participative (Viviane Pons)

Mercredi 19 octobre Séance participative (Vincent Pilaud)

Mercredi 26 octobre Mathias Lepoutre (LIX) Diagrammes ouverts au service des marches On s'intéresse à deux problèmes énumératifs auxquels manquait une preuve bijective. Ces deux problèmes, le premier proposé par Bousquet-Mélou et Mishna en 2010 et le deuxième proposé par Burrill, Courtiel, Fusy, Melczer et Mishna en 2015, consistent à apporter des preuves bijectives à des résultats analytiques portant sur certains types de marches du plan.
La similarité de ces deux problèmes nous amène à emprunter une démarche commune qui consiste à retirer les arcs ouverts de la représentation par diagrammes définies par Chen, Deng, Du, Stanley et Yan en 2005, pour se ramener à des excursions sous-diagonales marquées.
La résolution des problèmes initiaux nous amène à donner des preuves bijectives de plusieurs autres résultats portant sur des chemins non-intersectant, en passant notamment par les forêts de Schnyder et les orientations bipolaires.
Travail en commun avec Marni Mishna, Éric Fusy et Julien Courtiel.

Mercredi 16 novembre Lucas Gerin (CMAP) Permutations séparables et arbres aléatoires On s'intéresse à une certaine famille de permutations avec « contraintes » : elles évitent des motifs fixés. Lorsque l'on simule une telle permutation, il semble apparaître un phénomène fractal, le but de cet exposé est d'expliquer ceci en établissant une connexion entre ces permutations et des (grands) arbres aléatoires. Cette connexion a de nombreuses conséquences combinatoires. (Travail en commun avec F.Bassino, M.Bouvel, V.Féray, A.Pierrot).

Mercredi 23 novembre Christina Goldschmidt (Oxford) Se garer sur un arbre Le but de cet exposé est l'étude d'une extension des fonctions de parking, introduite par Lackner et Panholzer. Supposons d'abord que l'on prend un arbre enraciné aléatoire uniforme avec étiquettes dans \([n] := \{1,2,...,n\}\) et arêtes orientés vers la racine. Chaque noeud de l'arbre a la place pour une voiture. Un nombre \(m \le n\) de voitures arrivent, une par une, et la voiture \(i\) souhaite se garer au noeud \(S_i\), où \(S_1, S_2, ..., S_m\) sont des variables aléatoires uniformes dans \([n]\). Si une voiture souhaite se garer à une place déjà occupée, alors elle suit l'unique chemin orienté vers la racine jusqu'au premier moment où elle rencontre une place libre (dans ce cas elle s'y gare) ; si elle n'en trouve pas, elle quitte l'arbre. Soit \(A_{n,m}\) l'événement que toutes les voitures trouvent des places dans l'arbre. Lackner et Panholzer ont démontré (en utilisant des méthodes de la combinatoire analytique) qu'il existe une transition de phase dans ce modèle. Soit \(m = [\alpha n]\) pour \(\alpha \in (0,1)\). Alors si \(\alpha \le 1/2\) on a \(P(A_{n,m}) \frac{\sqrt{1-2\alpha}}{1-\alpha}\), tandis que si \(\alpha > 1/2\) on a \(P(A_{n,m}) \to 0\). (En fait, ils démontrent des comportements asymptotiques bien plus fins en \(n\) pour \(\alpha \le 1/2\)). Dans cet exposé, je donnerai une explication probabiliste de ce phénomène, et une preuve alternative en utilisant la méthode « objectif » d'Aldous et Steele. S'il y a assez de temps à la fin, je discuterai quelques généralisations. Travail en commun avec Michał Przykucki (Oxford).

Mercredi 30 novembre Amandine Véber (CMAP) Arbres généalogiques de populations sexuées On présentera différents résultats sur un modèle simple de pédigré (i.e., de relations ancestrales) pour des populations sexuées, dans lequel chaque individu a un seul parent avec probabilité \(1-r\), ou deux parents avec probabilité \(r\), indépendamment les uns des autres. Cette situation apparaît notamment lorsqu'on retrace l'histoire généalogique de la population correspondant à une portion d'ADN qui, durant chaque reproduction, subit une « recombinaison » avec probabilité \(r\). En particulier, on verra que lorsque la taille \(n\) de la population tend vers l'infini, il faut remonter environ \((1/\ln(1+r) -1/\ln(1-r)) \ln n\) générations pour trouver un premier individu qui soit un ancêtre commun à toute la population actuelle. On donnera également un encadrement asymptotique du nombre de générations à remonter pour atteindre la première génération (dans le passé) à laquelle chaque individu est soit ancêtre de toute la population actuelle, ou ancêtre d'aucun individu au temps présent. Pour finir, on s'intéressera à quelques propriétés de ces généalogies à taille de population fixée. Travail en collaboration avec R. Sainudiin et B. Thatte.

Mercredi 7 décembre Manuel Wettstein (ETH Zürich) Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers We introduce the notion of a trapezoidal diagram of a plane straight-line graph \(G\). Loosely speaking, such a diagram encodes the vertical visibility relations between edges and vertices of \(G\). We study the number of such diagrams if the graphs \(G\) are either (a) perfect matchings or (b) triangulations. We give bijections to (a) 3-dimensional balanced bracket expressions and (b) a subset of indecomposable such expressions. While the former corresponds to a well-known 3-dimensional generalization of Catalan numbers, the latter gives rise to a previously unknown integer sequence which we call prime Catalan numbers. Exponential growth rates of both sequences can then be determined. A connection between the resulting diagrams (b) and so called upward triangulations will be discussed briefly.

Mercredi 14 décembre Julien David (LIPN) Génération aléatoires d'automates non-déterministes « intéressants » Les automates finis sont le modèle de calcul le plus simple de la hiérarchie de Chomsky-Schützenberger. Ces machines à états finis reconnaissent les langages rationnels, appréciés pour leur propriétés de clôtures, souvent calculable en temps polynomial. Un automate déterministe (définition simplifiée pour ce résumé) est un automate pour lequel pour tout état, pour une action donnée, il existe au plus un état d'arrivée. Pour tout automate non-déterministe, il existe un automate déterministe qui reconnaît le même langage. L'opération permettant de calculer cet automate, appelée déterminisation, a un coût exponentiel dans le pire des cas.
La génération aléatoire d'objets combinatoires est un outil puissant pour conduire des études expérimentales sur les propriétés moyennes et limites des objets engendrés, ainsi que sur les algorithmes qui s'y appliquent. Si plusieurs solutions efficaces existent pour engendrer des automates déterministes aléatoirement, la question même d'un modèle intéressant se pose pour les automates non-déterministes. Je proposerai donc un ensemble de modèles et une solution efficace pour ce problème.
Aucun prérequis n'est nécessaire pour cet exposé.