Séminaire de l'Équipe Modèles Combinatoires - 2015
Mercredi 7 janvier
Thibault Manneville
(LIX)
Éventails de compatibilité pour les graphes associaèdres
Les associaèdres sont des polytopes classiques qui ont été généralisés dans diverses directions. Dans le cadre des algèbres amassées de type fini, F. Chapoton, S. Fomin et A. Zelevinsky ont en particulier construit des associaèdres généralisés, dont l'associaèdre classique est celui de type A. Leur construction a été revisitée et étendue par F.Santos dans ce dernier cas. Ces réalisations reposent essentiellement sur la construction d'un éventail simplicial complet à partir d'un degré de compatibilité entre les variables d'amas. Dans cet exposé, on s'intéresse aux graphes associaèdres de M. Carr et S. Devadoss, qui contiennent également d'autres polytopes classiques tels que les cycloèdres et les permutaèdres. Je présenterai une réalisation des graphes associaèdres en tant qu'éventails simpliciaux complets à partir d'un degré de compatibilité entre les tubes d'un graphe.
Travail en commun avec Vincent Pilaud (CNRS & LIX).
Mercredi 14 janvier
Sophie Morier-Genoud
(IMJ)
\(SL_2(\mathbb{Z})\)-pavages et graphe de Farey
Les \(SL_2\)-pavages sont des matrices infinies dans lesquelles tous mineurs \(2 \times 2\) d'entrées adjacentes valent \(1\). Cette notion étend naturellement la notion de « frise » introduite et étudiée par Coxeter et Conway au début des années 70. Les pavages et les frises de nombres entiers ont des propriétés combinatoires remarquables. En particulier les frises entières sont en bijection avec les triangulations de polygones. On revisite ce résultat à l'aide de chemins dans le graphe de Farey et on l'étend au cas des pavages.
Mercredi 21 janvier
Séance participative (Viviane Pons)
Mercredi 11 février
Matthieu Josuat-Vergès
(IGM)
Des sous-algèbres de l'algèbre des descentes, basées sur les séquences alternantes des permutations
Etant donné une permutation vue comme une suite \(\sigma(1),\sigma(2),...\), on peut y voir des séquences croissantes d'éléments voisins, alternant avec des séquences décroissantes d'éléments voisins. On les appelle séquences alternantes et c'est le nombre total de séquences qui nous intéresse. Divers travaux d'énumération ont été faits, mais ici on a une approche algébrique: on définit des sous-algèbres
de l'agèbre du groupe symmétrique (en fait, de l'algèbre des descentes), en regroupant les permutations selon le nombre de séquences alternantes. Les preuves sont partiellement combinatoires et bijectives (existence de sous-algèbres) et partiellement algèbrique (commutativité).
Mercredi 18 février
Séance participative (Alin Bostan, Florent Hivert)
Mercredi 25 février
Séance participative (Aram Dermenjian)
Mercredi 4 mars
Florent Hivert
(LRI)
Monoide semi-plaxique
On s'intéresse à la classe des monoïdes dits de type plaxique qui possèdent les propriétés de compatibilité avec la standardisation et avec la restriction aux intervalles. En effet, par passage au quotient dans l'algèbre des fonctions quasi symétriques libres (algèbre de Hopf des permutations de Malvenuto-Reutenauer), ils donnent naissance à des algèbres de Hopf intéressantes. Cette situation possède plusieurs exemples importants :
- le monoïde plaxique lui-même qui fabrique l'algèbre des tableaux dont l'image commutative est l'algèbre des fonctions symétriques, ce qui permet de prouver la règle de Littlewood-Richardson;
- le monoïde sylvestre qui construit l'algèbre des arbres binaires de Loday-Ronco;
- le monoïde hypoplaxique qui construit les fonctions quasi symétriques et symétriques non commutatives.
D'autre part, Priez a montré que l'intersection de deux monoïdes de type plaxique est encore de type plaxique.
Dans cet exposé, je présenterai un travail en cours sur l'intersection des monoïdes plaxique et sylvestre. Le résultat principal est le suivant : pour toute classe de permutations, il existe un ordre partiel dont la classe est exactement l'ensemble des extensions linéaires. Ces ordres sont des objets intermédiaires entre les tableaux et les arbres binaires de recherche; ils sont construits grâce à un algorithme d'insertion. La preuve de ce résultat se fait en étudiant un système de réécriture non pas sur les mots, mais sur les ordres partiels eux-mêmes.
Mercredi 11 mars
Steve Oudot
(INRIA)
Reflections in quiver and persistence theories
Reflections are among the classical operations used in quiver theory to transform a given quiver \(Q\) into another quiver \(Q'\). The nice feature of such a reflection is to be associated with a functor mapping the representations of \(Q\) into representations of \(Q'\). This is interesting in the context of the classification of quiver representations, where decompositions of representations of \(Q\) can be transferred to decompositions of representations of \(Q'\). This principle has been applied with success in the past, to prove Gabriel's theorem and some of its extensions. In this talk I will draw a connection between reflection functors and the so-called « diamond principle » from persistence theory, then I will present two recent contributions to persistence which are based on the same kind of ideas.
Mercredi 18 mars
Séance participative (Vincent Pilaud)
Mercredi 25 mars
Arnaud de Mesmay
(IST, Autriche)
Embeddability of \(2\)-complexes into \(3\)-manifolds
The study of embedded graphs, be it into the plane or into surfaces, is one of the cornerstones of graph theory, as is exemplified by their importance in the design of algorithms or in structural results a la Robertson-Seymour.
On the other hand, embeddings of hypergraphs, or equivalently simplicial complexes, are still very poorly understood. In a recent breakthrough, Matousek, Sedgwick, Tancer and Wagner showed that deciding embeddability of complexes into \(\mathbb{R}^3\) is decidable, and this talk addresses the adjacent problem of deciding whether a \(2\)-dimensional simplicial complex embeds in a \(3\)-manifold. This leads to two very different questions depending on whether we allow the target space to be any manifold or if we fix a manifold in the input. In the first case, using tools from graph drawing, we provide a polynomial-time algorithm for a subclass of complexes; in the second case we prove that the problem is NP-hard.
Based on joint work with Uli Wagner.
Mercredi 1 avril
Maciej Dolega
(LIAFA)
A bijection for rooted maps on general surfaces
One of the major bijective results in the area of enumeration of maps and in the area of studying uniform random maps is the approach initiated by Cori and Vauquelin and extended by Chapuy, Marcus and Schaeffer which treats rooted orientable maps of genus \(g\). We extend their bijection for rooted maps drawn on any surface (orientable or non-orientable). It allows us to prove several results concerning asymptotic behavior of large maps on general surfaces as well as enumerative properties of them. This is a joint work with Guillaume Chapuy.
Mercredi 8 avril
Lucas Gerin
(CMAP)
Processus d'Hammersley discrets et pseudo-sous-suites croissantes
A la fin des années 60, Hammersley a introduit un processus à temps et espace continus pour étudier le comportement de la plus longue sous-suite croissante d'une permutation aléatoire. Plus récemment, deux variantes discrètes de ce processus ont été introduites, ces variantes comptent des objets semblables à des sous-suites croissantes. En étudiant de près les mesures stationnaires de ces processus nous unifions ces résultats et donnons quelques nouvelles conséquences.
(Travail en commun avec A.-L.Basdevant, N.Enriquez, J.-B.Gouéré)
Mercredi 15 avril
Xavier Goaoc
(LIGM)
Autour des limites de types d'ordre
J'expliquerai comment des idées tirées des « limites de graphes denses » (à la Lovasz) et des « algèbres de drapeaux » (de Razborov) permettent d'identifier certaines difficultés fondamentales dans la génération aléatoire uniforme de types d'ordre, des structures combinatoires associées à des ensembles de points du plan. L'exposé se veut introductif et ne supposera aucune connaissance des objets sus-mentionnés.
Mardi 21 avril
Séminaire commun CMAP/CMLS/LIX
Michael Joswig
(TU Berlin)
Lattice Polygons and Real Roots
It is known from theorems of Bernstein, Kushnirenko and Khovanskii from the 1970s that the number of complex solutions of a system of multivariate polynomial equations can be expressed in terms of subdivisions of the Newton polytopes of the polynomials. For very special systems of polynomials Soprunova and Sottile (2006) found an analog for the number of real solutions. In joint work with Günter M. Ziegler we could give a simple combinatorial formula and an elementary proof for the signature of foldable triangulation of a lattice polygon. Via the Soprunova-Sottile result this translates into lower bounds for the number of real roots of certain bivariate polynomial systems. We also mention computational results (with Benjamin Assarf and Andreas Paffenholz) as well as results on products of polytopes (with Niko Witte).
Mercredi 22 avril
Séance participative (Aram Dermenjian, Thibault Manneville)
Mercredi 6 mai
Pierre-Guy Plamondon
(Orsay)
Comptage de frises en type Dynkin
Dans les années 70, Conway et Coxeter ont étudié certaines suites d'entiers définies récursivement, nommées « frises » pour souligner leur étonnante périodicité. En 2000, Fomin et Zelevinsky ont développé une théorie algébrique, celle des « algèbres amassées », qui permet une vaste généralisation de la notion de frise.
Dans cet exposé, nous nous intéresserons à une généralisation d'un résultat de Conway et Coxeter : la détermination du nombre de frises d'un type donné. (Il s'agit d'un travail commun avec Bruce Fontaine).
Mercredi 13 mai
Frédérique Bassino
(LIPN)
Propriétés statitistiques d'un sous-groupe aléatoire du groupe libre
Soit \(A\) un alphabet fini. Le groupe libre \(F(A)\) est l’ensemble des mots réduits composés de lettres de \(A\) et d’inverses (formels) de lettres de
\(A\). Dans cet exposé, on montrera comment étudier par des méthodes combinatoires certaines propriétés algébriques d’un sous-groupe aléatoire finiment engendré de \(F(A)\). On comparera différentes distributions de probabilités assez naturelles sur ces sous-groupes.
Mercredi 20 mai
Anne-Sophie Gleitz
(Université de Caen Basse-Normandie)
Algèbres de lacets quantiques aux racines de l'unité et algèbres amassées généralisées
L'algèbre de lacets quantique \(U_q^{}(L\mathfrak{sl}_2)\) se spécialise à une racine de l'unité \(\varepsilon\), pour obtenir l'algèbre \(U_\varepsilon^{\mathrm{res}}(L\mathfrak{sl}_2)\). Dans l'esprit des travaux de Hernandez et Leclerc sur \(U_q^{}(L\mathfrak{g})\) (2013), on démontre que l'anneau de Grothendieck d'une sous-catégorie tensorielle \(\mathcal{C}_{\varepsilon^{\mathbb Z}}\) des représentations de dimension finie de \(U_\varepsilon^{\mathrm{res}}(L\mathfrak{sl}_2)\), est isomorphe à une algèbre amassée généralisée \(\mathcal A_{l-1}\) de type \(C_{l-1}\) (où \(l\) est l'ordre de \(\varepsilon^2\)). De plus, l'isomorphisme d'anneaux ainsi construit fait correspondre la base des classes des modules simples à celle des monômes de variables d'amas multipliés par les polynômes de Tchebychev en l'unique coefficient de \(\mathcal A_{l-1}\). En particulier, les variables d'amas sont identifiées aux classes des modules de Kirillov-Reshetikhin qui restent simples après la spécialisation \(q=\varepsilon\).
Une conjecture est également formulée pour \(U_\varepsilon^{\mathrm{res}}(L\mathfrak{sl}_3)\) et démontrée dans le cas \(l=2\), où l'on exhibe une algèbre amassée généralisée de type \(G_2\).
Mercredi 27 mai
Éric Balandraud
(IMJ)
Une introduction à la combinatoire additive
En dehors des résultats les plus connus de théorie additive des nombres, que sont le théorème de Waring ou la conjecture de Goldbach, de nombreux résultats ont été développés dans les groupes finis, groupes abéliens. En particulier les théorèmes de Cauchy-Davenport ou d'Erdös-Ginzburg-Ziv se trouvent être les bases de nombreux développements combinatoires. On parle maintenant plutôt de Combinatoire additive.
Sans présenter beaucoup de preuves, je vous propose une introduction à ces résultats et questions de nature additive dans les groupes, des premiers résultats cités au dessus jusqu'à des récents. J'essaierai de donner une idée des diverses méthodes impliquées dans ces travaux.
Mercredi 10 juin
Vincent Jugé
(LIAFA)
Comptage des tresses et des laminations
Les groupes de tresses sont des objets qui apparaissent dans des contextes à la fois algébriques et géométriques. D'un côté, les groupes de tresses sont des groupes finiment engendrés, qui ont été à l'origine de la notion de structure automatique d'un groupe ; de l'autre, ce sont également des groupes d'isotopie de disques épointés, ce qui donne lieu à des représentations graphiques naturelles des tresses : les laminations du disque. Les approches algébrique et géométrique donnent alors naissance à différentes notions de complexité des tresses. Nous étudierons plusieurs d'entre elles, en particulier vis-à-vis de problématiques de comptage : quelle est la complexité de telle tresse, et combien y a-t-il de tresses de telle complexité ?
Mercredi 17 juin
Alexandre Nolin
Préconditionnement par arbre couvrant
La résolution de systèmes linéaires associés à une matrice symétrique semi-définie positive est un problème courant en simulation et dans certains calculs, comme l'estimation des valeurs propres de telles matrices. Or ce type de matrice émerge naturellement lorsqu'on s'intéresse à des graphes, que l'on peut représenter par leur matrice Laplacienne. Cette équivalence entre graphe et matrice permet l'étude de certaines propriétés combinatoires sous un angle algébrique. Inversement, on peut montrer que certaines matrices associées à des sous-graphes d'un graphe G sont de bonnes approximations (au sens de leurs spectres) de la matrice associée à G, ce qui permet de conditionner le système linéaire initial de façon à accélérer sa résolution. Dans cet exposé, nous nous intéresserons aux propriétés des matrices d'arbres couvrants d'un graphe, et de l'efficacité pratique de légères variations de ces objets.
Lundi 22 juin
Erik Slivken
(UC Davis)
Pattern-avoiding permutations close to the diagonal
We describe shape results for the class of permutations avoiding the monotone and skew monotone patterns respectively. Permutations avoiding the monotone pattern \([k+1,... 2,1]\) can be viewed as the union of \(k\) increasing sequences. We show that with high probability, each sequence must lie close to the diagonal (when viewing the permutation matrix). We also obtain similar results for the class of permutations avoiding the skew-monotone pattern. Finally, using a connection with beta\((0,1)\)-trees, we show \(4213\)-avoiding permutations are close to the diagonal provided the number of left to right maxima are numerous enough
This is joint work with Benjamin Fineman, Christopher Hoffman, and Douglas Rizzolo.
Lundi 21 et mardi 22 septembre
Journées du GT Combinatoire Algébrique du GDR IM
Orateurs :
- Bérénice Delcroix-Oger (Institut de Mathématiques de Toulouse)
- Arthur Nunge (LIGM, Université de Marne-la-Vallée)
- Zakaria Chemli (LIGM, Université de Marne-la-Vallée)
- François Viard (ICJ, Université Lyon 1)
- Nicolas Thiéry (LRI, Université d'Orsay)
- Grégory Chatel (LIGM, Université Marne-la-Vallée)
- Thibault Manneville (LIX, École Polytechnique)
- Mathias Pétréolle (ICJ, Université Lyon 1)
- Ammar Aboud (LITIS, Université de Rouen)
- Anne-Sophie Gleitz (IRMA, Université de Strasbourg)
- Ange Bigeni (ICJ, Université Lyon 1)
- Henri Mühle (LIAFA, Université Paris 7)
Les informations détaillées sont ici.
Mercredi 30 septembre
Isabel Hubard
(UNAM)
Chiral symmetry in polytopes
The term «chiral» comes from the greek «kheir», which means hand. Objects with chiral symmetry are those that differ from their mirror image. In this talk the concept of an abstract polytope will be introduced. Chiral (abstract) polytopes will be presented as those having maximum possible rotational symmetry, but are not «reflexible». We shall see that chiral polytopes seem hard to come by, but present some examples of them, as well as some ideas for a constructing chiral polytopes of every rank (or dimension). We´ll also present some interesting algebraic, combinatorial and geometrical problems in the subject.
Mercredi 7 octobre
Jérémie Bettinelli
(LIX)
Une bijection pour les cartes non-orientables
Récemment, Chapuy et Dolega ont trouvé une bijection entre les quadrangulations biparties d'une surface nonorientable et les cartes à une face de la même surface, dont les sommets sont étiquetés. Cette bijection généralise la bijection de Chapuy, Marcus et Schaeffer qui se concentrait sur les surfaces orientables et qui généralisait la fameuse bijection de Cori, Vauquelin et Schaeffer entre les quadrangulations planes et les arbres bien étiquetés.
Au cours de cet exposé, nous allons un pas plus loin en présentant une bijection entre les cartes générales d'une surface nonorientable donnée et certaines cartes étiquetées à une face de la même surface. Cette bijection généralise à la fois la bijection de Chapuy et Dolega et celle de Bouttier, Di Francesco et Guitter pour les cartes planes générales.
Mercredi 14 octobre
François Viard
(ICJ)
Une extension de l'ordre faible sur les groupes de Coxeter
Quand on étudie l'ordre faible sur un groupe de Coxeter \(W\), on a en général deux configurations distinctes selon la cardinalité de \(W\). Si \(W\) est fini, alors l'ordre faible sur \(W\) est un treillis complet, ayant un élément maximal et dont les chaines maximales sont encodées par un objet combinatoire bien connu : les décompositions réduites de l'élément maximal. Si par contre \(W\) est infini, on n'a alors plus qu'un semi-treillis inférieur, et donc pas d'élément maximal. Cette différence de comportement, ainsi que d'autres constats portant sur une généralisation des treillis cambriens aux cas des groupes de Coxeter infini dut à Reading et Speyer, nous amène à la question suivante : est-il possible d'étendre l'ordre faible sur les groupes de Coxeter infini, de manière à obtenir un poset ayant des propriétés équivalentes à celles du cas fini ?
C'est justement l'objet de deux conjectures de Matthew Dyer, qui proposent un candidat pour une telle extension utilisant les systèmes de racines. Dans cet exposé, je présenterai un angle d'approche nouveau de ces conjectures, et expliquerai comment on peut construire des extensions de l'ordre faible ayant presque toutes les propriétés conjecturalement attachées aux extensions de Dyer. Si le temps le permet, je mentionnerai également une des applications possibles de ce travail concernant l'extension des semi-treillis cambriens.
Mercredi 21 octobre
Laurent Ménard
(Univ. Nanterre)
Développement asymptotique du spectre de grandes matrices aléatoires et énumeration de marches sur des graphes
Mercredi 28 octobre
Emmanuel Guitter
(IPhT)
Une étude comparée de deux ensembles de quadrangulations
Dans cet exposé, je comparerai deux ensembles statistiques de quadrangulations à bord, chacun contrôlé par deux paramètres. Dans le premier ensemble, les quadrangulations sont bicoloriées et on contrôle le nombre de sommets de chacune des deux couleurs. Dans le deuxième ensemble, on contrôle le nombre de sommets qui sont des maxima locaux pour la distance au sommet racine, et le nombre de ceux qui n'en sont pas. Chaque ensemble peut être caractérisé par ses fonctions génératrices à bord de longueur fixé ou, de manière alternative, par ses fonctions génératrices de « slices » (qui sont les tranches de carte obtenues par découpage géodésique de la quadrangulation). Je montrerai que les fonctions génératrices à bord de longueur fixé sont égales pour les deux ensembles tandis que les fonctions génératrices de slices s'obtiennent en écrivant une même quantité, soit comme fraction continue de Stieltjes pour le premier ensemble, soit comme fraction continue de Thron pour le second. J'insisterai particulièrement sur le cas moins conventionnel des fractions continues de Thron pour montrer comment obtenir de manière constructive une expression explicite des fonctions génératrices de slices du second ensemble. Il s'agit d'un travail en commun avec Éric Fusy.
Mercredi 18 novembre
Séance participative (Marie Albenque, Vincent Pilaud)
