2009-2010

Vendredi 25 juin 2010 : Arvind Ayer http://www.math.rutgers.edu/~ayyer/home/

Titre : Pattern avoidance and alternating sign matrices

Résumé : In joint work with Robert Cori, I introduce a new class of objects called gog words that are in natural bijection with alternating sign matrices. We then define a notion of pattern avoidance on these words which we show corresponds to a certain structure on monotone triangles. Moreover, we show that gog words which avoid the pattern 312 are in natural bijection with a subset of totally symmetric self-complementary plane partitions.

Vendredi 18 juin 2010 : Alice Jacquot (LIP6)

Titre : Bijection entre cartes combinatoires et arbres enrichis pour l'énumération de lambda-termes

Résumé : Les système BCI et BCK sont des systèmes de logiques intuitionnistes dont les formules peuvent être représentés par des lambda-termes. Un terme BCI est un lambda-terme sans variable libre où chaque variable déclarée apparaît exactement une fois. Les arbres syntaxiques des lambda termes sont des arbres unaires-binaires enrichis d'arcs retour liant feuilles et nœuds unaires. L'arbre syntaxique d'un BCI est un arbre enrichi où chaque feuille est liée à un et un seul nœud unaire et réciproquement. Ces arbres sont en bijection avec la cartes combinatoire où tous les sommets sont de degré 3. Il en découle l'asymptotique et un générateur aléatoire pour les BCI. La bijection peut également s'étendre à d'autres classes d'arbres enrichis, comme les BCK.

Vendredi 11 juin 2010 : Mike Robson

Titre : Les Pics de Permutations

Résumé : Une formule pour le nombre de permutations de {1..L} ayant M pics peut être déduite d'une équation sur une série génératrice. J'essaierai de donner une explication combinatoire de cette formule.

Vendredi 4 juin 2010 : Pascal Weil

Titre : Sous-groupes des groupes libres

Résumé : La combinatoire des sous-groupes finiment engendrés des groupes libres est un sujet fascinant. Ces sous-groupes sont tous libres, donc dotés d'un rang, de bases, etc : la situation pourrait sembler aussi claire que celle des sous-espaces d'un espace vectoriel de dimension finie. Mais il n'en est rien, la façon dont ils sont immergés dans le groupe libre ambiant peut être extrêmement complexe : un sous-groupe du groupe libre de rang 2 peut avoir un rang arbitrairement grand, des sous-groupes de même rang peuvent ne pas être échangeables par un automorphisme, etc.
Un outil apparu au début des années 1980 a révolutionné l'étude de ces sous-groupes : il s'agit de leur représentation par des graphes, dits de Stallings. Ce sont des graphes orientés finis, dont les arêtes sont étiquetés par des lettres (il est donc loisible de les voir comme des automates), soumis à quelques contraintes simples, et chaque sous-groupe est uniquement déterminé par un tel graphe. De plus, le graphe représentant un sous-groupe H est effectivement (et rapidement) calculable à partir d'un ensemble de générateurs de H. L'intérêt est double : d'une part on dispose d'une représentation visuelle intuitive du sous-groupe; et d'autre part, la porte est ouverte à des développements algorithmiques efficaces.
Je commencerai par expliquer comment calculer le graphes de Stallings d'un sous-groupe, et comment ces graphes permettent le calcul d'invariants simples : le rang, l'indice, une base du sous-groupe. Nous verrons aussi comment ils permettent de résoudre efficacement le problème du mot généralisé (étant donné u et H, est-ce que u est dans H ?), le problème de la conjugaison (étant donnés des sous-groupes H et K, sont-ils conjugués ?). Le calcul de l'intersection de deux sous-groupes, très simples avec les graphes de Stallings, ouvre la voie de la discussion de la conjecture de Hanna Neumann (ouverte depuis 1956...) sur la borne optimale du rang de cette intersection.
Je présenterai aussi quelques propriétés des sous-groupes (pureté, malnormalité, minimalité au sens de Whitehead) dont la décision se fait (plus ou moins efficacement) à l'aide de ces graphes, parfois en mobilisant des notions qui appartiennent traditionnellement à la théorie des automates (apériodicité, minimisation au sens des langages rationnels).
Enfin, j'essaierai de présenter des résultats récents sur les propriétés asymptotiques des sous-groupes du groupe libre, appuyées sur plusieurs distributions naturelles de ces sous-groupes.

