Séminaire de l'Équipe Modèles Combinatoires - 2014
Mercredi 22 janvier Nicolas Broutin (Inria Paris-Rocquencourt) Connectivity properties of sparsified random geometric graphs Consider a graph whose vertices represent \(n\) uniform points in the unit square. One forms a geometric graph by connecting two vertices if the distance between the corresponding points is at most some visibility radius \(r\). It is well-known that for such graph to be connected with a decent probability, the average degree must be at least of order \(\log n\), which may be two much for many applications. One may sparsity the graphs as follows: let \(c\) be a positive integer, and let each vertex select independently \(c\) nodes among its neighbours to which he is allowed to keep an edge. All other edges are removed from the graph. We study the connectivity properties of such geometric graphs. In particular, we give the threshold \(c^*\) for the connectivity, and prove that the phase transition for the apparition of a giant component is explosive.
Joint work with L. Devroye and G. Lugosi.
Mercredi 5 février Justin Salez (LPMA) La convergence locale faible: un cadre pour l'étude des grands graphes Dans le régime « dilué », où le nombre d'arêtes diverge linéairement avec le nombre de sommets, il est fascinant de constater que diverses propriétés fondamentales d'un graphe sont essentiellement déterminées par sa seule géométrie locale, c'est-à-dire par l'aspect d'une boule de petit rayon autour d'un sommet typique. Nous montrerons que cette heuristique peut être formalisée à l'aide de la notion de convergence locale faible, et qu'elle permet de remplacer l'étude asymptotique des grands graphes aléatoires par l'analyse directe d'objets limites appropriés. Nous illustrerons cette approche par des résultats explicites pour divers invariants importants en théorie des graphes.
Mercredi 5 mars Mikhail Gorsky (IMJ) Les complexes des sous-mots et les mouvements de Hecke Le complexe de sous-mots est un complexe simplicial associé à un mot dans les générateurs simples d'un groupe de Coxeter fini et à un élément de ce groupe. Pour étudier les propriétés d'un tel complex, il est utile de travailler avec le 0-monoïde de Hecke. Il est obtenu à partir du groupe par le remplacement des réflexions par les projecteurs. Il y a deux types naturels des transformations de mots, qui préservent les éléments correspondants dans le monoïde : les mouvements des tresses et les 0-mouvements. Nous nous intéressons aux transformations des complexes des sous-mots induites par ces mouvements. Il se trouve que sous certaines conditions ils ont des descriptions simples dans en termes de sous-divisions des 1-simplexes et de la suspension. On espère que cela serait utile dans l'étude de l'existence des polytopes duaux des complexes des sous-mots et de leurs réalisations géometriques. Si le temps le permet, nous discuterons les liens entre les complexes associés aux mots de forme spéciale et la théorie des représentations des carquois.
PDF Mercredi 12 mars Jérémie Bouttier (IPhT) Sur la fonction à deux points des cartes et hypercartes générales Nous considérons la fonction à deux points des cartes et hypercartes générales, c'est-à-dire la série génératrice de celles ayant deux points marqués à distance prescrite. Les cartes considérées ici peuvent avoir des faces de degrés arbitraires, ce qui nécessite de nouvelles bijections. Nous obtenons des expressions exactes dans les cas suivants: cartes générales et biparties comptées selon le nombre d'arêtes, 3-hypercartes et 3-constellations comptées par leurs nombres d'hyperarêtes, et enfin cartes générales et biparties comptées à la fois par le nombre d'arêtes et par le nombre de faces.
PDF Mercredi 19 mars Thibault Manneville (LIX) Propriétés graphiques des associaèdres de graphes Les associaèdres sont des polytopes qui encodent géométriquement la combinatoire des dissections d’un polygone convexe. Différentes constructions des associaèdres mènent chacune à des généralisations différentes. Nous nous intéressons ici à l’interprétation de l’associaèdres comme un complexe simplicial défini par une certaine relation de compatibilité sur les sous-chemins d’un chemin donné. Cette définition se généralise à un graphe fini quelconque, on sait alors que le complexe obtenu est toujours polytopal, les polytopes obtenus sont alors appelés graphe-associaèdres. Certains polytopes classiques s’obtiennent de cette façon : le permutaèdre est un graphe complet-associaèdre et le cycloèdre est un cycle-associaèdre. Nous nous intéressons aux propriétés graphiques des graphe-associaèdres, c’est-à-dire aux propriétés combinatoires de leur graphe de flips. Nous présenterons certains résultats concernant leur diamètre, dont la valeur est connue pour l’associaèdre classique et le permutaèdre, ainsi que sur leur hamiltonicité, qui n’était connue que dans ces deux cas également.
PDF Mercredi 26 mars Gilles Schaeffer (LIX) Regular colored graphs of positive degree Regular colored graphs are dual representations of pure colored D-dimensional complexes. These graphs can be classified with respect to an integer, their degree, much like maps are characterized by the genus. We analyse the structure of regular colored graphs of fixed positive degree and perform their exact and asymptotic enumeration. In particular we show that the generating function of the family of graphs of fixed degree is an algebraic series with a positive radius of convergence, independant of the degree. We describe the singular behavior of this series near its dominant singularity, and use the results to establish the double scaling limit of colored tensor models.
PDF Mercredi 2 avril Sandrine Dasse-Hartaut (LIAFA) Combinatoire des tableaux escalier Les tableaux escalier sont des objets assez récents, qui permettent, entre autres, de donner une expression de la probabilité stationnaire du modèle de physique statistique appelé PASEP (Partially Asymmetric Exclusion Process). Contrairement à ce modèle, ils manquent de symétrie, et si on peut en étudier très bien certains sous-ensembles, lorsqu’on s’intéresse à l’ensemble des tableaux escalier, ce manque de symétrie pose problème. On verra comment lier certains sous-ensembles avec des arbres un peu particulier ou avec les permutations, et ce qui se passe si l’on essaie de généraliser ce qui est obtenu sur ces sous-ensembles.
PDF Mercredi 9 avril François Nunzi (LIAFA) Probabilités multivariées de jonglage On s'intéresse à différentes extensions des chaînes de Markov de jonglage introduites par Warrington. Ainsi, on généralise la construction au cas du jonglage à des hauteurs arbitraires ou avec un nombre infini de balles. Dans chacun des cas, on donne des formules produits explicites pour les probabilités stationnaires et des expressions concises pour les facteurs de normalisation. On s'intéresse également à des chaînes de Markov enrichies sur des partitions d'ensembles. Enfin, on montre que dans l'un des cas étudiés, l'état stationnaire est atteint en temps fini.
PDF Mercredi 7 mai Kilian Raschel (LMPT, Tours) Une histoire de la conjecture de Gessel Imaginons un échiquier infini dans les directions Est et Nord, et sur cet échiquier figurons-nous un roi biaisé, se déplaçant à chaque coup dans l'une des directions Est, Sud-Ouest, Ouest ou Nord-Est. Le mathématicien américain Ira Gessel conjectura en 2001 une formule pour le nombre de possibilités pour le roi, partant du coin inférieur gauche de l'échiquier, d'y revenir après un nombre fixé de coups. Depuis l'énoncé de cette conjecture, en passant par la première preuve en 2008 (utilisant de façon cruciale la puissance des ordinateurs) et jusqu'à la première démonstration purement humaine en 2013, beaucoup de chercheurs se sont confrontés à ce problème, utilisant des approches mathématiques tout à fait différentes. Dans cet exposé nous retraçons l'histoire des tentatives de preuve de la conjecture de Gessel. Il s'agit de travaux communs avec A. Bostan, G. Fayolle et I. Kurkova.
PDF Mercredi 21 mai Samuele Giraudo (LIGM, MlV) Opérades pluriassociatives Les algèbres dendriformes sont des structures remarquables en combinatoire puisqu'elles offrent un cadre pour étudier des opérations associatives relativement complexes en les séparant en deux sous-opérations plus simples. D'autre part, la théorie des opérades offre une formalisation fructueuse de la notion d'opérateurs et de leurs assemblages. L'opérade dendriforme, introduite par Loday, est une structure algébrique qui code toutes les algèbres dendriformes et dont la combinatoire fait intervenir les arbres binaires. Elle peut se construire à partir d'une opérade très simple, l'opérade diassociative, en considérant son dual de Koszul. Dans cet exposé, on présente une généralisation à un paramètre entier de l'opérade diassociative, appelée opérade pluriassociative. En considérant son dual de Koszul, on obtient une généralisation à un paramètre entier de l'opérade dendriforme dont la combinatoire fait intervenir des arbres binaires colorés. Cet exposé est organisé en deux parties : dans la première seront présentées des notions de base sur les algèbres dendriformes et les opérades pour un public non forcément familier avec ces théories. Dans la seconde, des résultats sur les opérades pluriassociatives seront expliqués.
Mercredi 28 mai Jean-Philippe Labbé (FU Berlin) En quête de réflexions totalement ordonnées À la base, les groupes de Coxeter forment une abstraction algébrique des groupes engendrés par des réflexions d'un espace vectoriel. La relative simplicité de leur définition leur permet d'être liés à une multitude d'objets combinatoires, géométriques et algébriques. Dans cet exposé, nous explorerons la notion d'ordre total de réflexions d'un groupe de Coxeter. Dans le cas fini, les relations d'ordre totales de réflexions correspondent aux mots réduits du mot le plus long et joue un rôle important dans la combinatoire des groupes de Coxeter et les objets reliés: polynômes de Kazhdan-Lusztig, complexe de sous-mots, éléments triés, etc. Dans le cas infini, elles correspondent à des mots infinis réduits permettant la construction d'un ensemble limite (souvent fractale) associée au groupe.
PDF Mercredi 4 juin Bérénice Oger (ICJ, Lyon) Arbres en boîtes et hyperarbres décorés Des sortes d'hyperarbres décorés par des espèces apparaissent dans différents articles de la littérature comme dans l'étude du groupe des automorphismes du groupe libre par C. Jensen, J. McCammond et J. Meier, ou encore dans l'étude de l'action du groupe symétrique sur l'homologie du poset des hyperarbres. Ces exemples incitent à l'étude de ces hyperarbres décorés. Après un rappel des notions d'espèces et d'hyperarbres, nous exposerons le dénombrement de ces hyperarbres par le codage de Prüfer d'une structure que nous nommerons arbres en boîte auxquelles les hyperarbres décorés sont reliés.
Mercredi 11 juin Jehanne Dousse (LIAFA) Identités de partitions du type Rogers-Ramanujan et équations aux q-différences Une partition d'un entier n est une suite décroissante d'entiers (appelés parts) dont la somme est égale à n. Les identités de Rogers-Ramanujan, découvertes en 1894 par Rogers et redécouvertes en 1917 par Ramanujan, établissent que pour tout n, le nombre de partitions de n telles que la différence entre deux parts consécutives est au moins 2 est égal au nombre de partitions de n en parts congrues à 1 ou 4 modulo 5. Plus généralement, les identités du type Rogers-Ramanujan établissent des égalités entre certains types de partitions avec des conditions de différence et des partitions avec des conditions de congruence.
Nous montrerons comment des équations aux q-différences sur les séries génératrices de certains types de partitions permettent de prouver des identités du type de Rogers-Ramanujan comme le théorème de Schur et sa généralisation aux surpartitions, le théorème d'Andrews et sa généralisation aux surpartitions ou le théorème de Siladic.
PDF Mercredi 25 juin Viviane Pons (Université de Vienne) Réalisation de \(m\)-Tamari sur les arbres Le treillis de Tamari est un structure d'ordre partiel sur des objets comptés par les nombres de Catalan. Ses réalisations les plus courantes s'expriment en termes d'arbres binaires, de chemins de Dyck ou encore de triangulations de polygones. Récemment, une généralisation de ce treillis a été introduite par Bergeron et Préville-Ratelle appelée treillis de \(m\)-Tamari et décrite sur les chemins. Nous donnons la réalisation de ces treillis sur les arbres \((m+1)\)-aires ainsi que certains résultats qui en découlent en particulier pour l'énumération des intervalles.
Mercredi 10 septembre Frédéric Chapoton (ICJ, Lyon) Comment \(q\)-compter les points dans les polytopes Sur le modèle de la théorie classique des polynômes d'Ehrhart, qui concerne le nombre de points entiers dans les polytopes avec des sommets dans \(\mathbb{Z}^d\), on présentera une version analogue de cette théorie faisant intervenir un paramètre supplémentaire \(q\). C'est en quelque sorte un \(q\)-analogue de la théorie classique, sur laquelle on retombe lorsque \(q=1\).
PDF Mercredi 17 septembre Jean-Baptiste Priez (LRI, Orsay) Monoïde de type plaxique et Algèbre de Hopf combinatoire Partant d'algèbres de Hopf définies par réalisation polynomiale: \(\textbf{FQSym}\), \(\textbf{WQSym}\), \(\textbf{PQSym}\), etc, on caractérise un type de relation définies sur le monoïde libre et permettant de quotienter ces algèbres de Hopf.
PDF Mercredi 24 septembre Pauline Sarrabezolles (CERMICS) The colourful simplicial depth conjecture Given \(d+1\) sets of points, or colours, \(S_1,\ldots,S_{d+1}\) in \(\mathbb{R}^d\), a colourful simplex is a set \(T \subseteq\bigcup_{i=1}^{d+1}S_i\) such that \(|T\cap S_i|\leq 1\), for all \(i\in\{1,\ldots,d+1\}\). The colourful Caratheodory theorem states that, if \(0\) is in the convex hull of each \(S_i\), then there exists a colourful simplex \(T\) containing \(0\) in its convex hull. Deza, Huang, Stephen, and Terlaky (Colourful simplicial depth, Discrete Comput. Geom., 35, 597--604 (2006)) conjectured that, when \(|S_i|=d+1\) for all \(i\in\{1,\ldots,d+1\}\), there are always at least \(d^2+1\) colourful simplices containing \(0\) in their convex hulls. We prove this conjecture via a combinatorial approach.
PDF Mercredi 1 octobre Vincent Pilaud (LIX) Algèbre Cambrienne J.-L. Loday et M. Ronco ont construit une algèbre de Hopf sur les arbres binaires qui peut se voir comme une sous-bigèbre de l'algèbre de M. Malvenuto et C. Reutenauer sur les permutations. Je montrerais une construction similaire sur les arbres Cambriens et quelques propriétés intéressantes de l'algèbre qui en résulte. Travail en commun avec G. Chatel.
PDF Mercredi 8 octobre Henri Mühle (Université de Vienne) SB-Labelings, Distributivity and Bruhat Order on Sortable Elements Recently, Hersh and Mészáros introduced a new class of lattices that admit a certain type of edge-labeling, called an SB-labeling. They showed that these lattices all have the property that their open intervals are either homotopic to a sphere or a ball. They showed that distributive lattices, the weak order semilattices of a Coxeter group, and the Tamari lattices admit such an SB-labeling.
We extend their work by showing that the Bruhat order on the sortable elements of a Coxeter group (in the sense of Reading) admits an SB-labeling as well. By using results of Armstrong, we extend this result to all join-distributive lattices, a class of lattices that can be regarded as the hierarchy of feasible sets of an antimatroid. Finally, we elaborate on the question for which Coxeter groups there exist Coxeter elements such that the Bruhat order on the corresponding sortable elements forms a distributive lattice. It turns out that this is the case in the so-called coincidental types \(A_n\), \(B_n\), \(H_3\) and \(I_2(k)\).
PDF Mercredi 22 octobre Axel Bacher (RISC, Linz) Loi limite d’algorithmes de rejet anticipé Nous nous intéressons aux algorithmes de génération aléatoire par rejet anticipé, tel que le « rejet florentin » (Barcucci et al., 1994), ou l’algorithme de génération aléatoire d’arbres unaires-binaires de (B., Bodini, Jacquot, 2014). Ces algorithmes sont connus pour avoir une complexité linéaire en moyenne. Nous montrons que la complexité admet une loi limite qui coïncide avec la loi dite de « Darling-Mandelbrot ». Nous donnons explicitement la densité de cette loi limite. Enfin, nous présentons d’autres objets combinatoires pouvant être engendrés aléatoirement avec de tels algorithmes.
Travail en commun avec Andrea Sportiello.
PDF Mercredi 12 novembre Frédéric Jouhet (ICJ) Autour des éléments pleinement commutatifs dans les groupes de Coxeter finis et affines Un élément d'un groupe de Coxeter est dit pleinement commutatif si deux quelconques de ses décompositions réduites se déduisent l'une de l'autre uniquement par des relations de commutation. De tels éléments apparaissent naturellement dans un contexte algébrique, car ils indexent une base de l'algèbre (généralisée) de Temperley-Lieb. Nous énumérons les éléments pleinement commutatifs selon leur longueur de Coxeter, dans les groupes finis et affines. Notre approche consiste à caractériser ces éléments à l'aide d'empilements de Viennot, que nous encodons eux-mêmes par des chemins du plan possédant d'agréables fonctions génératrices. Dans le cas fini nos travaux généralisent l'énumération exhaustive de 1998 due à Stembridge; les cas des types \(A\) et \(\tilde A\) simplifient et précisent des résultats récents de Barcucci-Del Lungo-Pergola-Pinzani et Hanusa-Jones, respectivement. Une conséquence étonnante de notre énumération est l'ultime périodicité des coefficients des fonctions génératrices dans tous les types affines. Nous donnerons une méthode pour déterminer la période exacte pour chacun d'eux, et nous pencherons enfin sur le cas particulier des involutions, dont l'énumération suivant l'indice majeur en type fini présente des propriétés intéressantes.
Cet exposé est basé sur des travaux en collaboration avec Riccardo Biagioli et Philippe Nadeau (Lyon 1).
Mercredi 3 décembre Robert Cori (LaBRI) Une interprétation des polynômes de Hall Littlewood dans le cadre du modèle combinatoire du Tas de Sable sur un graphe Le modèle combinatoire du Tas de Sable sur un graphe donne lieu à des propriétés algébriques remarquables. En effet les opérations d'éboulement définissent un groupe dont il est intéressant d'étudier les propriétés. Dans cet exposé on définit des suites d'éboulements particulières représentées par des mots de Yamanouchi. Une famille de générateurs de la sous-algèbre engendrée par ces suites possède des propriétés combinatoires intrigantes lorsqu'on se limite à des graphes particuliers: les chemins de taille \(n\) (il y a \(n\) sommets et \(n-1\) arêtes qui les relient entre eux par un seul chemin). On montre que l'énumération des façons différentes d'exprimer un élément comme un produit de générateurs de cette famille fait intervenir les polynômes de Hall Littlewood, classiques en combinatoire algébrique.
Ces résultats sont le fruit d'un travail en commun avec Pasquale Petrullo et Domenico Senato (Univertsité du Basilicate).
PDF Mercredi 17 décembre Arnau Padrol (FU Berlin) Dyck path triangulations of products of simplices and extendability The set of triangulations of the product of two simplices is an intricate combinatorial object that plays an important role in different fields of mathematics. In this talk, I will discuss recent results obtained in collaboration with Camilo Sarmiento and César Ceballos concerning the extendability problem for partial triangulations of the product of two simplices. Our proofs involve a new family of triangulations whose maximal cells are indexed by Dyck paths. These results have an interpretation in terms of arrangements of tropical (pseudo)hyperplanes that provides tropical analogues to classical results in oriented matroid theory.

Valid XHTML 1.0 Strict CSS Valide !