Résumé: In the 1980's, Gessel and Viennot popularized a determinantal method for counting non-intersecting lattice paths. I present an extension of this method to counting non-intersecting cycle systems (disjoint unions of cycles) in a particular type of directed graph we call a hamburger. THis "Hamburger Theorem" gives a purely combinatorial proof of a determinantal formula for the number of domino tilings of an Aztec diamond, as first introduced by Brualdi and Kirkland in 2003. I present this argument and expand upon ghe Hamburger Theorem's applications to domino tilings of other regions of interes.
Résumé: The partially asymmetric exclusion process (PASEP) is an important model from statistical mechanics which describes a system of interacting particles hopping left and right on a one-dimensional lattice of n sites. It is partially asymmetric in the sense that the probability of hopping left is q times the probability of hopping right. There are also parameters alpha and beta describing the probabilities that particles enter the system from the left and leave from the right. In this talk we will describe a surprising connection between the PASEP and the combinatorics of certain 0-1 tableaux called permutation tableaux. Namely, we prove that in the long time limit, the probability that the PASEP is in a particular configuration tau is given by a generating function for permutation tableaux of shape lambda(tau), enumerated according to three statistics.
There should be connections between the PASEP model and total positivity for the Grassmannian (via work of Postnikov), and to Stanley's theory of differential posets.
This is joint work with Sylvie Corteel.
Résumé: Le but de cet exposé est triple: introduire la notion de processus d'exclusion (partiellement ou totalement) asymétrique (PASEP ou TASEP, "partially or totally asymmetric exclusion process"), introduire la notion de "tableaux à permutation" ("permutation tableaux") et résoudre un problème ouvert posé par Einar Steingrimmson et Lauren Williams (math.CO/0507149, JCTA à paraître) relativement à certains de ces tableaux dénombrés par les nombres de Catalan.
Le modèle d'exclusion asymétrique décrit la diffusion de particules le long d'une chaîne de n cases avec la condition que chaque case ne peut être occupée que par au plus une particule. Les particules rentrent et sortent à chaque extrémité, sautent sur une des cases immédiatement voisines, chaque transition possible étant décrite par certaines probabilités. Ce modèle simple présente de très riches propriétés et a été beaucoup étudié par les physiciens, notamment par Bernard Derrida et ses coauteurs, donnant une approche algébrique pour calculer les probabilités du régime stationnaire. Plus récemment des liens profonds sont apparus avec la combinatoire (travaux de Shapiro-Zeilberger, Duchi-Schaeffer, Brak-Essam, Corteel-Brak- Rechnitzer-Essam, Corteel-Williams) et la théorie des polynômes orthogonaux.
Les "tableaux à permutations" sont simplement des diagrammes de Ferrers dont les cases sont remplies avec des 0 et des 1, soumis à certaines conditions. Ils ont été introduit (sous une forme un peu plus générale) par Alex Postnikov dans le contexte de sa théorie des "web graphs" et des "cellules totalement positives des Grassmaniennes". Ces tableaux sont en bijection avec les permutations et une bijection due à Postnikov est décrite (sous une forme simplifiée) par E.Steingrimsson et L.Williams dans l'article math.CO/ 0507149. Sylvie Corteel et Lauren Williams ont donné une interprétation des probabilités stationnaires en termes de ces "tableaux à permutations" (math.CO/0602109) (ceci fera l'objet de l'exposé de L. Williams au GT du 23 Juin).
Dans cet exposé, je me restreindrai au cas particulier des particules allant toujours vers la droite, avec probabilité d'entrée et sortie égales à 1. Dans ce cas, l'interprétation de Corteel-Williams est en termes de certains tableaux comptés par les nombres de Catalan (que je propose d'appeler "tableaux de Catalan"). Steingrimmson et Williams ont montré que ces tableaux étaient en bijection avec une classe de permutations définie par certain motif interdit et ont posé le problème de trouver une bijection avec des objets "classiques" du jardin des objets dénombrés par les nombres de Catalan. Je décrirai une bijection entre ces tableaux de Catalan et les arbres binaires. Cette bijection permet aussi de relier l'interprétation combinatoire des probabilités stationnaires données par Corteel-Williams à une autre donnée par Shapiro et Zeilberger en termes de paires de chemins (c'est à dire les classiques polyominos parallélogrammes). D'autres solutions au problème de Steigrimsson-Williams ont aussi été donné très récemment par Alexander Burstein, Sylvie Corteel, Niklas Eriksen et Astrid Reifegerste.
Résumé: Cet exposé complète la petite école sur les fonctions symétriques et est aussi une (brève et pédagogique) introduction à la théorie des polynômes de Schubert. Ces polynômes (indexés par les permutations) ont été introduits par Lascoux et Schützenberger et forment actuellement un domaine actif de la combinatoire algébrique. Une interprétation géométrique a été donnée par Fomin et Kirillov avec certaines configurations de chemins.
Nous considérons la classe bien connue des permutations sans décroissance de longueur 3 (c'est-à-dire évitant le motif 321) et énumérée par les nombres de Catalan. Dans ce cas particulier, les polynômes de Schubert stables (appelés aussi partie symétrique des polynômes de Schubert) sont des fonctions de Schur gauches. Ces fonctions peuvent aussi être interprétées par des configurations de chemins provenant de l'identité de Jacobi-Trudi (ou de sa duale). Nous montrons le lien entre ces configurations et celles introduites par Fomin et Kirillov.
Ces considérations géométriques nous permettront de faire une révision de plusieurs concepts algébrico-combinatoires sous-jacents: base de l'algèbre de Temperley-Lieb, commutations et empilements de dominos, décomposition réduite d'une permutation.
Enfin, si le temps le permet, je propose une surprise: un lien méconnu avec d'autres configurations de chemins introduites par Lalonde et comptées par... les nombres de matrices à signes alternants.
Résumé: Cet exposé est la suite de mon exposé sur les chemins pour les fonctions de Schur et polynômes de Schubert. La partie essentielle est relative à la classe des permutations sans décroissance de longueur trois, c'est-à-dire évitant le motif 321.
Je reprendrai donc cette classe de permutations dénombrées par les nombres de Catalan et donnerai diverses bijections et caractérisations en termes de diagrammes de Ferrers gauches (ou polyominos parallélogrammes), de décompositions réduites, d'empilements de dominos et de bases d'algèbre de Temperley-Lieb.
Enfin je reprendrai les configurations de chemins de Lalonde associées à toutes permutation évitant le motif 321. Ces configurations sont en bijection avec les partitions planes descendantes introduites par Andrews et sont énumérées par les fameux nombres de matrices à signes alternants.
Résumé: We consider the class of permutominoes, i.e. a special class of polyominoes which are determined by a pair of permutations having the same size. We give a characterization of the permutations associated with convex permutominotes, and then we enumerate various classes of convex permutominoes, including parallelogram, directed-convex, and stack ones.
Résumé: Nous nous pencherons sur les relations de similarités non singulières étudiés par T.Fine. Ces relations binaires, symmetriques et reflexives opérants sur [n], sont telles que tout élément doit être en relation avec au moins un autre. Celle-ci sont énumérées par une formule, due à D.G.Roger, faisant intervenir la distribution alpha des Catalans.
Nous étendrons cette définition à l'aide de la relation de congruence-modulo. Nous fournirons ensuite un arbre de génération pour ces objets étendus ainsi qu'une formule d'énumération. Par la suite, nous prouverons, à l'aide de la méthode des arbres de génération, que deux cas particuliers sont en bijection avec des ensembles de permutations à motifs exclus.
Résumé: On s'intéresse aux cartes boisées, c'est-à-dire, les cartes planaires enracinées dont un arbre couvrant est distingué. Les cartes boisées sont en bijection avec les mélanges de deux mots de parenthèses ce qui permet de les compter facilement. Mullin remarqua que le nombre de cartes boisées à n arêtes est CnCn+1, où Cn est le nème nombre de Catalan.
Cette propriété énumérative suggère une décomposition des cartes en deux arbres de tailles respectives n et n+1. En 1986, Robert Cori, Serge Dulucq et Xavier Viennot définirent une bijection entre mélanges de mots de parenthèses et paires d'arbres. Cependant, l'interprétation de cette bijection en termes de cartes ne fut pas comprise.
Durant cet exposé, je définirai une bijection entre cartes boisées et les couples formés d'un arbre et d'une partition non-croisée. Cette bijection passe par une correspondance entre les arbres couvrants et certaines orientations. J'essaierai également de donner une idée de l'isomorphisme avec la bijection de Cori, Dulucq et Viennot.
Résumé: Cet exposé comprend trois parties. Tout d'abord une partie pédagogique. Je rappellerai brièvement quatre façons de présenter cette correspondance entre permutations et paires de tableaux de Young de même forme: l'algorithme original avec les insertions à la Schensted, la forme géométrique introduite par l'orateur, l'algorithme "local" sur une grille dû à Fomin et le "jeu de taquin" introduit par notre "bon maître" M.P. Schützenberger. Je montrerai les rapports entre ces quatre présentations en dégageant quelques outils classiques de base: les transpositions de Knuth et la théorie de Greene sur les familles de sous-suites k-croissantes et k-décroissantes.
Dans la deuxième partie j'introduirai la notion de (p,q)-grille d'une permutation et je donnerai des idées pour mes tentatives de "symétriser" la théorie de Greene, c'est-à-dire faire jouer un rôle symétrique aux lignes et colonnes des tableaux de Young associés à la permutation. Ceci conduit à une conjecture pouvant conduire à une cinquième forme de la correspondance de Robinson-Schensted.
Enfin, si le temps le permet, j'évoquerai comment des algorithmes classiques comme le "jeu de taquin" et l'involution de Schützenberger définissant le dual d'un tableau peuvent aussi être décrits par un algorithme "local" sur une grille. On retrouve alors la célèbre règle de Littlewood-Richardson.
Cet exposé est la suite logique du précédent, mais peut être suivi indépendamment.
Résumé: Sergey Fomon et Richard Stanley ont introduit la théorie des ensembles partiellement ordonnés différentiels ("differential posets"), et plus généralement des "graphes duaux gradués". Il s'agit d'opérateurs vérifiant certaines relations de commutation. Le cas le plus simple est la relation de Heisenberg UD = DU + I. Cette théorie permet de retrouver la correspondance de Robinson-Schensted entre permutations et paires de tableaux de Young de même forme, et plus généralement d'unifier diverses correspondances analogues.
Je me propose d'exposer le B.A.-BA de cette approche algébrique, en suivant principalement l'approche de Fomin dans le cas fondamental du treillis de Young (les diagrammes de Ferrers ordonnés par inclusion). Nous passerons des commutations à des choses sympathiques pour la combinatoire bordelaise: règles de réécriture, puis un algorithme sur une grille défini par des règles locales.
Ensuite je montrerai que cet algorithme "local" est équivalent à celui de Robinson-Schensted en utilisant la construction géométrique avec "ombres et lumières" introduite par l'orateur il y a bien longtemps. La simplicité de la preuve nous autorisera à faire un coup de pub pour cette construction géométrique.
Résumé: On racontera un travail (modeste, et en cours...) parti de l'étude d'une classe de permutations motivée par des raisons (obscures) de géométrie algébrique. On se contentera de les caractériser (quelques motifs exclus), de les compter (quelques séries algébriques) et de souligner les liens (que dis-je, quelques liens) avec une famille d'animaux qui étendent les animaux dirigés, et les empilements correspondants.
Résumé: C'est un travail en commun avec J.-M. Labarbe (Versailles)
On s'intéresse à quatre familles de trajectoires formées de pas +1 et -1 commençant en 0: les marches de Bernoulli, les excursions (chemins de Dyck), les méandres (préfixes de chemins de Dyck), les ponts (chemins terminant en 0). On appelle pic, un maximum local.
Le nombre standard de pics dans chacune de ces familles est n/4 (pour des trajectoires de longueur n): on a même un TCL avec variance linéaire.
Du côté des trajectoires, on a également un comportement asymptotique: divisées par racine carrée de n en espace et par n en temps, elles convergent, selon la famille, vers le mouvement Brownien, le méandre Brownien, l'excursion Brownienne ou le pont Brownien.
Le but de l'exposé est de répondre à la question suivante: quelle est l'influence du nombre de pics dans le comportement asymptotique des familles décrites plus haut? (c'est-à-dire, comment se comportent ces trajectoires si on les conditionne à avoir k=k(n) pics? et quel est, asymptotiquement, le lien entre "la répartition des pics" et les valeurs prises par les trajectoire?)
Résumé: Soit t(n) le nombre de mots de taille n sans carrés sur un alphabet de 3 lettres. On a t(0)=1, t(1)=3, t(2)=6, t(3)=12, t(14)=18. On s'intéresse à la constante C définie comme la limite de t(n)1/n.
Christoph Richard et Uwe Grimm obtiennent une borne supérieure C<1.30193812 en 2003, en utilisant la "Goulden-Jackson cluster method". Je présenterai une nouvelle méthode, plus élémentaire, utilisant une grosse matrice. Avec l'aide de Tony Reix, ingénieur chez Bull, nous avons calculé une borne C<1.30178858 grâce à cette méthode (et une matrice de 15Go).
Résumé: Nous introduisons une nouvelle classe d'objets combinatoires appelés "Tours de Kepler" et dénombrée par les nombres de Catalan. Ces objets sont liés à la combinatoire des nombres de Strahler des arbres binaires et à la théorie des empilements de pièces.
Résumé: En 1965, Germain Kreweras publia une formule énumérative pour les chemins planaires constitués de pas Sud, Ouest et Nord-Est. Il démontra que le nombre de chemins à 3n pas partant et retournant à l'origine et restant dans le quart de plan Nord-Est est kn = 4n /((n+1)(2n+1)) Binomial(3n,n).
La démonstration du résultat de Kreweras connut différentes modifications et simplifications avec les travaux de Niederhausen, Gessel et Bousquet-Mélou. Mais aucune de ces démonstrations n'explique la combinatoire sous-jacente. Quant à la formule de Mullin, il fallut attendre les travaux de Gilles Schaeffer en 2003 pour en avoir une démonstration bijective.
Dans cet exposé je présenterai une démonstration conjointe et bijective des deux résultats. La bijection pour les triangulations est différente de celle de Schaeffer. Les bijections permettent d'interpréter les formules énumératives et de proposer un algorithme efficace de génération aléatoire.
Résumé: Bousquet-Mélou et Rechnitzer ont introduit la classe des animaux multidirigés comme une extension des classiques animaux dirigés 2D introduits en physique statistique. Ils ont donné une expression explicite de leur série génératrice. Pour les animaux dirigés, la fonction génératrice est algébrique et diverses preuves bijectives sont bien connues. Par contre, dans le cas multidirigé, la série génératrice n'est pas algébrique, ni même récursivement finie (D-finite). Néanmoins, nous donnons une preuve bijective en introduisant la "décomposition nordique" d'un empilement connexe de dominos sur la droite discrète formée des entiers naturels.
Ces empilements connexes sont non seulement en bijection avec les animaux multidirigés, mais aussi avec des objets introduits en gravitation quantique 2D par les physiciens Ambjorn, Loll, Di Francesco, Guitter, Kristjansen sous le nom de triangulations Lorentziennes. Un intérêt possible de cette décomposition nordique pourrait être de résoudre des problèmes ouverts d'énumération relatifs au paramètre "courbure" de ces objets.
Cet exposé fait le lien avec les festivités de la rentrée sur les traces d'Antoni Mazurkiewicz. Il s'agit bien d'énumérer des traces connexes, mais sur l'alphabet infini des entiers, et ceci à "translation près".
Résumé: Un modèle d'arbres aléatoires classique en probabilités est celui des arbres de Galton-Watson (GW). Un arbre de GW est l'arbre généalogique d'une population où les individus ont un nombre d'enfants aléatoires (de loi commune p), indépendamment les uns des autres. Au début, la population ne comprend qu'un seul individu. On cherche à dire des choses à propos de l'arbre aléatoire obtenu T, lorsque T est contraint à avoir n noeuds (autrement dit, on cherche à dire des choses sur T, sachant |T|=n).
Dans cet exposé, j'essaierai d'aborder les points suivants:
Résumé: Dans un premier exposé inachevé, en avril 2003, on avait considéré un algorithme permettant de décrire simultanément plusieurs constructions des mots/chemins de Dyck. Une étude systématique des règles de réécriture paramétrant l'algorithme avait permis de redécouvrir une partie du folklore bijectif sur ces objets. Cette fois-ci, on présente des variantes de l'algorithme, utilisées dans trois contextes combinatoires distincts pour y décrire des bijections.
D'abord, on considère l'interprétation combinatoire d'une utilisation du développement de Taylor selon la variable catalytique dans la résolution d'une équation fonctionnelle écrite pour appliquer la méthode du noyau (avec l'ambition peu avouable d'énumérer les chemins de Dyck). Ensuite, on énonce brièvement le problème de la symétrie des q,t-Catalan introduit par Haiman et Haglund. Enfin, on présente une relation entre une involution de Kreweras et une bijection de Delest et Viennot.