Vendredi 28 mai 2010 : David Renault

Titre : Algorithmes de construction de graphes de Cayley planaires localement finis

Résumé : Imaginons vouloir utiliser les propriétés géométriques du plan pour effectuer un calcul générique. Dans le plan euclidien, cela pourrait correspondre à utiliser une structure discrète (par exemple la grille infinie) à laquelle on adjoindrait un modèle de calcul (par exemple un automate cellulaire) qui tirerait parti des propriétés géométriques de la grille dans sa totalité (pour construire, pourquoi pas, des bandes infinies pour des machines de Turing).
Dans le cas qui nous concerne, le plan hyperbolique fournit une géométrie bien plus riche que celle du plan euclidien. En particulier, les graphes de Cayley planaires localement finis (qui jouent le rôle de la grille sus-nommée dans le plan hyperbolique) sont infiniment plus nombreux et ont des propriétés géométriques plus variées dans le plan hyperbolique que dans le plan euclidien.
Dans cet exposé, on s'intéresse au problème suivant sur ces graphes de Cayley : comment construire de tels graphes qui soient planaires localement finis. On montre comment cette question est reliée à des problèmes de géométrie comme le problème de la discrétude des groupes d'isométrie du plan hyperbolique, et de combinatoire comme le problème du mot généralisé. Et on décrit un algorithme permettant de construire effectivement ces graphes (pour une certaine notion de "effectivement").

Transparents

Vendredi 21 mai 2010 à 9h30 : Matthieu Josuat-Vergès http://www.liafa.jussieu.fr/web9/equiprech/fichepers_fr.php?id=260 (voire http://www.lri.fr/~josuat/index.php)

Titre : Nombres d'Euler et nombres Eulériens pour les permutations signées

Résumé : De nombreux résultats classiques en combinatoire concernent les permutations alternantes (interprétations des nombres tangents et sécants, liens avec les nombres eulériens). Le but de cet exposé est de présenter des propriétés d'objets appelés "serpents" (en quelque sorte, des permutations signées alternantes) et de montrer comment ils généralisent certains des résultats classiques sur les permutations alternantes.

~~~~~

Vendredi 21 mai 2010 à 10h45 : Florent Le Gac

Titre : Comptage d'ASMs en fonction de leur nombre de -1 (et de leur taille)

Résumé : Les matrices à signe alternant (ASMs) sont des objets largement étudiés en physique statistique. Ils se trouvent en bijection avec les configurations de boucles compactes, relatées à l'ex-conjecture de Razumov-Stroganov. Nous présentons une formule de comptage des ASMs en fonction de leur taille et de leur nombre d'entrées négatives. Cette formulation nous permet de trouver l'asymptotique pour les ASMs ayant un nombre fixé d'entrées négatives ainsi que des formules exactes lorsque le nombre d'entrées négatives reste petit.

Vendredi 23 avril 2010 : Axel Bacher

Titre : Chemins auto-évitants fractals

Résumé : Un chemin sur le réseau carré est auto-évitant s'il ne visite pas deux fois le même sommet. Nous nous intéressons aux chemins qui traversent un rectangle (i.e. relient deux sommets opposés en restant dans le rectangle). Nous définirons une famille de tels chemins, et présenterons une équation que vérifie sa série génératrice (cette équation fait intervenir un produit de Hadamard). Nous donnerons aussi quelques résultats asymptotiques.

Vendredi 16 avril 2010 : Thomas Feierl http://homepage.univie.ac.at/thomas.feierl/

Titre : Asymptotics for lattice walks in a Weyl chamber of type B

Résumé : We consider a certain class of lattice walks confined to the region ⚠ $0<x_1<...<x_k$. The main results in this talks are asymptotic formulas for the number of walks with arbitrary starting and end point as well for the number of walks with arbitrary starting point and a free end point. The asymptotic formulas are proved by a saddlepoint approach. The main problem which has to be overcome here is the determination of asymptotics for certain determinants.
As applications, we determine asymptotics for two vicious walkers models (the lock step model and the random turns model) and derive asymptotics for ⚠ $k$- non-crossing tangled diagrams.
(based on arXiv:math.CO/0906.4642)

Vendredi 9 avril 2010 : Valentin Féray

Titre : Caractères irréductibles du groupe symétrique et grands diagrammes de Young (2/2)

