Cours de Combinatoire
M2 Maths Fondamentales, 2019/2020.

Guillaume Chapuy, TD par Matthieu Josuat-Vergès.

Tentative a priori de plan du cours accessible ici.
Références: pour commencer Stanley EC1/EC2, Flajolet-Sedgewick, Aigner, sont plus que suffisants. J'utilise aussi l'article de Bousquet-Mélou aux premiers cours dont je ne saurais que trop recommender la lecture. Voir refs en bas de page.

Résumé des séances (Combi I, septembre-octobre)

• 9 septembre: Introduction: triangulations d'un polygone et récurrence de Catalan. Qu'est-ce que compter? Pour se motiver j'ai montré la formule de Harer-Zagier sur les recollements de polygones.
  Références: on peut lire le plaisant chapitre introductif du Flajolet.
• 10 septembre: Notion de classe combinatoire et construction admissible d'après Flajolet. Constructeurs classiques (+,x,SEQ,MSET) et quelques exemples. Généralités sur les séries rationnelles, et on a commencé à parler de marches sur les graphes dirigés.
  Références: Pour les séries, le Flajolet Chapitre I. Pour les séries rationnelles et les marches, le Bousquet-Mélou Section 2.2 que l'on poursuivra la prochaine fois. Ou plus dense, le chapitre 4 de Stanley EC1 dédié aux séries rationnelles.
• 12 septembre: TD 1.
• 16 septembre: On exprime la série génératrice des marches de u à v sur un graphe dirigé comme un ratio d'indicatrices de cycles. Application (très jolie) aux chemins de Dyck de hauteur bornée. En guise de digression, un peu d'algèbre linéaire sur les graphes (valeurs propres du graphe complet et de l'hypercube). Rappels sur les langages rationnels, définis par expressions rationnelles et/ou par automates. Leur série génératrice est rationnelle.
  Références: L'article de MBM à l'ICM, sections 2.1, 2.2, 2.3. Pour la digression sur les valeurs propres, voir par exemple le petit Stanley (Algebraic Combinatorics, walks, trees, etc) chapitres 1 et 2, ou tout bon article de survey sur les valeurs propres de graphes.
• 17 septembre: On a reparlé un peu de langages rationnels pour voir sur un exemple comment calculer une expression régulière à partir de l'automate, en résolvant le système («linéaire») d'équations aux langages. On a insisté sur le fait que les expressions non-ambigües permettent de compter, contrairement aux expressions ambigües. En suivant toujours l'article de MBM, on a donné des exemples de classes rationnelles: polyominos verticalement convexes, points entiers dans un polytope, aire sous les chemins de Dyck. Puis on a introduit le monoïde de Cartier-Foata, ou de manière équivalente les empilements de pièces. On a démontré le théorème de Viennot qui écrit la série génératrice des empilements comme un ratio d'indicatrices d'empilements triviaux.
  Références: Pour les séries rationnelles, toujours l'article de MBM à l'ICM, sections 2.4, 2.5. Pour les empilements, par exemple l'intro de la thèse de Marie Albenque (pages 25--30).
• 19 septembre: TD 2. Pour une indication pour l'exercice 6, on pourra consulter la page 41 de la thèse d'Axel Bacher.
• 23 septembre: Vocabulaire sur les arbres, arbres plans enracinés. Série génératrices d'arbres binaires/m-aires, mots de Lukaciewicz, lemme cyclique. Le nombre d'APE de passeport fixé est donné par une belle formule close.
  Références: Stanley EC2 Chapitre 5, ou la section de Flajolet sur le lemme cyclique.
• 24 septembre: Classes étiquetées, espèces, produit étiqueté, constructeurs SET et CYCLE, premières applications (permutations, surjections). Arbres de Cayley via inversion de Lagrange, puis bijection de Joyal.
  Références: Flajolet pour les classes étiquétées, ou pour les fans de théorie des espèces de structures, le livre référence des québécois Bergeron, Labelle, Leroux.
• TD 3.
• 30 septembre: Combinatoire analytique: théorèmes de transferts pour les singularités algébro-logarithmiques dans un Delta-domaine.
• 1 octobre: Quelques rappels de probas élémentaires (moment, inégalités de Markov et Chebicheff, méthode du second moment) et applications immédiates de l'analyse de singularités: degré de la racine dans un arbre plan, nombre de zéros des ponts aléatoires, nombre de cycles dans une permutation.
  Références pour ces deux cours: Le Flajolet qui fait beaucoup plus, et dont ce cours est une collection de moreceaux choisis. Pour le critère de Carlemann sur les moments, c'est par exemple dans l'appendice de ce même livre.
• TD 4. Pour l'exercice 1, on utilisera le théorème des fonctions implicites complexes, voir par exemple l'appendice du Flajolet qui contient notamment la preuve élémentaire (et combinatoire!) par les séries majorantes.
• 7 octobre: Démonstration du théorème de Drmota-Lalley-Woods. Au passage, preuve «combinatoire» du théorème des fonctions implicites analytique. Puis, changement de sujet, et généralités sur les cartes planaires.
  Références: Les passages dédiés du Flajolet pour DLW. Pour les cartes, par exemple le chapitre "Planar Maps" de Gilles Schaeffer dans le Handbook of Combinatorial enumeration.
• 8 octobre: Cartes planaires, suite. On dessiné toutes les petites cartes enracinées pour se convaincre qu'on comprenait bien la notion d'enracinement. On a parlé de sous-carte, de carte duale, de sous-carte duale. On a compté les cartes boisées «à la Mullin» puis j'ai présenté, sans preuve (quoique j'aie cité les éléments principaux) la double bijection de Bernardi (cartes boisées, orientations, paires d'arbres).
  Références: Le chapitre "Planar Maps" de Gilles Schaeffer dans le Handbook of Combinatorial enumeration.
• TD 5.
• 14 octobre: Énumération des cartes planaires enracinées par la méthode de l'équation de Tutte. Au passage, quelques rappels sur les fonctions algébriques et l'élimination, en particulier les séries de Puiseux et les développements de Puiseux d'une fonction algébrique en ses singularités.
  Références: Pour l'équation de Tutte et sa résolution voir toujours le chapitre du "Handbook" (c'est fait aussi dans le Flajolet ou dans mes notes ci-dessous). Pour les généralités sur les fonctions algébriques, voir l'article de Bousquet-Mélou à l'ICM, et toujours le Flajolet (Section VII.7 et appendice B.1).
