2011-2012
Vendredi 22 juin 2012 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (15)
Résumé de la 4e partie :
Avec cette 15e séance se termine la petite école.
Certaines parties sont pratiquement indépendantes du reste et peuvent probablement être comprises sans avoir assisté à tous les épisodes précédents, ainsi que pour les nouveaux arrivants.
En particulier avec l'introduction de l'idée de "démultiplication" d'un système d'équations.
Pour résumer les 14 premiers épisodes, l'Ansatz cellulaire est une méthodologie permettant dans un premier temps d'associer à certaines algèbres quadratiques Q des objets combinatoires (les Q -tableaux) , puis dans un deuxième temps de deviner des constructions de bijections à partir d'une représentation de ces algèbres avec des opérateurs "combinatoires".
Les deux exemples de base sont la correspondance RSK avec l'algèbre définie par la relation UD=DU+Id, et une bijection entre permutations et tableaux alternatifs avec l'algèbre du PASEP définie par DE=ED+E+D.
Pour conclure cette petite école, j'aborde une troisième partie en construction : comment deviner ces représentations combinatoires ?
Une méthode s'inspire de la théorie des histoires de fichiers (structure de données) en informatique (J. Françon, P. Flajolet et J. Vuillemin) et conduit aux opérateurs relatifs à la bijection du PASEP décrite dans un épisode précédent.
Une autre méthodologie est basée sur la notion de "démultiplication" des relations définissant l'algèbre quadratique Q.
Dans le cas de UD=DU+Id, on retrouve alors la représentation par opérateurs agissant sur les diagrammes de Young et conduisant à RSK.
On peut aussi retrouver les tables d'inversion des permutations et plus généralement la classique bijection entre involutions sans points fixes et "histoires d'Hermite".
Je terminerai avec la cerise sur le gâteau en abordant l'algèbre XYZ (ou algèbre associée au modèle "8-vertex") contenant en particulier l'algèbre associée aux matrices à signes alternants.
Résumé de la 3e partie :
Cf. (13)
Résumé de la 2e partie :
Cf. (10)
Résumé de la 1re partie :
Cf. (1)
voire
cf. (8)
pour celui plus spécifique aux 8e et 9e séances.
~~~~~
Vendredi 22 juin 2012 (Groupe de Travail) : Tony Guttmann (Department of Mathematics and Statistics, The University of Melbourne, Australia) http://www.ms.unimelb.edu.au/~tonyg/
Titre : Spanning trees, lattice Green functions and Mahler measures
Résumé :
On regular lattices the number of spanning trees grows exponentially, characterised by a constant known as the spanning tree constant.
This constant is known for two dimensional lattices, but not for three dimensional lattices (with one exception).
By recasting the definition in terms of the logarithmic Mahler measure of a Laurent polynomial, we can make use of recently proved results for Mahler measures to find the spanning tree constant for the four regular three-dimensional lattices.
Further, by generalizing the spanning tree constant to what we call a spanning tree generating function (STGF), we relate this to the lattice Green function (LGF), and comparing results between the LGF and the STGF gives possibly new hypergeometric function identities.
Joint work with Mathew Rogers (Illinois, USA).
Vendredi 15 juin 2012 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (14)
Résumé de la 3e partie :
Cf. (13)
Résumé de la 2e partie :
Cf. (10)
Résumé de la 1re partie :
Cf. (1)
voire
cf. (8)
pour celui plus spécifique aux 8e et 9e séances.
~~~~~
Vendredi 15 juin 2012 (Groupe de Travail) : Olivier Guibert
Titre : Un cas d'énumération de permutations triées par trois piles et deux symétries
Résumé :
On considère un cas particulier de permutations triées par trois piles et deux symétries (complément puis complément/miroir).
Leur énumération est obtenue grâce à une bijection avec certains chemins de Motzkin (dont les pas montants et horizontaux sont bicoloriés).
Travail en commun avec Mathilde Bouvel.
Vendredi 8 juin 2012 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (13)
Résumé de la 3e partie :
La troisième et dernière partie de la petite école forme le chapitre 5, chapitre de compléments et de futurs développements. (séances 13,14 et 15)
- Quelques rappels sur la théorie combinatoire des polynômes orthogonaux et des fractions continues (voir la petite école donnée sur le sujet en 2006/2007).
- Rappels sur les "histoires d'Hermite", "histoires de Laguerre" et "histoires de Laguerre subdivisées", leurs q-analogues et les bijections avec les involutions sans point fixes, les permutations vues comme paires d'involutions sans point fixes et les tableaux de Dyck.
- Lien avec la théorie des "histoires de fichiers" pour l'étude dynamique des structures de données en informatique (développée dans les années 80 par J. Françon, P. Flajolet et J. Vuillemin).
- Lien entre cette théorie des "histoires de fichiers" et les "représentations combinatoires" des algèbres de Weyl-Heisenberg (UD=DU+Id) et de l'algèbre du PASEP (DE=ED+E+D), correspondant respectivement aux polynômes d'Hermite (structure file de priorité) et de Laguerre (structure dictionnaire).
- Des polynômes d'Hermite et de Laguerre aux polynômes d'Askey-Wilson pour le PASEP général à cinq paramètres.
- Une notion de "démultiplication" des équations définissant ces algèbres pour construire d'autres bijections avec certains Q-tableaux. Le cas des matrices à signes alternants.
Résumé de la 2e partie :
Cf. (10)
Résumé de la 1re partie :
Cf. (1)
voire
cf. (8)
pour celui plus spécifique aux 8e et 9e séances.
~~~~~
Vendredi 8 juin 2012 (Groupe de Travail) : Mathilde Bouvel
Titre : Énumération de permutations triées par deux piles et une symétrie
Résumé :
On étudie les permutations triées par des opérateurs de la forme S.α.S, où S est l'opérateur usuel de tri par une pile et α est une symétrie du carré.
Ces permutations sont caractérisées par des motifs exclus (de type généralisé), et des conjectures sur leur énumération ont été proposées par A. Claesson, M. Dukes et E. Steingrimsson.
Ces conjectures portent sur une énumération raffinée selon la distribution de statistiques classiques sur les permutations.
Nous démontrons ces conjectures, en ajoutant quelques statistiques dans l'une d'elles.
Les preuves sont principalement à base d'arbres de génération, et utilisent aussi une bijection récente de S. Giraudo entre les permutations de Baxter et les permutations de Baxter tordues.
Il s'agit d'un travail en collaboration avec Olivier Guibert.
Vendredi 1er juin 2012 : Adrien Boussicault
Titre : Étude d'une suppression d'une case dans les tableaux boisés et dans les tableaux de Dyck
Résumé : Dans cet exposé, nous allons étudier la suppression d'une case dans les tableaux boisés ainsi que dans les tableaux de Dyck. L'objectif de ce travail est de mettre à jour des opérations qui trient les permutations en retirant au plus un seul motif 2-31.
Vendredi 25 mai 2012 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (12)
Résumé de la 2e partie :
Cf. (10)
Résumé de la 1re partie :
Cf. (1)
voire
cf. (8)
pour celui plus spécifique aux 8e et 9e séances.
Vendredi 11 mai 2012 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (11)
Résumé de la 2e partie :
Cf. (10)
Résumé de la 1re partie :
Cf. (1)
voire
cf. (8)
pour celui plus spécifique aux 8e et 9e séances.
Vendredi 4 mai 2012 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (10)
Résumé de la 2e partie :
Dans cette deuxième partie de la petite école, j'appliquerai la philosophie de l'Ansatz cellulaire pour l'algèbre quadratique du PASEP définie par la relation de commutation DE=ED+E+D.
Les tableaux alternatifs sont les Q-tableaux associés à cette algèbre.
Je définirai une représentation de l'algèbre Q du PASEP par des opérateurs combinatoires, en liaison avec la notion d'« histoires de Laguerre » venant de la théorie des polynômes orthogonaux.
Cette représentation conduit à la construction d'une bijection entre tableaux alternatifs et permutations.
Comme pour le cas de la correspondance RSK développée dans les séances précédentes, cette bijection définie par des « règles locales » peut être réécrite sous forme « globale », et apparait alors équivalente à une bijection de S.Corteel et P.Nadeau.
Une version « arboricole » est également possible.
Résumé de la 1re partie :
Cf. (1)
voire
cf. (8)
pour celui plus spécifique aux 8e et 9e séances.
~~~~~
Vendredi 4 mai 2012 (Groupe de Travail) : Valentin Féray
Titre : Fonctions quasisymétriques sur les diagrammes de Young
Résumé :
La théorie des représentations des groupes symétriques a été développée par Frobenius en 1900.
Comme pour tout groupe fini, tout se ramène à regarder une série de nombres χμλ indexés par deux partitions λ et μ : les caractères irréductibles.
Ce n'est que dans les années 1990 que Kerov et Olshanski ont l'idée de regarder, avec une bonne normalisation, ces nombres comme des fonctions de λ.
La première partie de l'exposé consiste à présenter l'approche de Kerov et Olshanski.
Dans cette approche, les caractères sont vus comme des fonctions "symétriques" de λ.
Dans une seconde partie, nous expliquerons qu'il est plus naturel de les voir comme des fonctions quasisymétriques, une extension des fonctions symétriques beaucoup étudiée ces dernières années.
Il n'est pas nécessaire (c'est d'ailleurs inutile) de connaître la théorie "classique" des représentations du groupe symétrique pour suivre l'exposé.
Vendredi 20 avril 2012 : Olivier Mallet (université de Rouen)
Titre : k-formes, nombres de Genocchi et tableaux boisés
Résumé : Les k-formes sont des partitions qui ont été introduites récemment par Lam, Lapointe, Morse et Shimozono en lien avec la théorie des fonctions symétriques. Dans cet exposé, issu d'un travail en collaboration avec Florent Hivert, on montre que la série génératrice des k-formes est une fraction rationnelle. La démonstration de ce résultat fait intervenir une certaine classe de k-formes, dites irréductibles, dont on conjecture qu'elles sont comptées par les nombres de Genocchi. On présente les pistes explorées jusqu'ici pour tenter de prouver cette conjecture. On conclut sur les liens entre les k-formes irréductibles et des objets étudiés par Adrien Boussicault et Jean-Christophe Aval : les tableaux de Dyck et les tableaux boisés.
~~~~~
Vendredi 20 avril 2012 : Jean-Philippe Dubernard (université de Rouen)
Titre : Une méthode générique d'énumération de différentes classes de polycubes dirigés
Résumé : Après avoir posé les définitions et propriétés permettant une extension des propriétés classiques des polyominos aux polycubes, nous exposons une méthode générique d’énumération de certains polycubes dirigés tri-dimensionnels. Celle-ci est basée sur la méthode de décomposition des polyominos colonne par colonne et son interprétation en termes d'équations fonctionnelles due à Bousquet-Mélou. Nous la généralisons ensuite au cas non dirigé, puis en dimension quelconque. Nous appliquons chacune de ces variantes à des sous-classes de polycubes et exprimons des fonctions les dénombrant selon le volume et la largeur ainsi que des propriétés les caractérisant.
Vendredi 13 avril 2012 : Anthony Labarre http://homepages.ulb.ac.be/~alabarre/ (Université de Louvain (K. U. Leuven), Belgique)
Titre : Distributions de cycles et distances entre génomes
Résumé :
Un grand nombre de mesures ont été proposées dans le but de comparer les génomes au niveau des gènes, et sont généralement basées sur des distances d'éditions impliquant des opérations inspirées par des mutations
constatées dans l'évolution.
Le "breakpoint graph" et ses variantes sont omniprésents dans l'étude de ces distances, et consistent en des
représentations graphiques des génomes à comparer permettant l'obtention d'un grand nombre de résultats (bornes, calcul exact en temps polynomial ou résultats de complexité).
Je présenterai ici le calcul de la distribution des cycles de ce graphe dans le cadre des permutations (signées et non signées), comment cette distribution permet d'estimer celles d'un certain nombre de distances, ainsi qu'une méthode automatique permettant d'obtenir des minorations sur ces distances dans le cas non signé.
[Ce travail a été réalisé avec Simona Grusea]
Vendredi 6 avril 2012 : Kerstin Weller http://www.maths.ox.ac.uk/contact/details/weller
Titre : Combinatorics of minor-closed classes of graphs
Résumé : In the past few years there has been a growing interest in finding properties of minor-closed classes of graphs. Typical examples of such properties are the number of graphs on n vertices, the probability that a graph on n vertices taken uniformly at random is connected etc. One of the first classes to be analyzed was the class of planar graphs and in fact many results known in this context extend to minor-closed classes, where the forbidden minors are 2-connected. In this talk, I am going to survey some well known results and present some examples indicating what might happen if we drop the condition that the excluded minors are 2-connected using tools from analytic combinatoric as well as methods from graph theory.
Vendredi 23 mars 2012 : Mireille Bousquet-Mélou
Titre : Intervalles de m-Tamari étiquetés
Résumé :
Lors de sa venue au Labri à l'automne 2010, François Bergeron a présenté -- entre autres -- deux conjectures sur l'énumération des intervalles de certains treillis, dits de m-Tamari.
Une conjecture pour des intervalles non-étiquetés, avec des nombres qui ressemblent à des nombres de cartes
et ont une série génératrice algébrique.
Une conjecture pour des intervalles étiquetés, avec des nombres qui ressemblent plutôt à des nombres d'arbres
de Cayley, voire de cartes de Cayley, si ce n'est que la notion reste à inventer.
La première formule a été prouvée avec Éric Fusy et Louis-François Préville-Ratelle, et présentée au GT l'an dernier.
La seconde a été prouvée, et très largement raffinée, avec ce même Louis-François et Guillaume Chapuy.
La preuve manipule des séries génératrices, et les bijections restent à inventer.
Ces questions sont -- conjecturalement -- reliées aux polynômes coinvariants diagonaux en trois jeux de variables.
Transparents : ici
Vendredi 16 mars 2012 : Antoine Gerbaud http://www-verimag.imag.fr/~gerbaud/index.html
Titre : Modèle du marcheur pour les réseaux d'interactions
Résumé : Des observations empiriques de la fin des années 1990 ont montré que la plupart des réseaux d'interactions (Internet, le web, les réseaux de collaboration) partagent des propriétés structurelles non triviales que ne possèdent pas les graphes aléatoires engendrés par le modèle classique d'Erdös-Rényi. Le modèle du marcheur tente de modéliser plus fidèlement ces réseaux. Je présenterai dans cet exposé certaines des propriétés des graphes aléatoires qu'il engendre : nombre d'arête, ordre de la plus grande composante connexe, présence de hubs.
Vendredi 24 février 2012 : Nicolas Bonichon
Titre : Ordonnancement, Combinatoire : un problème d'identité remarquable
Résumé :
« J'ai plein de choses à faire, mais par où commencer ?» Qui n'a jamais été confronté à cette angoissante question ? Après une introduction tout en douceur à l'ordonnancement, nous verrons que des préoccupations de ce genre permettent de définir des problèmes algorithmiques intéressants. Plus surprenant, l’un de ces problèmes fait apparaître des polynômes multivariés présentant une symétrie étonnante...
Bien que cet exposé présente plus de problèmes ouverts que de résultats, nous conclurons par quelques éléments de réponse à la question initiale : « par où commencer ?».
(Travail réalisé en collaboration avec Olivier Beaumont, Lionel Eyraud-Dubois et Loris Marchal)
Cf. http://www.labri.fr/perso/bonichon/malleable/.
Vendredi 17 février 2012 : Michele d'Adderio
Titre : Arithmetic matroids and Tutte polynomial
Résumé : I will discuss the notion of arithmetic matroid, whose main example is given by a finite list of elements in a finitely generated abelian group. Guided by the geometry of toric arrangements, I will present a combinatorial intepretation of the associated arithmetic Tutte polynomial, which generalizes Crapo's formula for the classical Tutte polynomial.
Vendredi 10 février 2012 : Alexandre Zvonkine
Titre : Arbres plans pondérés et une classe de polynômes extrémaux à coefficients rationnels
Résumé :
Les objets que nous étudierons dans cet exposé seront les hypercartes planes dont toutes les faces, à part la face extérieure, sont de degré 1.
Les arbres pondérés sont juste des outils pratiques pour manier plus facilement les hypercartes en question.
Deux questions seront explorées : pour un assortiment de degrés donné des sommets noirs et blancs, quand est-ce qu'une hypercarte correspondante existe ?
Quand est-ce qu'elle est unique ?
La motivation provient du problème suivant : soient deux polynômes P et Q à coefficients complexes, premiers entre eux, du même degré, et avec les multiplicités fixées de leurs racines.
Alors, quelle est la borne inférieure pour le degré de la différence P - Q ?
Cette borne est-elle toujours atteinte ?
Peut-on l'atteindre par des polynômes à coefficients rationnels ?
Toutes ces questions prennent leur origine dans la théorie des nombres.
Travail en commun avec Fedor Pakovich.
Vendredi 27 janvier 2012 : Andrey Bogatyrev (Institut des méthodes numériques, Moscou, Russie)
Titre : Graphical description of extremal polynomials
Résumé : Problems of conditional minimization of the uniform norm of polynomials or rational functions arise in different branches of science and technology. The solutions for those problems are very specific functions as they satisfy the so called equiripple property. This means that the vast majority of critical values (but not all of them!) lie in the set of (say) just two elements. An algebro-geometric Chebyshev construction describes such polynomials. As well they admit a representation in terms of certain weighted graphs.
Vendredi 20 janvier 2012 : Jean-François Marckert
Titre : Animaux dirigés, systèmes quadratiques et systèmes de réécritures
Résumé : Un animal dirigé A sur le réseau carré est une partie de N2 contenant l'origine 0, et telle que chaque point de A peut être atteint depuis 0 en restant à l'intérieur de A, uniquement par des pas (0,1) ou (1,0). Le cardinal de A s'appelle l'aire de A, et l'ensemble des sommets de N2 que l'on peut ajouter à A sans lui faire perdre sa qualité d'animal dirigé (AD), s'appelle le périmètre de A. On s'intéresse à la question du calcul de la série génératrice G(x, y) des AD sur réseau carré selon l'aire et le périmètre. Il s'agit d'une question centrale dans l'étude des AD, très directement liée au problème de la percolation dirigée, pour lequel le seuil critique, qui est sup { p : G( p, 1-p) = 1 }, est inconnu (alors qu'il existe de nombreuses méthodes pour calculer G(x,1)). Dans cet exposé, nous montrons l'équivalence entre le calcul de G et le calcul d'une solution à un système quadratique dont les inconnues sont des matrices (équations relativement proches de celles apparaissant pour le TASEP). Incapable de résoudre ce problème, nous montrons que des matrices infinies obtenues comme point fixe d'un système de type "système de réécriture", sont "solutions naturelles" de ce problème quadratique. Trouver un vecteur propre pour l'une d'elle devrait permettre de calculer G...
Vendredi 13 janvier 2012 : Valentin Féray
Titre : Un modèle simple d'arbres décorés pour les cartes unicellulaires
Résumé :
Dans cet exposé, nous nous intéressons aux cartes unicellulaires, c'est-à-dire aux graphes dessinés sur des surfaces de telle sorte que le complémentaire soit homéomorphe à un disque.
Nous montrons que l'on peut mettre ces objets en bijection avec une famille d'arbres décorés.
Malheureusement, l'existence de cette bijection est obtenue récursivement et on n'obtient donc pas de construction explicite.
Mais on peut faire en sorte que cette bijection préserve beaucoup de structure : le graphe sous-jacent à la carte (avec ses éventuelles boucles et arêtes multiples !) peut être décrit simplement à partir de l'arbre décoré.
Cette propriété permet de démontrer combinatoirement de nombreuses formules fines d'énumération de cartes unicellulaires.
Travail en commun avec Guillaume Chapuy et Éric Fusy.
Vendredi 6 janvier 2012 : Akka Zemmari
Titre : Complexité de la coloration probabiliste d'un anneau : une application de la transformée de Mellin
Résumé :
Dans cet exposé, on s'intéresse à la 3-coloration distribuée d'un anneau anonyme.
Nous étudions la complexité en temps et la bit-complexité de ce problème en présentant un algorithme probabiliste permettant de le résoudre et en montrant une borne inférieure générale.
L'analyse de l'algorithme utilise la transformée de Mellin, ce qui permet de donner la valeur exacte du temps moyen et non seulement une borne supérieure.
Nous en déduisons que l'algorithme présenté est optimal.
Travail en collaboration avec Y. Métivier, M. Robson et N. Saheb.
Vendredi 9 décembre 2011 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (9)
Résumé spécifique aux 8e et 9e séances : Cf. (8)
Résumé général sur ce sujet : Cf. (1)
~~~~~
Vendredi 9 décembre 2011 (Groupe de Travail) : Mathilde Bouvel
Titre : Une méthode algorithmique pour le calcul des séries génératrices des classes de permutations, et pour la génération aléatoire dans ces classes
Résumé :
L'objectif de l'exposé est de présenter un cheminement algorithmique qui, partant d'une classe de permutations C donnée par sa base (supposée finie), permet d'obtenir automatiquement des résultats énumératifs sur la classe C, et un générateur aléatoire de permutations de C.
Je commencerai par définir les classes de permutations, et expliquerai comment le point de vue de la décomposition par substitution peut être efficacement utilisé pour décrire les permutations de toute classe donnée dans le formalisme des structures combinatoires.
Une fois dans ce cadre classique, il devient aisé d'obtenir des résultats d'énumération et des générateurs aléatoires.
La difficulté principale est de passer « algorithmiquement » de la description d'une classe par sa base à un système d'équations la décrivant comme une structure combinatoire.
Je montrerai les principales étapes de ce cheminement, et esquisserai une explication plus détaillée de certaines d'entre elles.
Il s'agit d'un travail en commun avec Frédérique Bassino, Adeline Pierrot, Carine Pivoteau et Dominique Rossin.
Vendredi 2 décembre 2011 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (8)
Résumé spécifique aux 8e et 9e séances : Les deux prochains exposés (chapitre 3) de la petite école de combinatoire (2 et 9 décembre 2011) sont consacrés à la correspondance RSK revisitée par l'Ansatz cellulaire. Dans l'exposé du 2 décembre je rappellerai trois façons équivalentes de définir RSK : l'algorithme original par les insertions de Schensted (1961), la version géométrique avec les "ombres" et "lumières" due à l'orateur (1978), puis la version "locale" avec les "diagrammes de croissance" due à Fomin (1992). Dans le deuxième exposé, je montrerai comment à partir d'une représentation combinatoire de l'algèbre quadratique définie par UD=DU+Id, on peut construire de manière "guidée" une bijection qui n'est pas autre chose que RSK (mise sous la forme locale de Fomin). Enfin j'introduirai deux petites nouveautés dans l'esprit de cette petite école : l'automate planaire RSK (direct) et l'automate planaire RSK bilatère.
Résumé général sur ce sujet : Cf. (1)
~~~~~
Vendredi 2 décembre 2011 (Groupe de Travail) : Robert Cori
Titre : Permutations et partitions d'ensemble de genre 1
Résumé :
La notion d'hypercarte a permis de définir un genre pour les couples de permutations.
On prend ici pour définition du genre d'une permutation α, celui de l'hypercarte (ζn,α) où ζn est la permutation circulaire (1,2,...,n).
On sait depuis quelques années qu'avec cette définition les permutations de Sn de genre 0 correspondent aux partitions sans croisement de 1,2,...,n, introduites par G. Kreweras et étudiées extensivement par P. Edelman, R. Simion, R. Stanley et d'autres.
On s'intéresse ici aux permutations de genre 1, celles d'entre elles dont tous les cycles sont de la forme (a1, a2,...,ap), avec a1 < a2 < ... < ap, correspondent à des partitions ; mais il y en d'autres comme par exemple (1,4,3,2) ou (1,5,3)(2,6,4).
On proposera des formules d'énumération pour ces permutations et ces partitions.
On utilisera des bijections mais aussi des calculs sur les séries génératrices.
Ceci est un travail commun avec Gábor Hetyei.
Vendredi 25 novembre 2011 (Groupe de Travail) : Yvan Le Borgne
Titre : Promising q,t-Narayana polynomials
Résumé : Some q,t-Catalan polynomials are relatively famous polynomials symmetric in q and t that may be defined as an enumeration of Dyck paths of the same size according to two statistics. These polynomials appear in various, sometimes more algebraic, contexts. In a joint work with Mark Dukes, we were lead to the definition of a promising familly of q,t-Narayana polynomials that may defined as an enumeration of parallelogram polyonominoes with the same bounding box according to two statistics. It remains to place these polynomials in the litterature on the subject, but we can present a relatively natural path via the sandpile model between those two families of polynomials apparently both symmetric in q and t.
Vendredi 18 novembre 2011 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (7)
Résumé : Cf. (1)
~~~~~
Vendredi 18 novembre 2011 (Groupe de Travail) : Jean-Paul Bultel
Titre : Une déformation à un paramètre de l'algèbre de Farahat-Higman
Résumé : On montre, en introduisant une base appropriée, qu'une famille à un paramètre d'algèbres de Hopf introduite par Foissy interpole entre l'algèbre de Faà di Bruno et l'algèbre de Farahat-Higman. Les constantes de structure dans cette base sont des déformations des constantes de structure de l'algèbre de Farahat-Higman dans la base des projections des classes de conjugaison. On obtient pour ces constantes de structure déformées un analogue des formules de Macdonald.
Vendredi 4 novembre 2011 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (6)
Résumé : Cf. (1)
~~~~~
Vendredi 4 novembre 2011 (Groupe de Travail) : Mireille Bousquet-Mélou
Titre : Sur le profil des arbres plongés
Résumé :
Considérons un arbre binaire incomplet : chaque sommet à un fils droit et/ou un fils gauche.
Attribuons à la racine l'abscisse 0, et au fils gauche (resp. droit) d'un sommet d'abscisse i l'abscisse i-1 (resp. i+1), comme il se doit.
On démontre une formule produit simple donnant le nombre d'arbres binaires ayant n_i sommets d'abscisse i pour tout i.
On la démontre, on l'adapte à d'autres familles d'arbres, et on la raffine, le tout bijectivement.
Ce travail est réalisé avec Guillaume Chapuy, et motivé par les liens entre les arbres étiquetés et les cartes d'une part, la mesure ISE d'autre part.
Jeudi 3 novembre 2011 (Groupe de Travail) : Maciej Dołęga (université de Wrocław, Pologne)
Titre : Representation theory, symmetric functions and bipartite maps
Résumé : We define what is a representation of a finite group and we make an introduction to the theory of such objects. We define also an algebra of symmetric functions and some combinatorial objects called bipartite maps. We show some results which establish a connection between three of them and we state some conjectures which try to generelize this phenomena.
Vendredi 21 octobre 2011 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (5)
Résumé : Cf. (1)
Vendredi 14 octobre 2011 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (4)
Résumé : Cf. (1)
~~~~~
Vendredi 14 octobre 2011 (Groupe de Travail) : Julien Courtiel
Titre : Structure des cartes non orientables à une face
Résumé :
Cet exposé a deux objectifs :
le premier est de vous convier dans le monde mystérieux des cartes non orientables ;
le second, plus implicite, est de présenter l'orateur, nouveau doctorant, au reste de l'équipe.
Nous commencerons par introduire en douceur la notion de carte topologique (sur des surfaces générales) en tant que dessin d'un graphe sur une surface, et montrerons comment aboutir à une représentation plus simple d'un point de vue combinatoire.
Après cela, nous étudierons plus particulièrement ce qui était le sujet de mon mémoire de M2 : une approche bijective pour énumérer les cartes non orientables à une face.
Nous nous intéresserons principalement aux bijections (qui semblent assez visuelles) trouvées dans le cas où le genre vaut 1/2 (c'est-à-dire sur le plan projectif).
Puis selon le temps restant, nous exposerons ce qui a été tenté pour les genres supérieurs, notamment en introduisant la notion d'entrelacement.
Vendredi 7 octobre 2011 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (3)
Résumé : Cf. (1)
~~~~~
Vendredi 7 octobre 2011 (Groupe de Travail) : Alain Goupil
Titre : Polyominos inscrits
Résumé : Dans cet exposé, je discuterai de l’énumération de polyominos selon l’aire. L’approche proposée consiste à fixer le format d’un rectangle et à compter les polyominos inscrits dans ce rectangle. Un polyomino est inscrit dans un rectangle lorsqu’il touche chacun des quatre côtés du rectangle. Nous commencerons par construire la série génératrice des polyominos d’aire minimale en les caractérisant géométriquement puis nous considérons différentes extensions de cette construction.
Vendredi 30 septembre 2011 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (2)
Résumé : Cf. (1)
~~~~~
Vendredi 30 septembre 2011 (Groupe de Travail) : Yvan Le Borgne
Titre : Empilements de mots pour l'énumération des interactions supérieures dans les chemins de Dyck
Résumé : Objets classiques de la combinatoire énumérative, la seule chose que l'on ne compte peut-être pas sur les chemins de Dyck ce sont les méthodes pour les compter. Une interaction supérieure dans un chemin de Dyck est formée de deux sommets à la même hauteur définissant un facteur contenant une unique vallée. L'énumération des chemins de Dyck selon leurs nombres de pas et d'interactions supérieures contredit (temporairement) une décomposition récursive de ses chemins. Dans un précédent exposé, j'avais présenté deux méthodes permettant d'obtenir la série génératrice associée qui est un ratio de deux séries hypergéométriques basiques dont les raisons contiennent un coefficient algébrique. Après quelques rappels, cet exposé présentera une troisième méthode, inspirée de la théorie des empilements de Viennot, dont les étapes permettront de revisiter quelques-unes des méthodes d'énumération des chemins de Dyck.
Vendredi 23 septembre 2011 (Petite École de Combinatoire) : Xavier Viennot
Titre : L'Ansatz cellulaire (1)
Résumé :
Dans un premier temps, l'Ansatz cellulaire est une méthodologie permettant, par une approche cellulaire sur un réseau carré, d'associer des objets combinatoires (les Q-tableaux) à certaines algèbres quadratiques Q définies par relations et générateurs.
Cette notion est équivalente à la notion d'« automate planaire » ou de « réécritures planaires ».
L'exemple de base est l'algèbre définie par la relation UD = DU + Id (ou algèbre de Weyl-Heisenberg, bien connue en physique).
Les Q-tableaux associés sont les permutations.
Un deuxième exemple est l'algèbre définie par la relation DE = qED + E + D qui est à la base de la résolution en physique des systèmes dynamiques du modèle du PASEP (partially asymmetric exclusion process) avec le calcul des probabilités stationnaires.
Des Q-tableaux associés ont fait récemment l'objet de nombreuses études combinatoires sous le nom de « tableaux alternatifs », « permutation tableaux » ou encore « tree-like tableaux ».
Une autre algèbre, ou algèbre du modèle « 8-vertex », permet de retrouver les fameuses « matrices à signes alternants », les « partitions planes », les « configurations de chemins » ne se coupant pas ou encore des « pavages » sur réseaux planaires.
Dans un deuxième temps, l'Ansatz cellulaire permet la construction « guidée » de bijections entre les Q-tableaux et d'autres objets combinatoires, dès que l'on a une « représentation » par opérateurs combinatoires de l'algèbre quadratique Q.
L'exemple de base pour l'algèbre de Weyl-Heisenberg est la classique correspondance RSK (Robinson-Schensted-Knuth) entre permutations et paires de tableaux de Young.
Pour l'algèbre du PASEP on obtient une bijection entre tableaux alternatifs et permutations.
La théorie combinatoire des polynômes orthogonaux joue un rôle important, ainsi que la théorie des « histoires de fichiers » introduite en informatique pour l'analyse du coût intégré des structures de données.
Nous terminerons par des extensions et problèmes ouverts, en particulier pour l'algèbre du modèle « 8-vertex ».
Cf. http://web.me.com/xgviennot/Xavier_Viennot/petite_école.html.
Vendredi 16 septembre 2011 : Valentin Féray
Titre : Combinatoire des polynômes zonaux
Résumé :
Les fonctions de Schur (introduites par Jacobi) sont des fonctions symétriques avec des propriétés surprenantes, tant du point de vue de la combinatoire que de la théorie des représentations.
Dans cet exposé, nous considèrerons une autre famille de fonctions symétriques, les polynômes zonaux qui peuvent être considérés comme des analogues des fonctions de Schur.
Le résultat principal est une formule combinatoire relativement simple pour les polynômes zonaux.
Les objets combinatoires mis en jeu sont des triplets d'appariements, que l'on peut interpréter comme des graphes dessinés sur une surface (orientable ou non).