Résumé : L'étude de représentations d'un groupe fini se réduit à la construction des représentations irréductibles et au calcul des caractères correspondants. Dans le cas du groupe symétrique, ceci peut être fait en utilisant des objets combinatoires, en particulier les tableaux et les diagrammes de Young.
Après avoir fait les rappels nécessaires, on établira une nouvelle formule pour les caractères irréductibles, faisant intervenir des hypercartes.
Nous verrons ensuite comment cette formule permet de comprendre le comportement asymptotique des caractères irréductibles sur une permutation fixée et une application de ce résultat à l'étude de formes limites pour des grands diagrammes de Young.

Vendredi 2 avril 2010 : Olivier Guibert

Titre : Tableaux alternatifs et nombres de Schröder

Résumé : Les tableaux alternatifs, récemment introduits par Xavier Viennot, peuvent être définis comme des diagrammes de Ferrer dans lesquels chaque case peut être soit laissée vide soit remplie par une cellule bleue ou rouge mais de sorte qu’aucune cellule ne doit être remplie à gauche d’une cellule bleue ni en dessous d’une cellule rouge. Le nombre de tableaux alternatifs est (n+1)! où n est le nombre de lignes et de colonnes du diagramme de Ferrer. Plusieurs restrictions connues de ces tableaux alternatifs sont comptés par des nombres classiques en combinatoire (Catalan, Baxter). Dans cet exposé, nous montrons bijectivement qu’une autre restriction est comptée par les nombres de Schröder.

Vendredi 26 mars 2010 : Michel Marcus

Titre : Factorisations de permutations

Résumé : On s'intéresse au nombre d'écritures d'une permutation de type cyclique donné comme un produit de deux grands cycles. Dans le cas d'une permutation impaire, il existe une formule remarquablement simple attribuée à G. Boccara. Nous utilisons ce résultat pour mieux appréhender les factorisations des permutations paires. Le sujet a déjà été traité par Valentin Féray lors du groupe de travail du 18 décembre dernier. Nous apportons des compléments à son travail.

Vendredi 19 mars 2010 : Valentin Féray

Titre : Caractères irréductibles du groupe symétrique et grands diagrammes de Young (1/2)

Vendredi 12 mars 2010 : Mathilde Bouvel http://www.liafa.jussieu.fr/~mbouvel/

Titre : Motifs et classes de permutations : le point de vue des arbres de décomposition

Résumé : Dans cet exposé, on étudie les classes de permutations, qui sont des ensembles de permutations fermés par le bas pour la relation d’ordre de motif. Je présenterai d’une part des résultats de nature algorithmique sur la recherche de motif dans les permutations, et d’autre part des résultats plus combinatoires sur la structure des classes de permutations. Un point commun à ces résultats est qu’ils ont été obtenus en utilisant les arbres de décomposition des permutations. Je présenterai ces objets, et illustrerai par des exemples comment ils peuvent être utilisés en combinatoire comme en algorithmique.

Transparents

Vendredi 5 mars 2010 : Jean Fromentin http://users.info.unicaen.fr/~jfroment/

Titre : Algorithmique des tresses : la forme normale tournante

Résumé : Une tresse, est un objet géométrique composé de brins qui se croisent. En mettant bout à bout deux tresses ayant le même nombre de brins, on obtient une nouvelle tresse. Munis de cette opération, l'ensemble des tresses à n brins forme un groupe. Une présentation, par générateurs et relations de ce groupe, est donnée en 1942 par Artin. Une tresse peut alors être vue comme une classe d'équivalence de mots de tresse. Une forme normale est alors un moyen (souvent algorithmique) de sélection pour une tresse d'une mot de tresse distingué la représentant.
L'exposé sera divisé en deux parties. La première sera consacrée à une introduction aux groupes de tresses : point de vue intuitif, structure de groupe, présentation d'Artin, problème du mot, etc. Dans la seconde, je présenterai l'objet central de mes travaux, qui est une nouvelle forme normale des tresses, dite forme normale tournante, et j'expliquerai (un peu) en quoi cette nouvelle forme est intéressante, notamment en liaison avec l'ordre de Dehornoy des tresses. Ensuite, je me concentrerai sur les aspects plus informatiques de cette approche, à savoir la construction d'automates explicites reconnaissant les formes tournantes. Seules les idées seront présentées dans cet exposé, les détails techniques seront volontairement omis.