• 16 octobre: Bijection de Tutte entre cartes et quadrangulations. Bijection de Cori-Vauquelin-Schaeffer des arbres étiquetés pour expliquer la formule de Tutte.
  Références: Par exemple mes notes sections 1.7,4.1,4.2,4.3 (on remplacera partout g par zéro et "one-face map" par "arbre plan enraciné".)
• TD 6.

Résumé des séances (Combi II, novembre-décembre)

• 4 novembre: On commence la théorie des fonctions symétriques en suivant de près Stanley, EC2, Chapitre 7. Fonctions symétriques monomiales, élémentaires, complètes, powersums, et formules de changement de bases avec les monomiales pour chacune. Introduction de omega et preuve que c'est une involution.
  Références: Stanley, EC2, Chapitre 7.
• 5 novembre: Fonctions symétriques, suite. Identités de Cauchy et Cauchy duales pour les powersums. Action de omega sur les powersums. Introduction des tableaux (SSYT), définition combinatoire des fonctions de Schur et involutions de Bender-Knuth.
  Références: Stanley, EC2, Chapitre 7.
• TD 1.
• 11 novembre: Pas de cours (férié)
• 12 novembre: Fonctions de Schur (suite). On s'écarte un peu du Stanley. Relation d'entrelacement primale et duale, définition des fonctions de Schur comme fonctions génératrices de suites de partitions entrelacées. Règle locale primale et duale, et algorithme RSK et RSK dual vu comme itération de la règle locale (ce qui démontre Cauchy et Cauchy dual pour les Schur). Introduction des opérateurs de vertex, règle de quasi-commutation, équivalence avec la règle locale. Démonstration bijective de la règle locale (primale).
• TD 2.
  NOTE: pour la démonstration de la règle locale duale, voir l'article``Perfect sampling algorithms...'' ci-dessous, Section 3, paragraphe "Dual Cauchy case" page 10. L'algorithme "sampleHV" qui y est présenté fait exactement ce que l'on veut, si ce n'est qu'il faut partir d'un B dans {0,1} fixé et non pas le tirer au hasard comme dans l'article. La preuve détaillée que cela fonctionne est écrite dans le paragraphe suivant (jusqu'à l'équation (3.6) incluse). Le tout fait une quinzaine de lignes et se lit sans problème avec les notations du cours.
