Séminaire de l'Équipe Modèles Combinatoires - 2015
PDF 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)
PDF 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)
PDF 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 : 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.
PDF 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.
PDF 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.
PDF 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).
PDF 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.
PDF 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\).
PDF 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.
PDF 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é ?
PDF 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 : Les informations détaillées sont ici.
PDF 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.
PDF 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.
PDF 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
PDF 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)
Mercredi 25 novembre Séance participative (Henri Mühle)

Valid XHTML 1.0 Strict CSS Valide !