Vendredi 19 février 2010 : Yann Jullian http://iml.univ-mrs.fr/~jullian/

Titre : Représentation géométrique d'un système symbolique par substitution d'arbre

Résumé : Une substitution primitive engendre un système dynamique minimal et uniquement ergodique. Le but est de représenter (pour un exemple particulier) le système par un échange de domaines sur un arbre. Je commencerai par définir simplement les propriétés de la représentation géométriques que l'on souhaite obtenir. J'introduirai ensuite les substitutions d'arbre (combinatoire) comme des extensions des substitutions classiques sur les mots. J'associerai à la substitution sigma: a->ab, b->c, c->a, une substitution d'arbre et je me servirai de cette dernière pour construire un arbre qui supporte la dynamique engendrée par sigma.

Vendredi 12 février 2010 : Alexandre Zvonkine

Titre : Autour de l'icosaèdre de genre 4

Résumé : Il est connu depuis l'antiquité que l'icosaèdre est la seule carte planaire ayant 12 sommets de degré 5, 30 arêtes et 20 faces triangulaires.
Il est connu depuis 1884 que le graphe de l'icosaèdre peut être plongé sur la surface de genre 4 de manière très régulière : 12 sommets de degré 5, 30 arêtes et 12 faces de degré 5.
Il se trouve qu'il existe aussi beaucoup d'autres cartes de genre 4 ayant le même assortiment de degrés des sommets et des faces. On peut les construire comme revêtements ramifiés de certaines cartes planaires.

Vendredi 5 février 2010 à 9h30 : Manuel Lladser http://amath.colorado.edu/faculty/lladser/

Titre : Poissonization as a mathematical statistics tool

Résumé : Poissonization is a well-known technique in applied probability and analytic combinatorics, typically used to remove correlations in allocation problems. In this talk, we show a novel application of Poissonization as a mathematical statistics tool. Specifically, we address the following problems related to an urn composed with balls of different colors, from which one can sample with replacement: (a) assess the color bias when only two colors compose the urn but only a small sample is allowed from it; and (b) extrapolate the urn’s composition without knowing anything about the number of colors and their relative proportions. The first problem is in collaboration with my student G. C. Peterson and M. Yarus' lab. The second problem is in collaboration with R. Gouet and R. Knight’s lab. The research has been partially supported by the NIH grants 3R01GM048080-13S1 and 5R01R01HG04872.

~~~~~

Vendredi 5 février 2010 à 10h45 : Antoine Genitrini http://www.prism.uvsq.fr/~ange/

Titre : Expressions booléennes aléatoires et fonctions booléennes

Résumé : Écrivez une expression booléenne de manière aléatoire, construite avec des ensembles fixés de connecteurs et de littéraux. Quelle est la fonction booléenne “typique” qu’elle représente ? Quelle est la probabilité que l’expression calcule la fonction Vrai ? Un littéral ? Ou une autre fonction donnée ? D’autres questions de nature un peu différente peuvent se poser : quelle est la complexité de la fonction booléenne représentée par cette expression aléatoire (i.e. la taille de la plus petite expression la représentant) ? Quelle est la complexité moyenne d’une fonction booléenne définie sur k variables ?
Ces questions mettent en avant le problème suivant : comment définir une distribution de probabilité sur les fonctions booléennes à partir d’expressions aléatoires ? Les premiers articles se posant ce genre de questions ont mis en avant deux modèles d’expressions booléennes aléatoires, basées sur les connecteurs binaires Et/Ou, et qui engendrent une distribution (non uniforme) sur les fonctions booléennes. Ces articles n’ont répondu que très partiellement aux premières questions que j’ai évoquées. On adapte aisément ces distributions au cas d’expressions construites à l’aide de l’unique connecteur Implication, un des connecteurs de base d’un point de vue logique. Ce modèle de base suscite de l’intérêt car certaines expressions représentant des tautologies (expression calculant toujours Vrai) en logique classique ne sont pas des tautologies en logique intuitionniste.
Dans un premier temps, j’exposerai les résultats concernant les tautologies construites sur l’Implication, puis j’aborderai la distribution de probabilité sur l’ensemble des fonctions booléennes construites avec ce connecteur logique. Dans un troisième temps, j’enrichirai le modèle de expressions en utilisant plusieurs connecteurs logiques aléatoires. Enfin, je conclurai l’exposé en abordant différentes perspectives relatives à ces problèmes et sur lesquelles je travaille actuellement.

