Les fonctions quasi-symétriques peuvent être vues comme invariants d'une certaine action du groupe symétrique sur les polynômes, introduite par F. Hivert.
Je montrerai comment l'étude de cette action fait apparaître l'algèbre de Temperley-Lieb (TL_n). Il est remarquable que la dimension de TL_n, tout comme celle du quotient des polynômes par les fonctions quasi-symétriques est donnée par les nombres de Catalan [Aval, Bergeron].
Je proposerai ensuite une extension de cette étude au groupe des permutations signées. Celle-ci est liée à certaines permutations (signées) à motifs exclus. Cet exposé correspond à des travaux en cours et propose plusieurs questions ouvertes.
J'en profiterai enfin pour parler brièvement de bases de Gröbner ... non commutatives.
Résumé: Les arbres de génération à deux étiquettes décrivent la croissance de structures combinatoires dont le nombre de descendants dépend de deux paramètres. Plutôt que cette définition obscure, on peut proposer un certain nombre d'exemples : marches dans un quart de plan (les deux paramètres étant les coordonnées des points d'arrivée), permutations évitant certains motifs, tableaux de Young de hauteur bornée, etc.
Les séries génératrices de ces structures sont régies par des équations fonctionnelles linéaires où deux variables, dites catalytiques, font l'objet de substitutions par des constantes. Les équations linéaires à une variable catalytique sont résolubles par la méthode du noyau. Leur solution est toujours algébrique.
On présentera quatre exemples récents de solutions d'équations linéaires à deux variables catalytiques, correspondant à quatre familles de permutations a motifs exclus. Les solutions apparaissent comme diagonales de séries algébriques (et donc comme des séries holonomes).
Résumé: We discuss various recent developments concerning stack-sortable permutations. We mention results connected to unimodality, symmetry, and simplicial complexes. Conjectures on log-concavity and enumeration are included
Résumé: A metricized ribbon graph is a map to each edge of which a positive number (a "length") is assigned. There exists a construction (by Witten-Kontzevich-...) that associates a certain Riemann surface to a metricized ribbon graph; a simple version of this construction will be presented. This construction establishes a fascinating relation between metricized ribbon graphs and moduli spaces of Riemann surfaces. It will be shown that the Grothendieck theory of dessins d'enfants is a discrete version of this theory, corresponding to the case of commensurable lengths. Several implications and open questions will be presented.
Résumé: Viennot a donné une bijection naturelle (i.e. simple) entre les demi-pyramides et les chemins de Dyck. On présente des variantes a priori artificielles de cette bijection. En effet elles sont obtenues en étudiant automatiquement un ensemble fini de règles de réécriture. Ces règles définissent des applications potentiellement bijectives par une construction rappelant celle des grammaires algébriques. Les preuves de la bijectivité de ces applications nécessitent une compréhension combinatoire de paramètres qui sont autant d'analogues de la longueur de la dernière descente (comme le nombre de retours sur l'axe par exemple).
Ensuite on présente le problème délicat qui a initié cette étude: l'énumération des mots de Dyck selon leur demi-longueur grâce à une mise en équation "à la Temperley" où la variable catalytique est la longueur de la dernière descente. Au lieu de terminer cette étude par la méthode du noyau, ce qui est faisable, on se propose d'essayer de conclure en construisant un système d'équations sur les moments de la variable catalytique. Une interprétation combinatoire simple de ce système permet de résumer sa résolution à une bijection qui s'exprime dans une généralisation du cadre précédent.
Enfin, on évoque d'autres généralisations de ce cadre, motivées par le fait que les paramètres variés apparaissant dans les bijections sont facilement énumérables (mais pas forcément pertinents d'un point de vue combinatoire).
Énumération de pavages par losanges à symétrie octogonale par la méthode de Gessel-Viennot
Résumé: Nous proposons la première formule pour énumerer les pavages par losanges d'un octogone centro-symétrique de taille quelconque. Ce résultat s'appuie sur la méthode de Gessel-Viennot et généralise à un octogone quelconque des résultats d'Elnitsky dans le cas particulier où quatre des côtés de l'octogone sont égaux à 1. Nous commencerons l'exposé par un rappel des motivations pour énumérer de tels ensembles. Puis nous rappelerons comment se traite le cas plus simple de pavages d'un hexagone, avant de présenter notre résultat.
Décomposition canonique des cartes planaires extérieures et application à l'énumération, au codage et à la génération aléatoire
Résumé: Nous proposons une bijection entre les cartes planaires extérieures enracinées à n sommets et les arbres ordonnés enracinés bicolores à n sommets dont tous les sommets de la dernière branche sont coloriés en blanc. Nous en déduisons pour les cartes planaires extérieures enracinées à n sommets:
Méthodes combinatoires d'énumération des arbres couvrants dans certaines familles de graphes
Résumé: Il est bien connu qu'on peut déterminer le nombre
d'arbres couvrants d'un graphe donné en calculant le déterminant d'un
mineur du tableau Laplacien de ce graphe.
Mais compter les arbres couvrants d'un graphe donné est un problème
vraiment combinatoire, il est bon de chercher des méthodes
combinatoires.
Je présenterai (au moins) deux telles méthodes, et, si le temps le
permet, deux autres.
Upper and lower bounds for the growth constants of polygons and polyominoes
Résumé: I will present techniques to derive rigorous upper and lower bounds for the growth constants of polygons and polyominoes. In particular I will deal with polygons and polyominoes on the hexagonal lattice enumerated by area. The respective growth constants were found to lie between 4.7892 (4.8049) and 5.9045. The estimated value of the growth constant based on series analysis is 5.1619 (5.1831)
The idea is to find objects that over/under count polygons (polyominoes) and for which one can find the generating function and derive the growth constant. For the lower bound the enumeration the existing enumeration data can be used combined with a concatenation argument. Unfortunately this trick does work for the upper bound. A objects, so-called twigs, have to be enumerated. And from the new data, with the appropriate concatenation argument an upper bound is derived.
A nice bijection for a content formula for skew semistandard Young tableaux
Résumé: Based on Schützenberger's evacuation and a modification of the jeu de taquin, we give a bijective proof of an identity connecting the generating function of reverse semistandard Young tableaux with bounded entries with the generating function of all semistandard Young tableaux. This solves Exercise 7.102 b of Richard Stanley's book `Enumerative Combinatorics 2'.
Résumé: Peut-on encore dire des choses intéressantes sur la génération aléatoire uniforme de mots de Dyck ou d'arbres binaires? C'est en tout cas ce que j'essaierai de faire, en étudiant la complexité moyenne, en nombre de bits aléatoires, de trois algorithmes différents.
Résumé: Il s'agit d'étudier les tableaux carrés nxn dont les éléments sont dans un alphabet fini et qui vérifient la propriété suivante: le mot diagonal est différent de chacun des mots lignes. Plus radicalement, on demande que chacun des tableaux obtenus par permutation des lignes satisfasse à cette condition.
Exemple:
aaba baba bbab ababPar contre le suivant n'est pas cantorien (permuter les lignes 3 et 4):
abba baab abaa aaba
Résumé: Dans cet exposé, on essaiera de comprendre comment q-Pfaff Saalschutz permet d'établir les théorèmes Lecture Hall et de définir de nouveaux objets: les overpartitions.
Résumé: Au cours des dernières années les marcheurs méchants ont envahi la combinatoire. Ils sont connus aussi sous les pseudonymes de "marches aléatoires à une dimension", ou, en combinatoire, de "configurations de chemins qui ne se touchent pas".
Alors, étant donnés quelques points de départ (0,2a_1), (0,2a_2), ...,(0,2a_p), chaque marcheur doit faire m pas (1,1) ou (1,-1), sans toucher aucun des autres. Les physiciens posent la question de l'énumération approximative de telles configurations, quand m tend vers l'infini. Aussi, ils veulent connaître la scaling limit: le comportement asymptotique quand chaque pas est infinitésimal.
Je présenterai une méthode de Christian (Krattenthaler), Xavier (Viennot) et Tony (Guttmann), que j'ai raffinée un peu, qui répond à toutes ces questions, bien qu'elle soit très simple.
Résumé: Dans un premier temps, je donnerai la construction géométrique de Fomin- Kirillov permettant de définir le polynôme stable de Schubert associé à toute permutation. Cette construction repose sur des configurations de chemins associées aux décompositions réduites de la permutation. Les polynômes ainsi introduits sont symétriques et cette propriété est liée à la célèbre équation de Yang-Baxter en physique statistique.
Ensuite je montre que pour une permutation sans occurrences du motif (321), le polynôme stable de Schubert est en fait une fonction de Schur gauche. Il est bien classique que ces fonctions symétriques peuvent également être définies par des configurations de chemins en interprétant le déterminant de l'identité de Jacobi-Trudi. Nous montrons le lien entre cette construction et celle de Fomin-Kirillov.
Enfin, ces constructions géométriques sont liées à deux structures algébriques: d'une part l'algèbre nil-Coxeter (ou algèbre des différences divisées) pour les permutations générales, d'autre part l'algèbre nil-Temperley-Lieb, de dimension le nombre de Catalan, pour la classe des permutations sans occurrences du motif (321). Cet exposé est lié aux deux exposés que j'ai fait précédemment sur les algèbres de Temperley-Lieb, mais peut être écouté indépendament.
Résumé: Nous rappelons la théorie de Stanley sur l'énumération des partitions planes. Nous montrons la version non-commutative de cette théorie. Bien sûr, nous discuterons des conséquences algébriques de cette combinatoire.
Résumé : Il y a deux moyens d'aborder la gravitation quantique: du point de vue de la gravitation (ce qui mène à la théorie des cordes), ou celui de la mécanique quantique. Ici on trouve des modèles lorentziens (au lieu des modèles euclidiens) qui regardent l'espace-temps comme une triangulation. Ces triangulations sont en bijection avec les empilements de dominos.
La question à laquelle on veut vraiment répondre est : quel est l'effet d'ajouter un paramètre pour la courbure. La réponse est trouvée dans une réécriture de la bijection précédente comme un empilement de segments. Maintenant le nombre de segments est la courbure, et la longeur totale des segments est la nouvelle taille du modèle.
Je présenterai les deux modèles proposés récemment dans deux articles, démontrerai comment ajouter la courbure dans le premier (ce qui est fait dans l'article pour le deuxième modèle) et parlerai du résultat continu, où apparaissent des fonctions de Bessel modifiées.
Résumé : We show that the h-vector of a ladder determinantal ring cogenerated by M=[u_1|v_1] is log-concave. Thus we prove an instance of a conjectore of Stanley, resp. Conca and Herzog.
Résumé : L'algèbre de Temperley-Lieb fut introduite en physique statistique en relation avec le modèle de Potts. Sa dimension est le nombre de Catalan. Une interprétation géométrique fut donnée par Kauffman. Cette algèbre apparaît aussi dans divers domaines des mathématiques et de la physique : en théorie des noeuds et des tresses, dans les problèmes d'énumération de méandres et tout récemment dans des travaux reliant le modèle de "chaînes de spins XXZ" avec le célèbre nombre de matrices à signes alternants.
Dans cet exposé nous donnons trois interprétations des bases de cette algèbre de Temperley-Lieb. La première est en termes de certains empilements de dominos, factorisés selon le "lemme des escaliers", la deuxième est en termes de certains diagrammes de Ferrers gauches, ou encore de polyominos parallélogrammes, la troisième interprétation est avec les permutations ayant le motif 321 interdit.
Enfin nous définissons une variante nilpotente de l'algèbre de Temperley-Lieb, ayant la même dimension et les mêmes bases. Son intérêt est qu'elle peut jtre réalisée avec des opérateurs agissant sur les diagrammes de Ferrers (ou partitions d'entiers), soulignant ainsi le lien avec la théorie des fonction symétriques.