2016-2017

Vendredi 21 juillet : François Pitois (élève de l'ENS Lyon)

Titre : Autour des méandres

Résumé : Un méandre est une courbe fermée qui coupe une droite ; et l'on s'intéresse aux méandres pour lesquels on a fixé le nombre d'intersections entre la droite et ledit méandre. Je me suis penché sur le comptage, la génération, et certaines statistiques des méandres, ainsi que sur leur vitesse de croissance.

Jeudi 6 juillet : Stéphane Dartois, Laboratoire de Physique Théorique et Modélisation (LPTM) de l'université de Cergy-Pontoise et du CNRS (https://www.u-cergy.fr/fr/recherche-et-valorisation/laboratoires/lptm.html)

Titre : Récurrence Topologique à blobs et cartes farcies

Résumé : Dans cet exposé, je présenterai les outils de récurrence topologique utilisés pour l'étude des modèles de tenseurs aléatoires présentés dans https://arxiv.org/abs/1612.04624.
Dans un souci de pédagogie, les résultats des travaux de Gaëtan Borot et Sergei Shadrin (https://arxiv.org/abs/1307.4957 et https://arxiv.org/abs/1502.00981) serviront de base à la présentation. Je reverrai les modèles de cartes farcies et la récurrence topologique généralisée que ces modèles satisfont. En effet certains modèles de tenseurs aléatoires peuvent être compris à l'aide de ce type de cartes. Enfin, si le temps le permet, je montrerai comment passer des modèles de tenseurs aléatoires aux modèles de cartes farcies.

Vendredi 30 juin : Alina Mayorova, Laboratoire d'informatique de l'École polytechnique (LIX)

Titre : Un nouveau lien entre l’algèbre de descentes du groupe hyperoctaèdral, les tableaux de dominos et les fonctions quasisymétriques de Chow.

Résumé : Introduite par Solomon dans son article de 1976, l’algèbre de descentes d’un groupe de Coxeter fini a reçu une attention significative au cours des années passées. Gessel a montré dans le cas du groupe symétrique que ses constantes de structure donnent la table de comultiplication de la base fondamentale des fonctions quasisymétriques. Nous montrons que cette propriété implique en réalité plusieurs relations connues liées à la correspondance Robinson-Schensted-Knuth et certaines de ses généralisations. Ceci donne un nouveau lien entre ces résultats et la théorie des fonctions quasisymétriques et permet d’obtenir de nouvelles formules plus avancées faisant intervenir les coefficients de Kronecker. Par ailleurs en utilisant la théorie des fonctions quasisymétriques de type B introduite par Chow nous pouvons étendre notre méthode au cas du groupe hyperoctaédral et démontrer de nouvelles formules.

Vendredi 16 juin : Benjamin Hellouin de Menibus (équipe Automates et applications à l'Institut de Recherche en Informatique Fondamentale (IRIF) de l'université Paris-Diderot) http://www.mat-unab.cl/~hellouin/

Titre : Calculer l'entropie des pavages mélangeants

Résumé : Les pavages (ou sous-décalages) correspondent à des assignations d'états à chaque sommet d'une grille Z^d soumises à des contraintes locales. L'entropie d'un espace de pavage est un paramètre pertinent pour diverses communautés : en théorie de l'information (d=1), comme capacité d'un canal de communication ; en mathématiques, comme principal invariant de conjugaison ; en physique statistique (d=2 ou 3), comme entropie thermodynamique du système modélisé. Est-il possible de calculer (algorithmiquement) l'entropie d'un espace de pavages défini par des contraintes fournies en entrée ?
Pour des contraintes en nombre fini (pavage de type fini) et en dimension 1, l'entropie est calculable par une méthode algébrique classique. Le cas de la dimension supérieure s'est révélé beaucoup plus difficile, l'entropie de beaucoup d'exemples simples étant encore indéterminée. En 2007, il a été prouvé que l'entropie en dimension 2 n'est pas calculable en général. Des travaux plus récents ont montré que l'entropie redevient calculable sous des hypothèses de mélange, c'est-à-dire d'indépendance des motifs situés à une certaine distance. Où se situe la limite entre les cas calculable et incalculable ?
En introduisant une notion de taux de mélange, nous montrons l'existence d'un seuil en fonction de ce taux où la difficulté du problème passe de calculable à incalculable, sans pouvoir le déterminer exactement. Pour une famille plus large de pavages soumis à un nombre infini de contraintes, nous parvenons à déterminer exactement le seuil correspondant, et conjecturons que sa position est la même dans le cas fini.
Ces travaux sont en collaboration avec Silvère Gangloff.

Vendredi 9 juin : Andrew Elvey-Price (Department of Mathematics and Statistics, The University of Melbourne, Australia)

Titre : Enumeration in Thompson's group F

Résumé : Just over 50 years ago, Richard Thompson introduced the group F in an attempt to find a counter example to the Von-Neumann conjecture. On the one hand, F can be simply understood as a group of pairs of binary trees, or even more simply by its group presentation, yet in many ways, F is still very mysterious. Perhaps the biggest unknown question about F is whether it is `amenable', which, among other things, would answer Thompson's original question of whether it disproves the Von-Neumann conjecture. The amenability of F is one of those questions which tends to get a claimed solution each year, except that the claimed answer changes each time. I will describe combinatorially what it means for F to be amenable, and the results of my numerical work with Tony Guttmann on this question.

Vendredi 12 mai : Xavier Viennot

Titre : Fonctions zêta sur les graphes

Résumé : Diverses extensions de la fonction zêta de Riemann ont été proposées pour tout graphe, comme la fonction zêta de Ihara-Selberg. Deux évaluations de cette fonction ont été données par Bass. Giscard et Rochet ont proposé une nouvelle approche de ce sujet avec la théorie des empilements de pièces. Un des lemmes de base de la théorie est le lemme logarithmique. Je montrerai comment ce lemme permet de donner une approche bijective des formules de Bass.

Vendredi 5 mai : Xavier Viennot

Titre : Déterminants, empilements et chemins ne se coupant pas (2)

Résumé : Cf. (1)

Vendredi 28 avril : Xavier Viennot

Titre : Déterminants, empilements et chemins ne se coupant pas (1)

Résumé : Un Lemme très classique en combinatoire (Lemme LGV) relie les configurations sur un graphe sans circuits de chemins ne se coupant pas à un calcul de déterminant. Une extension aux graphes généraux a été étudiée par divers auteurs : Lalonde (1990) donnant une interprétation combinatoire de l'identité de Jacobi en algèbre linéaire (reliant les mineurs d'une matrice à ceux de la matrice inverse), des preuves bijectives par involution sur certaines configurations de chemins : Lalonde (1996), Fomin (2001), Talaska (2012) et enfin par Carrozza, Krajewski, Tanasa (1996) avec le calcul des variables et intégrales de Grassmann utilisées en physique quantique. Après un rappel de deux lemmes de base sur les empilements, j'exposerai le théorème de Lalonde, en termes d'empilements de cycles et de chemins, avec une nouvelle preuve bijective par involution, duquel découle toutes les interprétations précédentes.
Pour plus de détails, voir la vidéo et les transparents, chapitre 4c du cours : http://www.xavierviennot.org/coursIMSc2017/Ch_4.html.

Vendredi 7 avril : Xavier Viennot

Titre : Polynômes chromatiques des graphes et empilements de pièces

Résumé : Un théorème classique de R. Stanley en théorie des graphes donne une interprétation de la valeur pour (-1) du polynôme chromatique d'un graphe en terme d'orientations acycliques. Nous redémontrons ce théorème en utilisant la théorie des empilements de pièces et donnons une extension en introduisant la notion de série chromatique d'un graphe. Enfin nous évoquerons quelques développements récents reliant l'interprétation des coefficients du polynôme chromatique, la théorie des empilements et les algèbres de Lie partiellement commutatives.
Références : Chapitre 5a du cours 2017 de combinatoire bijective de X.V. Transparents et vidéos sur le site du cours : http://www.xavierviennot.org/coursIMSc2017/Ch_5.html.

Vendredi 31 mars : Mireille Bousquet-Mélou

Titre : À petits pas dans le quadrant : algébricité différentielle

Résumé : La « méthode des invariants » a été inventée par Tutte pour compter des cartes proprement coloriées. On montrera d'abord qu'on peut la recycler pour résoudre de manière uniforme tous les modèles algébriques de marches dans le quadrant (y compris le modèle difficile de Gessel).
Ensuite, on adaptera la notion d'invariants à un contexte plus analytique pour démontrer que certains modèles dans le quadrant, quoique non-différentiellement finis, sont différentiellement algébriques (i.e., satisfont une ED polynomiale).
Travail en commun avec Olivier Bernardi et Kilian Raschel.

Vendredi 17 mars : Philippe Duchon

Titre : Simulation à mémoire finie de lois de probabilités

Résumé : La question de la simulation exacte de lois de probabilités sur les réels est généralement étudiée sous un modèle « arithmétique » où on calcule de manière exacte sur des réels. Dans cet exposé, on se place au niveau « bit à bit », et on se demande ce qui peut être simulé si on n'a qu'une mémoire finie.
On est alors naturellement amené à considérer des automates qui tirent à pile ou face et qui écrivent des mots, qu'on espère infinis, et qu'on interprète comme le développement de réels ; la question est donc de savoir quelles distributions sont simulables de la sorte.
Le modèle est essentiellement celui considéré par Knuth et Yao en 1976, et pour lequel ils ont montré un résultat intrigant : si une loi simulable a une densité qui est une fonction analytique, alors cette densité est en fait polynomiale - ce qui exclut de fait de nombreuses lois usuelles.
Je présenterai le modèle et le résultat de Knuth et Yao, mais aussi un résultat plus nouveau de classification : étant donné un automate, on peut dire s'il simule une loi à atomes, ou à densité, ou une loi plus « méchante ». Je montrerai aussi des exemples qui interdisent une généralisation trop forte du résultat de Knuth et Yao.

Vendredi 10 mars : (Petite école de combinatoire) Mireille Bousquet-Mélou

Titre : Dénombrement de cartes (5)

Résumé : Cf. (1)

Vendredi 3 mars : Sébastien Labbé

Titre : Une généralisation d-dimensionnelle des mots de Christoffel 2/2

Résumé : Cf. (1)

Vendredi 17 février : Gábor Hetyei https://math.uncc.edu/people/gabor-hetyei Department of Mathematics and Statistics, The University of North Carolina at Charlotte

Titre : Propriétés de quelques fractions continues de Hurwitz

Résumé : On considère les fractions continues qui sont définies par une suite des termes formée par mélange périodique d'une suite constante et d'une suite arithmétique. On propose une formule close pour des sous-suites de la suite des convergents. La preuve utilise des séries de Laurent formelles et des identités sur les coefficients binomiaux qui se démontrent de manière combinatoire. En passant à la limite on obtient des formules closes qui font intervenir des fonctions de Bessel et des polynômes de Fibonacci. Les cas spéciaux fameux incluent les nombres e et tan(1).

Vendredi 10 février : (Petite école de combinatoire) Mireille Bousquet-Mélou

Titre : Dénombrement de cartes (4)

Résumé : Cf. (1)

~~~~~

Vendredi 10 février : Sébastien Labbé

Titre : Une généralisation d-dimensionnelle des mots de Christoffel 1/2

Résumé : Nous rappellerons le résultat de Brlek, Lachaud, Provençal, Reutenauer (2009) qui relie le concept de convexité en géométrie discrète avec des notions connues en combinatoires des mots notamment les mots de Lyndon, la factorisation de Lyndon et les mots de Christoffel. Nous nous intéresserons aux généralisations d-dimensionnelles de ce résultat (une question ouverte). Nous présenterons une généralisation d-dimensionnelle des mots de Christoffel développée en collaboration avec Christophe Reutenauer.

Vendredi 3 février : (Petite école de combinatoire) Mireille Bousquet-Mélou

Titre : Dénombrement de cartes (3)

Résumé : Cf. (1)

Vendredi 13 janvier : (Petite école de combinatoire) Mireille Bousquet-Mélou

Titre : Dénombrement de cartes (2)

Résumé : Cf. (1)

Vendredi 6 janvier : (Petite école de combinatoire) Mireille Bousquet-Mélou

Titre : Dénombrement de cartes (1)

Résumé : Une visite des approches (surtout récursives) pour le dénombrement de cartes, planaires ou non, équipées ou non d'une structure supplémentaire (arbre couvrant, coloration...). Cette petite école est liée à un cours donné cet hiver à l'institut Poincaré à Paris, dans le cadre du semestre thématique « Combinatoire et interactions ».

Vendredi 16 décembre : Vincent Delecroix

Titre : Indépendance asymptotique de la décomposition en cycles pour des paires de permutations contraintes par une équation de commutateur

Résumé : Fixons des entiers k₁, k₂, ..., k_m plus grands ou égaux à 2. On s'intéresse aux paires de permutations (s,t) de S_n telles que la décomposition en cycles de [s,t] = s t s^-1 t^-1 est faite exactement de cycles de longueur k₁, k₂, ..., k_m et de points fixes (i.e. des cycles de longueur 1). La raison de cet intérêt est que le nombre de telles paires compte certaines cartes combinatoires et leur asymptotique au premier ordre est guidée par le volume de certains espaces de modules algébriques.
J'essaierai de donner quelques motivations à l'étude de ces quantités mais surtout j'expliquerai pourquoi la décomposition en cycle de s est asymptotiquement indépendante de celle de t (résultat que je ne sais pas encore démontrer combinatoirement).

Vendredi 2 décembre : Nantel Bergeron (York University, Ontario, Canada) http://www.math.yorku.ca/bergeron/

Titre : Antipode et hypergraphe

Résumé : [en collaboration avec Carolina Benedetti]
Calculer des formules d'antipodes pour différentes algèbres de Hopf combinatoires est un problème classique mais difficile à résoudre. Récemment, de nombreux résultats dans ce sens ont été trouvés pour diverses algèbres de Hopf combinatoires [Humpert-Martin, Benedetti-Sagan, Aguiar-Ardila]. Une motivation pour trouver de telles formules réside dans leur interprétation géométrique potentielle, ou dans leur utilisation pour obtenir des informations concernant les invariants combinatoires des objets en jeu. Un exemple de ceci est l'algèbre de Hopf des graphes G. Humpert et Martin dérivent la formule antipode et l'utilisent pour mieux comprendre le célèbre théorème couleur (-1) de Stanley : le polynôme chromatique d'un graphe évalué à -1 est, à signe près, le nombre d'orientations acycliques du graphe. Du côté géométrique, un résultat remarquable d'Aguiar et Ardila montre que cet antipode est codé dans le vecteur -f du zonotope graphique correspondant au graphe donné.
Nous montrons qu'un cadre plus général pour étudier cela est donné par les hypergraphes.

Vendredi 25 novembre : Philippe Duchon

Titre : Comptage de couplages parfaits sans croisements (d'après Ruiz-Vargas et Welzl)

Résumé : Prenons un nombre pair, 2n, de points dans le plan, en position convexe. Le nombre de couplages parfaits de ces 2n points qui ne présentent pas de croisements d'arêtes (si celles-ci sont tracées par des segments), est bien connu : c'est le n-ième nombre de Catalan.
Mais que se passe-t-il si, au lieu d'être en position convexe, les points sont « presque » en position convexe : 2n-1 sont en position convexe, et le dernier se trouve à l'intérieur du polygone ? La réponse dépend alors des positions de tous les points, mais Ruiz-Vargas et Welzl ont démontré une élégante formule d'énumération qui ne fait intervenir que les positions des points par rapport à un petit nombre de droites. Je présenterai la preuve de ce résultat, et essaierai de discuter de la possibilité d'exploiter une telle formule pour faire de la génération aléatoire.

Vendredi 18 novembre : Camille Male http://camillemale.com/

Titre : Une approche unifiante en probabilité non commutative

Résumé : En théorie non commutative des probabilités, un espace de proba est une algèbre (non commutative) sur laquelle est définie une forme linéaire, jouant le rôle de l'espérance. Il a été montré par Speicher qu'il existe exactement trois notions d'indépendance universelles dans ce contexte :

l'indépendance tensorielle, qui n'est autre que l'indépendance statistique classique,
l'indépendance libre, qui a été introduite par Voiculescu et appliquée aux matrices aléatoires,
l'indépendance Booléenne.

Un problème de matrices aléatoires plus général que cela considéré par Voiculescu permet de définir une notion plus riche d'espace de probabilité non commutative, dans lequel les opérations algébriques ne sont pas seulement les polynômes, mais également des opérations encodées par des graphes. Ces espaces sont munis d'une notion d'indépendance qui unifie les trois notions ci-dessus.
Dans cet exposé introductif, je présenterai la combinatoire qui est derrière ces notions généralisées de probabilités non commutatives. Nous utiliserons des transformations de Möbius et nous verrons pourquoi les arbres sont des graphes plus importants que les autres pour les grandes matrices aléatoires.

Vendredi 4 novembre : Ferrán Valdez (Centre des sciences mathématiques, Université nationale autonome du Mexique (UNAM)) http://www.matmor.unam.mx/~ferran/index.html

Titre : Les billards polygonaux et les surfaces de translation de type infini

Résumé : Dans cet exposé on explique en termes élémentaires une construction qui associe à chaque billard polygonal une surface « plate » où le mouvement de la boule devient un flot linéaire. On expliquera la topologie de la surface qu'on obtient et, si le temps le permet, quelques problèmes de comptage associés au billard.

Vendredi 21 octobre : Kilian Raschel (Université de Tours, LMPT (Laboratoire de Mathématiques et Physique Théorique)) http://www.lmpt.univ-tours.fr/~raschel/

Titre : Marches aléatoires dans des cônes : exposants critiques.

Résumé : Le modèle combinatoire des marches dans des cônes connaît actuellement un essor considérable. Dans cet exposé nous parlerons de marches à grands pas, en dimension quelconque et de marches avec des poids. Nous nous concentrerons sur les exposants critiques qui apparaissent dans les asymptotiques :

des nombres d'excursions (marches reliant deux points fixés en un nombre donné de pas tout en restant dans un cône),
des nombres de marches de longueur prescrite.

Nous présenterons les travaux fondateurs de Denisov et Wachtel répondant à (1) ainsi que des résultats partiels et des conjectures liés à (2). Nous évoquerons des énoncés nouveaux de non-D-finitude des séries génératrices de comptage.
Il s'agit de résultats correspondant à des travaux en cours avec Julien Courtiel, Steve Melczer et Marni Mishna d'une part, Rodolphe Garbit et Sami Mustapha d'autre part.

Vendredi 30 septembre : Mathias Pétréolle

Titre : Algorithmes d'insertion pour les tableaux de dominos décalés

Résumé : Les tableaux de dominos classiques donnent une description combinatoire du produit de deux fonctions de Schur. De manière analogue, les tableaux de dominos décalés ont été introduits par Z. Chemli en 2016 dans le but de décrire le produit de deux fonctions Q-Schur (ou P-Schur). Dans mon exposé, je montrerai comment on peut définir un algorithme d'insertion (bijectif) à la Robinson-Schensted prenant en argument un mot bicolore et produisant deux tableaux de dominos décalés. J'en présenterai aussi l'algorithme inverse. Diverses conséquences seront évoquées : une règle de type Littlewood-Richardson pour les fonctions Q-Schur, le lien avec le super monoïde plaxique décalé, ...
Il s'agit d'un travail en collaboration avec Zakaria Chemli.

Vendredi 23 septembre : Mireille Bousquet-Mélou

Titre : Chemins à grands pas dans le quadrant

Résumé : L'énumération des chemins du quadrant formés de petits pas (c'est-à-dire de pas aux 8 plus proches voisins) est maintenant bien comprise. En particulier, leur série génératrice est différentiellement finie (solution d'une ED linéaire à coefficients polynomiaux) si et seulement si un certain groupe de transformations rationnelles, associé à l'ensemble des pas autorisés, est fini.
Il n'est pas du tout évident d'étendre à des marches à pas plus grands les méthodes qui ont permis cette classification. Guy Fayolle et Kilian Raschel ont décrit les difficultés qu'il faut attendre si on essaie de généraliser l'approche par analyse complexe (qui est très puissante dans le cas de petits pas). Dans cet exposé, je présenterai quelques progrès de l'approche algébrique via des séries formelles, dont la portée est de toutes façons limitée au cas de groupes finis.
(travail en commun avec Alin Bostan et Steve Melczer)

Vendredi 9 septembre : Vincent Despré http://www.gipsa-lab.fr/~vincent.despre/VincentDESPRE.html

Titre : Un codage pour les triangulations du tore.

Résumé : Dans le cas planaire, les triangulations sont en bijection avec un certain type d'arbres bourgeonnants. Cette bijection repose sur l'étude des bois de 'Schnyder et a de nombreuses implications intéressantes : codage optimal, sampling uniforme en temps linéaire, dessin sur une grille... Nous généralisons ce résultat au cas des triangulations du tore. La plupart des propriétés planaires sont conservées ; néanmoins, quelques propriétés ont un sens assez différent que nous discuterons. Ce travail a pour but d'être généralisé aux surfaces quelconques ; il est aussi intéressant de voir quels sont les nouveaux problèmes soulevés.

Combinatoire et interactions

Equipe du département Combinatoire et Algorithmique

du LaBRI