Vendredi 22 janvier 2010 à 9h30 : Andrea Sportiello http://pcteserver.mi.infn.it/~sportiel/index.html

Titre : Deterministic protocols in the Abelian Sandpile Model

Résumé : In the BTW Abelian Sandpile Model (ASM) various relevant configurations show scaling properties and definite thermodynamic limit. E.g.~this is the case for the recurrent identity, and the relaxation of a large mass at a site. However, this limit exists in a `weak' sense, as, at various sizes, subextensive structures arise in an unpredictable way, and the exact characterization of the extensive part is still at early stages. Conversely, for a variant on a directed lattice, these configurations show a thermodynamic limit in a `strong' sense, as also subextensive structures occur deterministically.
We consider a number of other `experimental settings', in the original BTW model, in which the limit exists in this strong sense. The intuition on which settings could have such a property comes from the comprehension of the `master' setting for what concerns the subextensive structures: a dynamics of toppling/antitoppling events starting from the maximally-filled configuration, which produces a network of `strings' satisfying remarkable conservation laws.

~~~~~

Vendredi 22 janvier 2010 à 10h45 : Yoann Gelineau http://math.univ-lyon1.fr/~gelineau/

Titre : Les nombres d'Entringer, leurs interprétations et leurs q-analogues

Résumé : Dans cet exposé, nous étudierons quelques formules liant les nombres d'Entringer, qui énumèrent les permutations alternantes en fonction de leur dernier terme. Ces formules, dont on peut facilement décrire des q-analogues, sont à la base de la table de Kempner qui génère les nombres tangents et sécants. Nous verrons également les autres interprétations combinatoires de ces nombres, en termes d'arbres binaires croissants ordonnés.

Vendredi 15 janvier 2010 : Philippe Duchon

Titre : Couplages rares dans des FPL symétriques et pavages d'hexagones

Résumé : En partant de conjectures déjà connues sur la distribution des "couplages" de configurations de boucles compactes (FPL) présentant des symétries particulières, on est naturellement amené à s'intéresser aux FPL invariants par symétrie centrale et ayant un couplage dans un ensemble très spécifique. Je démontrerai un cas particulier de formule qui n'est qu'une conséquence de ces conjectures, et, au passage, signalerai de nouvelles coïncidences énumératives troublantes faisant intervenir des comptages de pavages d'hexagones et des classes de symétrie de FPL.
(Travail largement en cours, et en collaboration avec Jean-Christophe Aval)

Vendredi 18 décembre 2009 : Valentin Féray

Titre : Énumération de certaines factorisations d'un long cycle

Résumé : Je m'intéresse ici au nombre de factorisations du cycle (1 2 ... N) dans S_N comme un produit d'un cycle et d'une permutation à m cycles. Une récente formule de Stanley montre un lien entre ces nombres et les nombres de Stirling de deuxième espèce.
Je donnerai dans cet exposé une preuve combinatoire de ce résultat (celle de Stanley est algébrique), en mettant en bijection des cartes partitionnées et une certaine classe d'arbres. Comme notre bijection conserve la valence des sommets, notre résultat est plus fin que celui de Stanley.
Travail en commun avec Ekaterina Vassilieva (LiX)

Vendredi 11 décembre 2009 à 9h30 : Angela Hicks http://www.math.ucsd.edu/~ashicks/

Titre : Quelques bijections dans la théorie des fonctions de parking

~~~~~

Vendredi 11 décembre 2009 à 10h45 : Adriano Garsia http://math.ucsd.edu/~garsia/

Titre : Polynômes de Macdonald et fonctions de parking (2/2)

Vendredi 4 décembre 2009 : Adriano Garsia http://math.ucsd.edu/~garsia/

Titre : Polynômes de Macdonald et fonctions de parking (1/2)

Vendredi 27 novembre 2009 : Philippe Narbel

Titre : Suites de complexité linéaire

Résumé : La notion la plus classique de complexité des suites infinies sur un alphabet fini est la fonction de comptage de ses facteurs distincts. Reliée à l'entropie, cette notion est néanmoins un moyen plus précis d'estimer l'ordre/désordre de telles suites. Nous présenterons ici un panorama des résultats et de certaines techniques de preuve associés aux complexités bornées linéairement et néanmoins strictement croissantes -- les suites de ces complexités sont celles qui peuvent être considérées comme les "plus simples" sans être périodiques. Ceci permettra de situer quelques nouveaux résultats liés aux codages des feuilletages de surface par des langages de mots infinis qui se révèlent, eux aussi, être de complexité linéaire.

