2014-2015
Mardi 7 juillet : Kilian Raschel (Université de Tours, LMPT (Laboratoire de Mathématiques et Physique Théorique)) http://www.lmpt.univ-tours.fr/~raschel/
Titre : Fonctions discrètes harmoniques dans le quart de plan
Résumé : Dans cet exposé nous nous intéressons aux fonctions discrètes harmoniques dans des cônes (en particulier dans le quart de plan). La série génératrice de ces fonctions harmoniques satisfait une équation fonctionnelle proche de celle obtenue dans le contexte de l'énumération de marches dans le quart de plan. Nous montrons le lien entre ces fonctions harmoniques et une famille à un paramètre d'applications conformes. Une des motivations à l'étude de ces fonctions est qu'elles permettent le conditionnement au sens de Doob de marches aléatoires.
Vendredi 26 juin : Lucas Gerin (Centre de Recherches en Mathématiques Appliquées (CMAP), École Polytechnique CNRS) http://gerin.perso.math.cnrs.fr/
Titre : Plus longue sous-suite croissante : point de vue probabiliste
Résumé :
Dans les années 1960, Hammersley a introduit un système de particules dans le but de démontrer (sans y arriver) que la longueur de la plus longue sous-suite croissante d'une permutation uniforme de n éléments
est de l'ordre de 2√n.
Dans les années 90, plusieurs auteurs ont réussi à compléter l'approche d'Hammersley pour obtenir une preuve
probabiliste de ce résultat, l'objectif de cet exposé est de présenter cette stratégie.
N. B. : il s'agit d'un exposé de type "Groupe de Travail", dans le sens où ce sont des résultats pas de moi, vieux, et considérés comme "bien connus", c'est-à-dire connus de très peu de gens.
Vendredi 12 juin : Claire Pennarun
Titre : On the enumeration of planar Eulerian orientations
Résumé :
Eulerian planar maps are planar maps with all vertices of even degree.
The number of Eulerian planar maps with a fixed number of edges m is well known, and they are in bijection with many combinatorial families, such as balanced Eulerian trees or bi-cubic maps.
Planar Eulerian orientations are directed planar maps in which the in- and out-degrees of every vertex are equal.
We first count the number of planar Eulerian orientations for m ≤ 12 (m is the number of edges) thanks to an encoding based on bilateral Dyck words.
The values found (2, 10, 66, 504, 4216, 37548...) do not match with any known series from the OEIS.
We then present a sequence of algebraic series giving lower and upper bounds of the growth rate of planar Eulerian orientations.
We show in particular that the growth rate of planar Eulerian orientations is between 10.69m and 12.94m.
Vendredi 5 juin : Ali Chouria (Université de Rouen, LITIS (Laboratoire d'informatique, de traitement de l'information et des systèmes)) http://www.univ-rouen.fr/version-francaise/outils/m-chouria-ali-230345.kjsp
Titre : Fonctions symétriques sur les mots et théorème de Redfield-Pólya
Résumé :
Depuis une vingtaine d’années de multiples généralisations des fonctions symétriques, souvent reliées à la théorie des représentations de certaines algèbres, ont été étudiées.
Ces structures admettent des bases indexées par des objets combinatoires (mots, partitions, compositions, partitions d’ensemble en listes, arbres ...) et sont décrites de façon combinatoire et algorithmique.
Les applications de ces algèbres sont vastes puisqu’elles interviennent en mathématique, physique et chimie.
C'est dans ce cadre que nous présentons les applications pour l’énumération de certains objets.
Nous donnons des versions non-commutatives du théorème d’énumération de Redfield-Pólya (qui a été publié par John Howard Redfield en 1927 puis indépendamment redécouverte en 1937 par George Pólya).
Ce théorème peut s'énoncer dans l'algèbre des fonctions symétriques classiques et permet d'énumérer les orbites de l'action d'un groupe fini sur un ensemble fini.
Nous l'étudions ici dans l'algèbre des fonctions symétriques sur les mots WSym introduite par Rosas et Sagan en 2004 et dans d'autres algèbres de Hopf combinatoires.
Vendredi 29 mai : Vincent Delecroix
Titre : Séquences récurrentes, triangulations L∞-Delaunay et un problème d'empilement
Résumé :
Nous présentons une borne optimale pour la récurrence des transformations de l'intervalle [0,1].
Notre preuve de ce résultat est géométrique est consiste à comprendre les empilements optimaux pour la "pseudo-métrique" dist(x,y) = |xy|.
Comme dans le cas euclidien, une preuve possible est via les triangulations de Delaunay.
Mais contrairement au cas euclidien, nous utiliserons des triangulations Delaunay pour la métrique L∞.
Si le temps le permet, on jouera aussi avec des permutations.
Vendredi 22 mai : Jean-Baptiste Priez (Laboratoire de Recherche en Informatique, Université Paris-Sud 11)
Titre : Énumération exacte d’automates acycliques minimaux et bijection avec les fonctions de parking généralisées
Résumé :
Les fonctions de parking sont intéressantes pour de nombreuses raisons.
Elles sont en bijection avec les séquences de Prüfer, les chemins de Dyck décorés, etc. et sont liées à l’inversion de Lagrange, aux polynômes harmoniques diagonaux, etc.
En particulier, elles sont en bijection avec les forêts d’arbres enracinés, autrement dit avec les endo-fonctions acycliques.
En 2002, Jim Pitman et Richard P. Stanley ont introduit une généralisation des fonctions de parking.
Nous verrons qu'une sous-famille de ces fonctions de parking généralisées est en bijection avec l’ensemble des fonctions de transition des automates finis déterministes acycliques.
Nous expliciterons une bijection et nous montrerons que cette dernière transporte une information précieuse sur les langages droits des états de l'automate.
Nous utiliserons cette information pour extraire et énumérer les automates acycliques non-initiaux pour lesquels tous les langages droits des états sont distincts.
Enfin par une technique usuelle de graphes, nous obtiendrons une formule exacte d’énumération des automates acycliques minimaux.
Vendredi 17 avril : Mireille Bousquet-Mélou
Titre : Chemins de Gessel dans le quadrant
Résumé :
L'énumération des chemins à pas prescrits confinés dans le quadrant, et leur classification selon la nature de la série
génératrice associée (algébrique, différentiellement finie, non différentiellement finie) s'est révélée un beau sujet combinatoire au cours de la décennie écoulée.
La classification des modèles à petits pas est maintenant terminée : la série qui compte les chemins du quadrant est D-finie si et seulement si un certain groupe associée à ce modèle est fini.
Du côté des modèles D-finis, un problème subsistait encore : donner une preuve simple de l'algébricité des chemins de Gessel (à pas E, O, NE, SW), d'abord établie à grands coups de calcul formel, puis en utilisant une machinerie sophistiquée d'analyse complexe, qui sort du champ des séries algébriques puisqu'elle fait intervenir les fonctions P et zeta de Weiertrass.
Je présenterai une preuve qui reste au niveau des séries formelles et ne brasse que des équations polynomiales.
Jeudi 9 avril : Tony Guttmann (Department of Mathematics and Statistics, The University of Melbourne, Australia) http://www.ms.unimelb.edu.au/~tonyg/
Titre : Integrability, Solvability and Enumeration
Résumé :
There are a number of seminal two-dimensional lattice models that are integrable, but have only been partially solved, in the sense that only some properties are fully known (e.g. the two-dimensional Ising model, where the free-energy is known, but not the susceptibility).
Alternatively, critical properties are known for some lattices but not others.
For example, the critical point of the self-avoiding walk model is known rigorously for the honeycomb lattice, but not for other lattices.
Similarly for the q-state Potts model and both bond and site percolation.
The critical manifold of the former is known only for some lattices, likewise the percolation threshold is known only for some lattices.
A range of numerical procedures exist, based on exact enumeration, or other numerical work, such as calculating the eigenvalues of transfer matrices, which, when combined with various structural invariants seem to give exact results in those cases that are known to be exact, but can be used to give increasingly precise estimates in those cases which are not exactly known.
Reasons for this partial success are not well understood.
In this talk I will describe four such procedures, and demonstrate their performance, and speculate on their partial success.
Vendredi 27 mars : Julien Courtiel (Université Simon Fraser, Vancouver, Canada) http://www.sfu.ca/~jcourtie/
Titre : Nouvelles bijections entre tableaux de Young, diagrammes d'arcs et marches dans le treillis de Young
Résumé :
Les objets étudiés en combinatoire énumérative montrent une grande diversité : marches, permutations, tableaux de Young, diagrammes d'arcs...
La liste est longue.
Bien que les apparences laissent croire à une absence de corrélation, l’œil avisé saura voir les liens qui unissent ces objets entre eux.
Cet exposé présentera quelques uns de ces liens.
L'objectif principal est la preuve d'une conjecture de Sophie Burrill, qui stipule que le nombre de tableaux de Young dont la hauteur est majorée par 2k est égal au nombre d'appariements ouverts ne présentant pas de nesting d'ordre k+1.
Cela sera l'occasion de présenter la très belle bijection de Chen, Deng, Du, Stanley, Yan entre partitions d'ensemble et marches vacillantes.
Nous donnerons par la suite la description de quelques classes combinatoires en bijection avec les appariements ouverts.
Nous prendrons alors notre plus grand shaker et secouerons tout cela afin d'obtenir la preuve d'une conjecture fraîchement servie (avec éventuellement quelques olives si le temps le permet).
Vendredi 13 février : Thierry Monteil, équipe CALIN du LIPN, université Paris 13
Titre : Pavages : quantifier l'apériodicité d'un jeu de tuiles
Résumé :
Un jeu de tuiles de Wang est un ensemble fini de carrés unités dont on a colorié chaque côté.
Un jeu de tuiles T pave le plan si celui-ci peut être recouvert par des translatés de copies d'éléments de T (selon Z^2), de sorte que les arêtes en contact de deux tuiles adjacentes soient de même couleur.
Un jeu de tuiles est dit apériodique s'il pave le plan mais si aucun pavage obtenu n'est invariant par une translation.
La plupart des jeux de tuiles apériodiques sont construits de façon autosimilaire (via une règle de substitution).
Le but de cet exposé est d'introduire des invariants permettant de quantifier le niveau d'apériodicité d'un jeu de tuiles de Wang.
L'un des invariants est de nature topologique, l'autre est métrique.
Ils reposent sur la manière dont le jeu de tuiles pave d'autres objets que le plan.
Ces invariants nous permettent de démontrer que les jeux de tuiles de Kari et Culik ne sont pas gouvernés par une construction autosimilaire, car trop apériodiques.
Vendredi 23 janvier : Vincent Pilaud http://www.lix.polytechnique.fr/~pilaud/, Laboratoire d'informatique de l'École Polytechnique (LIX)
Titre : Combinatoire des arbres Cambriens
Résumé :
Les arbres Cambriens fournissent une généralisation naturelle des arbres binaires de recherche, dans laquelle chaque sommet peut avoir un parent et deux enfants, ou deux parents et un enfant.
Ce premier exposé présentera la combinatoire de ces arbres, et en particulier une correspondance entre les permutations signées et les arbres Cambriens à niveaux, similaire à la correspondance de Robinson-Schensted ou à la correspondance sylvestre.
On abordera aussi la combinatoire des paires d'arbres Cambriens jumeaux, qui sont comptés par des nombres Baxter-Cambriens encore assez mystérieux.
Cet exposé est partiellement basé sur des travaux en commun avec Grégory Chatel (Univ. Marne la Vallée) et Carsten Lange (Univ. Munich).
~~~~~
Titre : Algèbres de Hopf Cambriennes
Résumé :
Ce deuxième exposé présentera des applications des arbres Cambriens à la construction d'algèbres de Hopf combinatoires.
On présentera en particulier l'algèbre Cambrienne qui généralise l'algèbre de Loday-Ronco sur les arbres binaires, et on étudiera certaines de ses propriétés (formules combinatoires pour les produits et coproduits, bases multiplicatives, indécomposables, ...).
Si le temps le permet, on abordera aussi des généralisations naturelles de cette algèbre, dont les bases sont indexées par les paires d'arbres Cambriens jumeaux et par les arbres Schröder Cambriens.
Cet exposé est basé sur un travail en commun avec Grégory Chatel (Univ. Marne la Vallée).
Vendredi 19 décembre : Xavier Viennot
Titre : La méthodologie de l'ansatz cellulaire appliquée aux tableaux du PASEP 2/2
Résumé : Cf. (1)
Vendredi 12 décembre : Xavier Viennot
Titre : La méthodologie de l'ansatz cellulaire appliquée aux tableaux du PASEP 1/2
Résumé :
Je montrerai le lien entre les exposés récents au GT de Patxi Laborde Zubieta et d'Olya Mandelshtam et la théorie de l'ansatz cellulaire, théorie qui avait l'objet d'une petite école en 2011/12.
Je ferai un rappel pédagogique sur quelques traits essentiels de cette théorie : comment associer un tableau (appelé Q-tableau) à une algèbre quadratique Q d'un certain type, comment définir une notion d'algèbre réciproque.
Les tableaux alternatifs et les tableaux boisés apparaissent comme les Q-tableaux associés à l'algèbre du PASEP (définie par la relation DE=ED+E+D) et à son algèbre réciproque.
Rappelons que le PASEP (partially asymmetric exclusion process) est un modèle très célèbre en physique des systèmes dynamiques et les tableaux associés permettent d'interpréter les probabilités stationnaires du modèle.
La théorie générale de l'ansatz cellulaire donne une méthode pour construire des bijections entre ces tableaux et d'autres objets combinatoires à partir d'une représentation combinatoire de l'algèbre Q.
Dans le cas de l'algèbre du PASEP, je rappellerai une telle bijection entre les tableaux alternatifs et les permutations.
Cette bijection permet de retrouver bijectivement le résultat de Patxi sur le nombre de coins occupés dans les tableaux boisés de taille n.
Dans un deuxième exposé, je rappellerai une autre méthode permettant de construire des bijections faisant intervenir ces Q-tableaux, appelée « démultiplication » des équations définissant l'algèbre quadratique Q.
Dans le cas de l'algèbre du PASEP, nous obtenons une (nouvelle) bijection entre les tableaux alternatifs et des paires de mots.
Cette bijection mériterait d'être étudiée.
Dans le cas des tableaux alternatifs de Catalan (associée au TASEP) cette bijection devient la bijection introduite dans l'exposé d'Olya entre ces tableaux de Catalan et certaines paires de chemins.
Enfin, si le temps le permet, je rappellerai que dans le cas de l'algèbre définie par la relation UD=DU+Id, certains Q-tableaux associés sont les (graphes de) permutations et une bijection associée à une représentation combinatoire est l'algorithme RSK (Robinson-Schensted-Knuth).
De plus la méthode de démultiplication des équations conduit naturellement à la même correspondance RSK.
Vendredi 5 décembre : Vincent Delecroix
Titre : La fonction de Fabius
Résumé :
Considérons la variable aléatoire obtenue en sommant des variables aléatoires indépendantes uniformes sur [0,2-n] (le support de cette variable est dans [0,1]).
Sa distribution est partout C∞ mais nulle part analytique !
C'est pour cette raison qu'elle a été introduite par Fabius (en 1966).
J'expliquerai par une promenade dynamique via le mot de Thue-Morse comment construire cette fonction.
Vendredi 28 novembre : Adrien Boussicault
Titre : Jardinage d'automne : comment réussir une transplantation d'arbres dans vos polyominos dirigés convexes
Résumé :
En tant que combinatoriciens, nous avons tous quelques arbres qui poussent au fond du jardin.
Nous avons aussi quelques polyominos qui prennent de la poussière sur nos étagères.
Dans cet atelier, grâce à la transplantation, nous allons montrer comment donner une seconde vie à tous nos polyominos dirigés convexes pour mettre en valeur nos arbres préférés.
Nous utiliserons cette méthode pour obtenir facilement et instantanément les fonctions génératrices des polyominos dirigés convexes avec différentes combinaisons de statistiques : hauteur, largeur, longueur de la dernière ligne/colonne, nombre de coins.
Nous énumérerons différentes familles de polyominos dirigés convexes : les polyominos symétriques, les polyominos parallélogrammes et le cas difficile des polyominos dirigés k-convexes.
Pour les travaux pratiques, n'oubliez surtout pas d'apporter avec vous tous vos outils de jardinages : fonctions génératrices, mots et expressions rationnelles.
Il s'agit d'un travail réalisé en commun avec Simone Rinaldi et Samanta Socci de l'université de Sienne en Italie.
Vendredi 14 novembre : Philippe Duchon
Titre : Une extension de l'algorithme de von Neumann pour simuler combinatoirement des variables exponentielles
Résumé :
Dans une note datant du début des années 1950, John von Neumann a décrit un algorithme très simple, ne faisant intervenir que des comparaisons et des compteurs, pour simuler de manière exacte une variable aléatoire suivant la loi exponentielle ; algorithme qui a d'ailleurs été analysé en détail par Flajolet et Saheb dans les années 1980.
Von Neumann termine sa note par une indication intrigante, affirmant que la méthode peut facilement s'étendre à « toute distribution satisfaisant une équation différentielle du premier ordre ».
À ma connaissance, cette extension n'a jamais été explicitée, ni même précisée en ce qui concerne les conditions d'applicabilité.
Je présenterai une interprétation possible de la remarque de von Neumann, et un algorithme de simulation qui ressemble effectivement à une généralisation raisonnable de son algorithme.
En l'occurrence, il s'agit de faire porter l'équation différentielle non pas sur la densité, mais sur la probabilité complémentaire de la fonction de répartition (« fonction de survie »).
Vendredi 7 novembre : Olya Mandelshtam http://math.berkeley.edu/people/grad/olya-mandelshtam Département de Mathématiques de l'Université de Californie, Berkeley, États-Unis d'Amérique
Titre : A Determinantal Formula for Catalan Tableaux and TASEP Probabilities
Résumé : We present a determinantal formula for the steady state probability of each state of the TASEP (Totally Asymmetric Simple Exclusion Process) with open boundaries, a 1D particle model that has been studied extensively and displays rich combinatorial structure. These steady state probabilities are computed by the enumeration of Catalan tableaux, which are certain Young diagrams filled with α's and β's that satisfy some conditions on the rows and columns. We construct a bijection from the Catalan tableaux to weighted lattice paths on a Young diagram, and from this we enumerate the paths with a determinantal formula, building upon a formula of Narayana that counts unweighted lattice paths on a Young diagram. Finally, we provide a formula for the enumeration of Catalan tableaux with a given number of rows, which corresponds to the steady state probability that in the TASEP on a lattice with n sites, precisely k of the sites are occupied by particles. This formula is an α ∧ β generalization of the Narayana numbers. We conclude with some extensions to a two-species PASEP, in which there are particles of type 1 and 2 hopping right with rate 1 and hopping left with rate q, with only type 2 particles being able to enter and exit. We describe certain Catalan-like tableaux for the q=0 case, and two-species alternative tableaux for the q=1 case.
Vendredi 24 octobre : Jean-François Marckert
Titre : Un nouveau codage pour les processus de coalescence. Applications aux cas additif et multiplicatif.
Résumé :
Travail commun avec Nicolas Broutin (INRIA, Rocquencourt).
Les processus de coalescence ont pour but de décrire l'évolution de la composition d'un mélange composé de particules (ou d'amas de particules), qui ont tendance à s'agglomérer selon un certain mécanisme aléatoire.
Certains modèles peuvent être codés au niveau des particules par des structures combinatoires aléatoires qui évoluent avec le temps.
Par exemple, le coalescent multiplicatif peut se représenter sous la forme de l'évolution de la taille des composantes connexes dans G(n,p) (= Graphe d'Erdös-Rényi) lorsque p évolue.
Dans ce travail, nous présentons un nouveau codage qui permet de représenter ces processus sous la forme d'agglomération d'intervalles de la ligne.
Cela mène à de nouveaux résultats, en particulier, dans le cas du coalescent multiplicatif.
Vendredi 17 octobre : Patxi Laborde Zubieta
Titre : Dénombrement des coins occupés dans les tableaux boisés
Résumé : Le bord des tableaux boisés joue un rôle important dans le lien qu'il y a entre ces objets et le modèle du PASEP. Notamment, les coins correspondent aux sites où un changement d'état est possible. Dans cet exposé, nous verrons que dans l'ensemble des tableaux boisés de taille n, qui est de cardinal n!, il y a n! coins occupés. J'exposerai deux preuves de ce résultat, la première utilise la structure récursive des tableaux boisés donnée par l'algorithme d'insertion, tandis que la deuxième dénombre une statistique sur les permutations équivalente à celle des coins occupés. Enfin, je vous présenterai une conjecture raffinant ce résultat : dans les classes non-ambiguës il y a autant de coins occupés que de tableaux boisés.
Vendredi 10 octobre : Wenjie Fang http://www.liafa.univ-paris-diderot.fr/web9/equiprech/fichepers_fr.php?id=355, Université Paris Diderot - Paris 7, LIAFA
Titre : Une généralisation de la relation des quadrangulations sur les constellations et les hypercartes
Résumé : Les constellations sont des cartes spéciales qui généralisent la notion de carte en terme de factorisation de permutations. Dans cet exposé, nous généralisons une relation énumérative de Jackson et Visentin (1990) entre les quadrangulations ordinaires et biparties. Nous présenterons une relation similaire entre les constellations et les hypercartes en passant par une factorisation de caractère. Avec cette relation, on retrouve le comportement asymptotique des hypercartes établi dans Chapuy (2009), avec une preuve simplifiée.
Vendredi 26 septembre : Matjaž Konvalinka http://www.fmf.uni-lj.si/~konvalinka/, université de Ljubljana (Slovénie)
Titre : The role of residue and quotient table in the theory of k-Schur functions
Résumé : Recently, residue and quotient tables were defined, and were used to describe strong covers in the lattice of k-bounded partitions. In the talk, we will show how residue and quotient tables can be used to describe many other results in the theory of k-bounded partitions and k-Schur functions, including k-conjugates, weak horizontal and vertical strips, and the k-Murnaghan-Nakayama rule. If time permits, evidence will be presented for the claim that one of the most important open questions in the theory of k-Schur functions, a general rule that would describe their product, can also be concisely stated in terms of residue tables.
Vendredi 19 septembre : Adrian Tanasa https://lipn.univ-paris13.fr/~tanasa/?lang=fr, équipe CALIN du LIPN, université Paris 13
Titre : Combinatoire algébrique et théories quantiques des champs
Résumé :
La combinatoire (algébrique, analytique, etc.) joue un rôle central dans le formalisme de théories quantiques des champs (TQC).
Dans ce séminaire, j'introduirai d'abord quelques notions de TQC : les graphes de Feynman, leur fonction génératrice et finalement la renormalisation (c.-à-d. la manière dont on manipule en TQC des intégrales, dites de Feynman, divergentes).
J'introduirai ensuite la notion d'algèbre de Hopf et j'illustrerai cela avec l'exemple de l'algèbre de Connes-Kreimer de graphes de Feynman.
Cette construction code d'une manière élégante la combinatoire de la renormalisation dans une structure d'algèbre de Hopf.
Si le temps le permet, j'indiquerai comment cela se généralise pour des TQC non-commutatives, où les graphes sont remplacés par des cartes combinatoires.
Vendredi 12 septembre : Robert Cori
Titre : Arbres binaires et « quatre couleurs »
Résumé :
En 1986 nous avons présenté avec Serge Dulucq une communication au Colloque sur les Arbres en Algèbre et Programmation (CAAP) dans laquelle nous donnions une preuve de l'équivalence entre l'existence d'une 4-coloration pour toute carte planaire et l'égalité de deux sous-ensembles du produit cartésien de deux monoïdes libres.
Une étape de notre preuve consistait en l'équivalence de ces propriétés avec une construction sur les arbres binaires.
Récemment (en 2012) B. Cooper, E. Rowland et D. Zeilberger (voir http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/4ct.html) publient un résultat semblable et en tirent des conséquences plus intéressantes que notre premier résultat.
Je me propose de présenter ces deux approches.