• 18 novembre: Définition combinatoire des processus de Schur, fonction de partition générale (produit d'équerres généralisées). Applications aux partitions planes (formule de MacMahon), aux partitions planes inverses, puis à la formule des équerres (usuelle) via argument asymptotique.
  Références: Pour ce cours et le précédent, voir mon habilitation section 3.3 et 3.4 pour entrelacements et opérateurs de vertex. Puis il faut commencer à fureter dans la littérature. Pour la définition combinatoire des processus de Schur et le point concret sur les opérateurs de vertex et les commutations d'opérateurs, l'algorithme RSK, on pourra regarder les sections 2.3 et 3 (jusqu'à la remarque 3.1) dans l'article ``Perfect sampling algorithms...'' ci-dessous. On pourra aussi regarder le Stanley ou toute autre référence qui décrit le point de vue classique sur l'algorithme RSK (par règle d'insertion), et méditer sur les différences.
• 25 novembre: Introduction des matrices à signes alternants, énoncé du théorème et quelques motivations historiques (lambda-déterminant). Démonstration du théorème. J'ai introduit le modèle à 6 sommets, défini les poids de Baxter et donné la relation de Yang-Baxter (démonstration au cas-par-cas, non tous faits en cours!). Ensuite, j'ai montré la récurrence d'Izergin.
• 26 novembre: À partir de là, plutôt que l'approche classique (déterminant de Izergin Korepin), j'ai «reconnu» que la fonction de Schur double-escalier satisfait la même récurrence. On l'évalue ensuite avec la hook-content formula pour conclure. Ensuite, j'ai rapidement (mais complètement) décrit comment obtenir les caractères du groupe symétrique grâce à l'application caractéristique, ce qui ne demande presque aucun travail au point où nous en étions.
  Références pour les deux cours: Jusqu'à la récurrence de Izergin, il y a plusieurs bonnes sources, dont le livre de Bressoud, ou encore le Aigner chapitre 10.4. La preuve qui consiste à reconnaître la fonction de Schur double escalier est due à Stroganov, on pourra la lire (très succinte) dans l'habilitation de P. Zinn-Justin (ci-dessous) section 2.5.6 à des petits changements de notation près. Pour la preuve de la "hook-content formula" que j'ai donnée en cours, voir toujours Stanley, EC2 (thm 7.21.2 et 7.21.4). Pour les caractères du groupe symétrique, tout est fait en quelques pages dans Stanley, EC2, section 7.18, que j'ai suivie à la lettre.
• 2 décembre. Cartes biparties, définitions topologique puis combinatoire. Expression des nombres de cartes avec l'algèbre de groupe. Éléments de Jucys-Murphy. Formule de Frobenius exprimant le nombre de factorisations de l'identité en fonction des caractères.
• 3 décembre: Esquisse de preuve de la formule de Frobenius à partir de l'orthogonalité des caractères. Expression de la série génératrice des cartes biparties comme somme de triple produits de fonctions de Schur. Puis, à l'aide des éléments de Jucys-Murphy et de la hook-content formula (qui donne leur action sur chaque représentation irréductible), expression de la spécialisation «bivariée» de cette série comme une somme impliquant contenus et deux fonctions de Schur. Enfin, calcul à la main du nombre de cartes à une face par Frobenius et Murnaghan-Nakayama.
  Références pour les deux cours: Pour les cartes biparties, algèbre de groupe, Frobenius, etc, mon habilitation ci-dessous Sections 1.1, 1.2, 2.1, 2..2 (hors digression), 3.1 qui sont plus ou moins le verbatim du cours (il faut juste mettre m=2 dans les parties parlant de constellations).
• 9 décembre: Correspondance Bosons-Fermions: on introduit les diagrammes Maya, en bijection avec les partitions chargées. On définit les opérateurs de création/annihilation et on s'en sert pour refabriquer des opérateurs qui agissent comme la multiplication par les powersums. On fait tout cela en utilisant le fait que l'on connaît déjà la règle de Murnaghan-Nakayama.
  Références: Rien de totalement clair malheureusement. Tout est fait en quatre pages (sans présupposer de connaissances sur la théorie des fonctions symétriques, que l'on retrouve), mais de manière assez elliptique, dans l'appendice A du célèbre "Infinite Wedge and Random partitions" d'Okounkov ci-dessous (Attention alpha_{n} et alpha_{-n} sont échangés par rapport à mon cours, ainsi que Gamma_+ et Gamma_-; aussi ses opérateurs Gamma sont multivariés, il faut prendre s_n=x^n/n pour retrouver ceux du cours).

Références:

Les trois premiers (Stanley EC1/2 et Flajolet) sont des références incontournables. Aigner est un pot-pourri composé avec beaucoup de goût.

• Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge ; New York : Cambridge University Press, 2009.
• Richard Stanley, Enumerative Combinatorics, Volume 2, New York : Cambridge University Press, 2012.
• Richard Stanley, Enumerative Combinatorics, volume 1, second edition, Cambridge University Press, 2011
• Martin Aigner, A Course in Enumeration, Berlin : Springer, c2007.

D'autres références que j'aurai utilisées ponctuellement. L'article de MBM à l'ICM est un must.

• Mireille Bousquet-Mélou, Rational and algebraic series in combinatorial enumeration, notes de sa conférence au congrès mondial des mathématicien·ne·s (ICM), ici.
• Richard Stanley, Algebraic Combinatorics, Walks, Trees, Tableaux, and more, Springer 2013
• Marie Albenque, Tresses, Animaux, Cartes : À l’interaction entre combinatoire et probabilité, thèse de doctorat, 2009, ici.
• François Bergeron, Gilles Labelle, Pierre Leroux, Combinatorial Species and Tree-like Structures, Encyclopedia of Mathematics, Cambridge University Press, 1998. 497 pages.
• Gilles Schaeffer, Planar Maps, chapitre dans le Handbook of Enumerative Combinatorics, editeur Miklos Bona. version accessible ici.
• Dan Betea, Cédric Boutillier, Jérémie Bouttier, Guillaume Chapuy, Sylvie Corteel, Mirjana Vuletić, Perfect sampling algorithm for Schur processes,Markov Processes Relat. Fields 24, 381-418 (2018), ici.
• G. Chapuy Rencontres autour de la combinatoire des cartes, mémoire d'habilitation, 2018, ici
• Bressoud, David M. Proofs and confirmations. The story of the alternating sign matrix conjecture. MAA Spectrum. Mathematical Association of America, Washington, DC; Cambridge University Press, Cambridge, 1999. xvi+274 pp. ISBN: 0-521-66170-6; 0-521-66646-5
• P. Zinn-Justin. Six-Vertex, Loop and Tiling models: Integrability and Combinatorics, mémoire d'habilitation, 2009, ici
• A. Okounkov, Infinite wedge and random partitions, Sel. math., New ser. (2001), ici

Cette page (dont les références) sera mise à jour au fur et à mesure.