Vendredi 20 novembre 2009 : Vincent Pasquier http://ipht.cea.fr/Phocea/Membres/Annuaire/index.php?uid=vpasquier

Titre : Les polynômes multivariables et l'effet Hall

Résumé : Je montrerai que les fonctions d'ondes de liquides bidimensionnels incompressibles décrivant les électrons de l'effet Hall sont des polynômes à autant de variables qu'il y a d'électrons et dans les cas les plus intéressants vérifient des propriétés d'annulation quand plusieurs variables sont spécialisées en des valeurs coïncidentes. Les physiciens se demandent comment une partie d'un liquide quantique est intriquée avec le reste de celui-ci. Cela revient à trouver des bonnes façons de couper un polynôme en deux et à mesurer l'intrication des deux parties. J'essayerai d'expliquer en quoi ces problèmes sont de nature combinatoire.

Vendredi 13 novembre 2009 : Matthieu Josuat-Vergès http://www.liafa.jussieu.fr/web9/equiprech/fichepers_fr.php?id=260 (voire http://www.lri.fr/~josuat/index.php)

Titre : Fonction de partition du PASEP et histoires de Laguerre

Résumé : Le processus d'exclusion asymétrique (PASEP) est un modèle de physique statistique décrivant l'évolution de particules. Les probabilités non-normalisées, et la fonction de partition, sont reliés à la combinatoire des permutations. En étudiant les bijections entre histoires de Laguerre et permutations, nous donnons une nouvelle interprétation combinatoire de la fonction de partition.

Vendredi 23 octobre 2009 : Cédric Chauve http://www.math.sfu.ca/people/profile.php?ID=chauve_c

Titre : Arbres de gènes et arbres d’espèces : problèmes de parcimonie

Résumé : Une famille de gènes est un ensemble de gènes, présents dans les génomes de plusieurs organismes, qui ont pour origine un unique ancêtre commun. Un arbre de gènes est un arbre phylogénétique décrivant les relations des gènes d'une même famille. Un tel arbre est le résultat d’événements d'évolution qui incluent la spéciation, la duplication de gène et la perte de gène.
Dans le cadre des approches dites « phylogénomiques » qui visent à inférer l’histoire évolutive de plusieurs espèces à partir de leurs génomes complets (au contraire des approches phylogénétiques qui se concentrent sur une famille de gènes), l’approche consistant à rechercher, étant donné un ensemble d'arbres de gènes, un arbre d'espèces qui induit un nombre minimum de duplications est de plus en plus employée.
Il s’agit d’un problème d’optimisation combinatoire simple à décrire, mais qui est, sans surprise, NP-complet.
Dans cet exposé, je propose de :

faire un survol de ce problème ;
présenter des instances que l’on peut résoudre en temps polynomial (collaboration avec J-P Doyon et Nadia El-Mabrouk) ;
décrire un algorithme astucieux de calcul d’une 3-approximation pour le calcul de la première spéciation parcimonieuse, basée sur la minimisation de fonctions sous-modulaires (collaboration avec A. Ouangraoua).

Vendredi 16 octobre 2009 à 9h30 : Mercedes Rosas http://www.personal.us.es/mrosas/

Titre : Stabilité des coefficients de Kronecker

Résumé : In the late 1930's Murnaghan discovered the existence of a stabilization phenomenon for the Kronecker product of Schur functions. For n sufficiently large, the values of the Kronecker coefficients appearing in the product of two Schur functions of degree n do not depend on the first part of the indexing partitions, but only on the values of their remaining parts. We compute the exact value of n for which all the coefficients of a Kronecker product of Schur functions stabilize. We also compute two new bounds for the stabilization of a sequence of coefficients and show that they improve existing bounds of M. Brion and E. Vallejo.

~~~~~

Vendredi 16 octobre 2009 à 10h45 : Emmanuel Briand http://personal.us.es/ebriand/

Titre : Coefficients de Kronecker, théorie de l'information quantique et théorie de la complexité

Résumé : Les coefficients de Kronecker sont les multiplicités dans la décomposition en irréductibles d'un produit tensoriel de représentations irréductibles du groupe symétrique. Ce sont aussi les constantes de structure pour le "produit de Kronecker" de fonctions symétriques, dans la base des fonctions de Schur.
Les coefficients de Kronecker sont beaucoup plus mystérieux que les coefficients de Littlewood-Richardson (leurs analogues pour le groupe général linéaire). Je présenterai de nouvelles approches de leur étude, motivées par des travaux récents en théorie de l'information quantique et la théorie de la complexité algébrique.

Vendredi 9 octobre 2009 (Petite École de Combinatoire à 10h45) : Valentin Féray

Titre : Tutoriel SAGE

Résumé : SAGE est un logiciel libre, proposant une alternative à Maple, Mathematica, Magma, MATLAB et MuPAD... Il est facile d'utilisation (en particulier bien documenté), comprend énormément de bibliothèques et repose sur une communauté assez active.
Après avoir donné quelques informations sur le logiciel, je ferai une démonstration de quelques fonctionnalités.
L'exposé sera donc orienté d'un point de vue pratique et non technique : comment trouver et utiliser les fonctions qui me paraissent utiles pour faire de la recherche en combinatoire ?
Voici les liens vers les feuilles de calcul de démonstration :
Expressions symboliques
Équations de séries génératrices
Permutations
Posets et fonction de Greene
Fonctions symétriques

Vendredi 2 octobre 2009 : Xavier Viennot

Titre : L'Ansatz cellulaire et les configurations B.A.BA

Résumé : Nous proposons un cadre unifié géométrico-algébrique pour l'étude, et en particulier l'énumération, de diverses structures sur réseaux apparaissant en physique statistique comme les matrices à signes alternants, les FPL, les pavages de diagrammes hexagonaux par losanges, partitions planes, chemins ne se coupant pas, graphes relatifs au modèle d'Ising, ou encore les tableaux interprétant les probabilités stationnaires du modèle PASEP.
L'Ansatz cellulaire se conjugue en deux temps. Le premier est la "géométrisation" des relations de commutations définissant une algèbre quadratique générale par des règles de réécriture planaires sur les cellules d'un réseau carré. Pour une certaine algèbre quadratique à 4 générateurs et 8 paramètres, cette planarisation conduit aux configurations B.A.BA contenant en substance toutes les configurations ci-dessus. De nouvelles familles de bijections apparaissent.
Le deuxième temps de l'Ansatz cellulaire consiste en la représentation des générateurs d'une algèbre quadratique par des opérateurs agissant sur des objets combinatoires, ce qui permet de construire "automatiquement" des bijections en un certain sens "canonique". La classique correspondance RSK (Robinson-Schensted-Knuth) en est un exemple. La bijection entre permutations et tableaux alternatifs interprétant le PASEP en est un autre. L'extension aux configurations générales B.A.BA est ouverte.

Vendredi 25 septembre 2009 : Valentin Féray

Titre : Interprétation algébrique d'une identité combinatoire due à Greene

Résumé : Le point de départ de ce travail est une identité rationnelle liée aux ensembles ordonnés obtenue par C. Greene. Un des membres de cette identité peut s'interpréter comme une intégrale sur un cone. Les propriétés géométriques de ce cone, provenant de la combinatoire de l'ensemble ordonné sous-jacent, permettent d'expliquer naturellement l'identité de Greene (dont la preuve consistait en une récurrence assez calculatoire).

Transparents

Vendredi 18 septembre 2009 : Cédric Chauve http://www.math.sfu.ca/people/profile.php?ID=chauve_c

Titre : Énumération et décomposition de graphes

Résumé : Dans cet exposé, je décris deux problèmes d'énumération de graphes. Ces problèmes sont indépendants mais sont attaqués via une approche similaire, à savoir l'analyse d'arbres de décomposition. Le premier problème est motivé par l'analyse en moyenne d'un algorithme de calcul de distance génomique et consiste à calculer des paramètres sur des (graphes de) permutations en utilisant leur arbre de décomposition modulaire. Il s'agit d'un travail en commun avec Mathilde Bouvel, Dominique Rossin et Marni Mishna qui a été présenté à CPM cet été. Le second concerne l'énumération de graphes « distance-héréditaires » en utilisant leur arbre de décomposition en split. Il s'agit d'un travail en cours avec Éric Fusy.

Combinatoire et interactions

Equipe du département Combinatoire et Algorithmique

du LaBRI