2012-2013
Vendredi 21 juin 2013 : Valentin Féray
Titre : Une formule d'équerre multivariée pour les arbres croissants
Résumé : Plusieurs formules sommatoires d'équerre pour les arbres binaires sont apparues récemment dans la littérature. Dans cet exposé nous présentons un analogue pour des arbres croissants de taille r, faisant intervenir O(r2) paramètres, alors que la plupart des formules dans la littérature ont un nombre fixe de paramètres. Le membre de droite de la formule s'écrit comme un produit de facteurs de degrés 2. La preuve de la formule est bijective et est basée sur une nouvelle opération de recollage de chaînes pour construire un arbre.
~~~~~
Vendredi 21 juin 2013 : Bharat Adsul, Department of Computer Science and Engineering, Indian Institute of Technology Bombay http://www.cse.iitb.ac.in/, India
Titre : An algebraic-combinatorial approach to the Kronecker problem via quantum group representations
Résumé :
In this talk, I will describe our on-going efforts towards an algebraic-combinatorial approach towards the Kronecker problem.
Consider the natural embedding of GLm(C) × GLn(C) into GLmn(C) via the Kronecker product.
With respect to this embedding, a GLmn(C) irreducible representation Vλ(mn) splits into a direct sum of irreducible GLm(C) × GLn(C) representations:
The Kronecker problem is the problem of computing the multiplicity coefficents χμ,νλ.
We consider the quantized version of this problem and propose an approach to this problem via the theory of quantum groups and the crystal bases.
I will talk about our initial results in this direction.
The talk is based on joint work with Milind Sohoni and K. V. Subrahmanyam.
Vendredi 14 juin 2013 : Gábor Hetyei https://math.uncc.edu/people/gabor-hetyei Department of Mathematics and Statistics, The University of North Carolina at Charlotte
Titre : Le vecteur h torique, les nombres de Narayana, et des partitions non-croisées
Résumé :
Le vecteur h torique est un invariant énigmatique des polytopes et des ensembles ordonnés Eulériens, introduit par Stanley.
Dans cet exposé nous explorons deux cas spéciaux où le calcul de cet invariant est relié aux partitions non-croisées et aux nombres de Narayana.
Dans le cas des polytopes cubiques, nous verrons qu'un renforcement de la symétrie exprimée par les équations de Dehn-Somerville se démontre en utilisant l'involution de Simion et Ullman sur le treillis des partitions non-croisées.
Dans le cas des polytopes simples, nous verrons que la réponse à une question de Kalai posée dans les années 80 peut être donnée en utilisant des variantes des nombres de Narayana.
Les résultats sur les polytopes cubiques sont obtenus en collaboration avec Sarah Birdsong.
Vendredi 31 mai 2013 : Julien Courtiel
Titre : Une définition unifiée de l'activité pour le polynôme de Tutte
Résumé :
On retrouve dans la littérature plusieurs caractérisations différentes du polynôme de Tutte d'un graphe.
Tutte l'a notamment défini grâce à une notion d'activité basée sur un étiquetage ordonné des arêtes.
Plus tard, Bernardi a donné une notion non équivalente de l'activité en plongeant le graphe dans une surface.
On verra que d'autres notions d'activité peuvent être ainsi imaginées et qu'elles se regroupent toutes en une seule et même définition.
On en profitera pour comprendre macroscopiquement le lien entre les différentes caractérisations du polynôme de Tutte.
À noter que cet exposé commencera par un état de l'art sur le polynôme de Tutte, cela permettra de remettre à plat ses connaissances sur le sujet.
Vendredi 24 mai 2013 : Vincent Delecroix http://www.math.jussieu.fr/~delecroix Institut de Mathématiques, Paris 7
Titre : Une fraction continue géométrique
Résumé :
Les fractions continues permettent de donner des meilleures approximations rationnelles d'un nombre réel donné.
Il est également possible d'interpréter cet algorithme comme des « changements de bases » dans un tore plat.
Je présenterai un algorithme qui généralise cette construction et permet de faire des fractions continues sur des surfaces plates de genre supérieur (chaque étape de l'algorithme peut être vu comme un changement de triangulation).
On verra également que cet algorithme décrit les trajectoires de particules dans certains billards.
C'est un travail en commun avec Corinna Ulcigrai.
Vendredi 17 mai 2013 : Jérémie Lumbroso https://www.greyc.fr/user/364 de l'équipe AMACC (Algorithmique, Modèles de calcul, Aléa, Cryptographie, Complexité) du GREYC, Université de Caen
Titre : Algorithmes probabilistes pour la fouille quantitative de très grandes masses de données
Résumé :
L'avalanche de données qui nous sont disponibles --- provenant d'Internet, des banques, du séquençage de génomes, des réseaux de capteurs, etc. --- rendent généralement illusoire l'idée qu'on peut les examiner de manière très précise.
La fouille quantitative ne s'attache donc qu'à extraire des statistiques élémentaires de flux, mais en le faisant de manière très efficace et peu couteuse en ressources (temps de calcul et espace) : le nombre d'éléments distincts, les éléments rares, et fréquents, le profils de données, les indices de similarité.
Dans cet exposé, il sera brassé un large panorama d'algorithmes qui se servent de techniques probabilistes pour atteindre de très grandes performances, là où une algorithmique déterministe serait inadéquate.
Vendredi 19 avril 2013 : Carine Pivoteau http://igm.univ-mlv.fr/~pivoteau/ Université Paris Est - Marne-la-Vallée
Titre : Un pont entre les espèces de structures et la combinatoire analytique (2/2)
Résumé :
Le livre Analytic Combinatorics de Flajolet et Sedgewick propose un cadre agréable -- la Méthode Symbolique -- pour définir des classes d'objets combinatoires à partir de grammaires (systèmes combinatoires) semblables à celles de la théorie des langages.
En se plaçant dans ce cadre, il est possible d'effectuer un certain nombre de traitements quasi-automatiques sur ces objets : manipulation de séries génératrices, génération aléatoire, analyse asymptotique, ...
Cependant, lorsqu'il s'agit d'implanter de telles méthodes, il est nécessaire de se poser la question : comment savoir si un système combinatoire donné est « bien formé » ?
Cette question nous a amené à considérer une autre approche permettant de décrire des objets combinatoires : la Théorie des Espèces de Structures.
Bien qu'étudiées à des fins très différentes, ces deux approches présentent de nombreux points communs et permettent, lorsqu'elles sont associées, de fournir une base de travail solide pour l'automatisation d'un certain nombre de traitements combinatoires.
Dans cet exposé, nous présenterons ces deux approches et nous décrirons les passerelles menant de l'une à l'autre, dans le but de caractériser les systèmes qui décrivent effectivement des structures combinatoires.
Cette présentation est basée sur un travail en commun avec B. Salvy et M. Soria.
Vendredi 12 avril 2013 : Mathilde Bouvel
Titre : Wilf-équivalences dérivées d'une bijection entre Av(231) et Av(132)
Résumé :
Dans le cadre de l'étude d'opérateurs de tri de permutations composés de piles et de miroirs, j'ai défini dans mon exposé du 29 mars une bijection (notée P) entre la classe des permutations évitant 231 et celle des permutations évitant 132.
Nous verrons dans cet exposé d'autres résultats que l'on peut obtenir grâce à cette bijection P.
Plus précisément, nous démontrerons que les classes Av(231,π) et Av(132,P(π)) sont Wilf-équivalentes (c'est-à-dire énumérées par la même séquence) pour de nombreux motifs π que nous caractériserons.
Nous verrons aussi que ces classes Av(231,π) sont toutes Wilf-équivalentes entre elles, à k=|π| fixé.
Il s'agit d'un travail en commun avec Michael Albert.
À noter qu'il n'est pas nécessaire d'avoir assisté à l'exposé du 29 mars pour venir à cette séance du GT.
Vendredi 5 avril 2013 : Philippe Nadeau, Institut Camille Jordan de l'université Lyon 1, http://math.univ-lyon1.fr/~nadeau/
Titre : Éléments « totalement commutatifs » et chemins du plan
Résumé :
Un élément d'un groupe de Coxeter W est dit « totalement commutatif » si on peut passer d'une de ses décompositions réduites à toute autre en utilisant uniquement les relations de commutation.
Ces éléments ont été étudiés en détail par Stembridge dans le cas où W est fini.
Nous considérons ici W fini ou affine, et énumérons les éléments totalement commutatifs selon leur longueur de Coxeter.
Notre approche consiste à encoder ces éléments par des chemins du plan que nous décomposons récursivement pour obtenir les fonctions génératrices voulues.
Pour le type A fini, cela redonne un théorème de Barcucci et al. ; pour A affine, cela simplifie et précise des résultats de Hanusa et Jones.
Pour tous les autres groupes finis et affines, nos résultats sont nouveaux.
Travail en collaboration avec Riccardo Biagioli et Frédéric Jouhet (Lyon).
Vendredi 29 mars 2013 : Mathilde Bouvel
Titre : Tri de permutations par plusieurs piles et miroirs, et Wilf-équivalences associées
Résumé :
On étudie les opérateurs de tri de permutations obtenus en composant l'opérateur S de tri par une pile de Knuth et l'opérateur R de miroir, un certain nombre de fois.
Pour tout opérateur A de cette forme, on donne une bijection entre l'ensemble des permutations triées par S.A et l'ensemble de celles triées par S.R.A, démontrant ainsi que ces ensembles ont la même séquence d'énumération, mais aussi que de nombreuses statistiques classiques sur les permutations ont la même distribution sur ces deux ensembles.
La description de cette famille de bijections repose deux ingrédients principaux : une caractérisation des préimages d'une permutation par S donnée par Mireille Bousquet-Mélou, et une bijection apparemment nouvelle entre l'ensemble des permutations qui évitent le motif 231 et l'ensemble de celles qui évitent 132, qui préserve de nombreuses statistiques.
On présente aussi d'autres propriétés de cette bijection, en particulier pour trouver des familles de classes de permutations équivalentes au sens de Wilf.
Il s'agit d'un travail en commun avec Michael Albert.
Vendredi 8 mars 2013 : Carine Pivoteau http://igm.univ-mlv.fr/~pivoteau/ Université Paris Est - Marne-la-Vallée
Titre : Un pont entre les espèce de structures et la combinatoire analytique (1/2)
Résumé :
Le livre Analytic Combinatorics de Flajolet et Sedgewick propose un cadre agréable -- la Méthode Symbolique -- pour définir des classes d'objets combinatoires à partir de grammaires (systèmes combinatoires) semblables à celles de la théorie des langages.
En se plaçant dans ce cadre, il est possible d'effectuer un certain nombre de traitements quasi-automatiques sur ces objets : manipulation de séries génératrices, génération aléatoire, analyse asymptotique, ...
Cependant, lorsqu'il s'agit d'implanter de telles méthodes, il est nécessaire de se poser la question : comment savoir si un système combinatoire donné est « bien formé » ?
Cette question nous a amené à considérer une autre approche permettant de décrire des objets combinatoires : la Théorie des Espèces de Structures.
Bien qu'étudiées à des fins très différentes, ces deux approches présentent de nombreux points communs et permettent, lorsqu'elles sont associées, de fournir une base de travail solide pour l'automatisation d'un certain nombre de traitements combinatoires.
Dans cet exposé, nous présenterons ces deux approches et nous décrirons les passerelles menant de l'une à l'autre, dans le but de caractériser les systèmes qui décrivent effectivement des structures combinatoires.
Cette présentation est basée sur un travail en commun avec B. Salvy et M. Soria.
Vendredi 1er mars 2013 : Bétréma
Titre : Évacuation et promotion
Résumé :
Dans les années soixante (non, il n'y a pas si longtemps:-) Schützenberger a créé de toutes pièces la théorie combinatoire du « jeu de taquin ».
Au départ il s'agissait de mieux comprendre une construction de Schensted (devenue ensuite « algorithme RSK »), et ses relations avec les représentations du groupe symétrique.
Vers 1970 Schützenberger a fait agir les algorithmes du jeu de taquin sur n'importe quel ensemble partiellement ordonné fini P, et a ainsi défini deux transformations fondamentales sur les extensions linéaires de P, qu'il a progressivement appelées « évacuation » et « promotion ».
Schützenberger a énoncé et prouvé plusieurs théorèmes fascinants vérifiés par ces transformations (par exemple l'évacuation est involutive).
En 2009 Stanley a recensé ces résultats et en a publié une présentation simplifiée, qui intègre en particulier des travaux de Haiman et de Reutenauer publiés autour de 1990.
L'évacuation et la promotion apparaissent ainsi comme de simples permutations circulaires, modifiées a minima pour être compatibles avec un ordre partiel donné.
J'exposerai ce point de vue en utilisant un logiciel où les « glissements » (opérations caractéristiques du jeu de taquin) sont exécutés par une application personnelle Flash
(la technologie infâme d'Adobe).
En complément j'ai publié des illustrations de la section 5 de l'article de Stanley,
obtenues avec le logiciel Sage, sous forme de deux "posts" sur un blog personnel :
l'évacuation est involutive,
et formule reliant
promotion et évacuation.
Vendredi 22 février 2013 : Omar Tout
Titre : Coefficients de structure de l’algèbre de Hecke de la paire (S2n, Bn)
Résumé :
L’algèbre du groupe symétrique C[Sn] est l’algèbre des combinaisons linéaires des permutations de taille n.
Une base du centre de l’algèbre C[Sn] est donnée par les Kλ, où Kλ est la somme des permutations de type cyclique λ.
Les coefficients de structure αλμν décrivent le produit dans le centre de C[Sn] :
Kλ Kμ = ∑ναλμν Kν .
En 1958, Farahat et Higman ont démontré la polynomialité en n des coefficients αλμν , lorsque λ, μ et ν sont des partitions fixées, complétées avec des
parts égales à 1 pour obtenir des partitions de n.
En 1999, Ivanov et Kerov ont donné une nouvelle démonstration en introduisant les permutations partielles.
Dans cet exposé, on commencera par présenter le cas du centre de l’algèbre du groupe symétrique.
Après, on considèrera l’algèbre de Hecke de la paire (S2n, Bn) qui est un analogue du centre de l’algèbre du groupe symétrique.
On donnera à la fin un résultat de polynomialité des coefficients de structure de cette algèbre en suivant la méthode de Ivanov et Kerov.
Vendredi 8 février 2013 : Luca Ferrari http://www.dsi.unifi.it/~ferrari/ Dipartimento di Sistemi e Informatica, Università degli Studi di Firenze (Italie)
Titre : Lattice paths from an order-theoretic perspective
Résumé : We will present some results and open problems regarding lattice paths which arise from certain natural partial order structures they can be endowed with. Some of the topics we will discuss are: rank-unimodality, enumeration of chains, computation of the Euler characteristic of distributive lattices of paths, order-isomorphisms with other poset of relevant combinatorial interest, the pattern containment order for lattice paths.
Vendredi 1er février 2013 : Marni Mishna (Université Simon Fraser, Vancouver, Canada) http://www.math.sfu.ca/people/staff/faculty/marni_mishna
Titre : A combinatorial approach to lattice path asymptotics
Résumé : Several di fferent approaches to determine the exponential growth for lattice paths restricted to the quarter plane have recently appeared. This talk will survey this recent progress and o ffer a relatively simple strategy that is surprisingly general, gives tight bounds and sheds some insight on the fundamental diff erences between walks restricted to a region defi ned by one boundary, and those restricted by two boundaries.
Vendredi 25 janvier 2013 : Mireille Bousquet-Mélou
Titre : Propriétés asymptotiques de quelques classes de graphes à mineurs exclus
Résumé :
Soit A une classe de graphes étiquetés, fermée pour l'extraction de mineurs.
Soit G_n un graphe aléatoire de taille n pris uniformément dans A.
Quand n est grand, quelle est la probabilité que G_n soit connexe ?
Plus généralement, combien de composantes connexes a-t-il ?
Grâce aux travaux de McDiarmid et de ses collaborateurs, ces questions sont désormais résolues lorsque tous les mineurs interdits sont connexes.
C'est par exemple le cas des graphes planaires.
Nous étudions, via une énumération exacte, une collection de classes A définies par l'interdiction de mineurs dont certains ne sont pas 2-connexes, et montrons que leur propriétés asymptotiques peuvent être très différentes de celles obtenues dans le cas de mineurs 2-connexes.
Ces propriétés dépendent de la nature des singularités dominantes de la série génératrice C(z) qui compte les graphes connexes de A.
Nous classons nos exemples selon cette nature, ce qui constitue un premier pas (modeste) vers une classification complète des classes de graphes closes par extraction de mineurs.
(travail en commun avec Kerstin Weller, Oxford)
Vendredi 11 janvier 2013 : Mireille Bousquet-Mélou
Titre : Chemins auto-évitants dans un demi-plan
Résumé :
Il y a deux ans, Duminil-Copin et Smirnov ont prouvé une (relativement) vieille conjecture de Nienhuis (1982), selon laquelle le nombre de chemins auto-évitants de longueur n sur le réseau hexagonal croît en gros comme mu^n, avec mu=sqrt(2+sqrt(2)).
J'avais présenté leur preuve à ce groupe de travail à l'automne 2010.
Elle a réveillé chez beaucoup de gens l'espoir de prouver d'autres conjectures du domaine.
Dans cet exposé, je présenterai ainsi la preuve d'une conjecture plus jeune (1995) de Batchelor et Yung, qui traite des chemins auto-évitants confinés dans un demi-plan, en interaction avec la frontière de ce demi-plan.
(travail joint avec N. Beaton, J. de Gier, H. Duminil-Copin et A. Guttmann)
Vendredi 14 décembre 2012 (Petite École de Combinatoire) : Valentin Féray
Titre : Approche duale des représentations du groupe symétrique (9)
Résumé : cf. (1)
~~~~~
Vendredi 14 décembre 2012 (Groupe de Travail) :
Julien Courtiel
(travail commun avec Mireille Bousquet-Mélou)
Titre : Arbres et cartes munis de forêt couvrante
Résumé :
Dans le monde fascinant de l'énumération de cartes, on dénombre deux grandes familles de bijection : la première transforme les cartes en mobiles, la seconde en arbres bourgeonnants.
D'abord introduites par Schaeffer pour les quadrangulations et cartes tétravalentes, ces bijections ont été généralisées grâce à Bouttier, Di Francesco et Guitter.
Cet exposé sera l'occasion de mettre en avant les arbres de la seconde famille, à savoir les arbres bourgeonnants.
Nous montrerons l'utilité de ces objets pour l'énumération de cartes munies de forêt couvrante, notre actuel sujet de recherche.
La première partie se voudra avant tout didactique, elle présentera les arbres bourgeonnants tels qu'ils ont été introduits par Bouttier, Di Francesco et Guitter.
Par suite, nous enrichirons ces objets avec des forêts couvrantes afin de retomber sur notre problématique de départ.
Une étude combinatoire permettra alors d'exhiber une propriété fort intéressante de positivité, qui n'est pas sans rappeler la positivité des coefficients du polynôme de Tutte.
À noter que cet exposé aura de beaux dessins.
Vendredi 7 décembre 2012 (Petite École de Combinatoire) : Valentin Féray
Titre : Approche duale des représentations du groupe symétrique (8)
Résumé : cf. (1)
~~~~~
Vendredi 7 décembre 2012 (Groupe de Travail) : Jean-Christophe Aval
Titre : Tableaux boisés
Résumé : Cet exposé se veut un survol des résultats combinatoires obtenus ces deux dernières années grâce aux tableaux boisés. Ces objets, qui peuvent être vus comme une nouvelle incarnation des tableaux de permutations (Postnikov) ou des tableaux alternatifs (Viennot), jouent un rôle crucial dans l'interprétation combinatoire d'un modèle de physique nommé PASEP. L'atout des tableaux boisés est une procédure récursive beaucoup plus simple que les constructions antérieures. Je donnerai dans cet exposé, des applications combinatoires de cette procédure.
Vendredi 30 novembre 2012 (Petite École de Combinatoire) : Valentin Féray
Titre : Approche duale des représentations du groupe symétrique (7)
Résumé : cf. (1)
Vendredi 23 novembre 2012 (Petite École de Combinatoire) : Valentin Féray
Titre : Approche duale des représentations du groupe symétrique (6)
Résumé : cf. (1)
Vendredi 16 novembre 2012 (Petite École de Combinatoire) : Valentin Féray
Titre : Approche duale des représentations du groupe symétrique (5)
Résumé : cf. (1)
~~~~~
Vendredi 16 novembre 2012 (Groupe de Travail) : Marni Mishna (Université Simon Fraser, Vancouver, Canada) http://www.math.sfu.ca/people/staff/faculty/marni_mishna
Titre : Towards randomly generated mammals...
Résumé :
Genome arrangements, a major mechanism of evolution, shuffle genetic material along chromosomes.
Thus, a now standard approach models groups of close genomes as signed permutations.
The correct data structure to study permutations in this context is the common interval tree.
We refine these trees according to a parameter, and the resulting sub-families turn out to be simple varieties of trees.
Thus, they are particularly amenable to analytic enumerative techniques, and Boltzmann generation.
This refinement also has implications in algorithm analysis for various ancestral genome reconstruction algorithms.
Finally, we compare the trees that we generate with those that arise with the direct comparison of a selection of mammalian genomes.
Work in collaboration with Mathilde Bouvel, Cédric Chauve, Rosemary McCloskey, Cyril Nicaud and Carine Pivoteau.
Vendredi 9 novembre 2012 (Petite École de Combinatoire) : Valentin Féray
Titre : Approche duale des représentations du groupe symétrique (4)
Résumé : cf. (1)
~~~~~
Vendredi 9 novembre 2012 (Groupe de Travail) : Philippe Narbel
Titre : Bouquets de cercles et langages de courbes
Résumé : Nous décrirons ici l'ensemble des fonctions de complexité des langages shifts qui proviennent du codage d'ensembles de courbes, appelés laminations en théorie des surfaces. Ces langages sont obtenus en déformant continuement les courbes sur des chemins de graphes étiquetés, orientés et plongés (proches de la notion de carte). Cette étude se basera sur l'ensemble de ces graphes qui n'ont qu'un seul sommet, i.e. les bouquets de cercles, et qui s'avèrent être des formes normales dans ce contexte. Nous montrerons également comment construire des langages pour chacune des complexités possibles, dont certaines des laminations finies correspondantes ont des représentations graphiques spiralées, vaguement minoennes irlando-crétoises.
Vendredi 26 octobre 2012 (Petite École de Combinatoire) : Valentin Féray
Titre : Approche duale des représentations du groupe symétrique (3)
Résumé : cf. (1)
Vendredi 19 octobre 2012 (Petite École de Combinatoire) : Valentin Féray
Titre : Approche duale des représentations du groupe symétrique (2)
Résumé : cf. (1)
~~~~~
Vendredi 19 octobre 2012 (Groupe de Travail) : Thomas Selig
Titre : Une extension stochastique du modèle du tas de sable sur un graphe
Résumé : Dans le modèle du tas de sable, lorsqu'un sommet devient instable, c'est-à-dire que le nombre de grains en ce sommet dépasse son degré, celui-ci s'éboule en envoyant un grain vers chacun de ses voisins. Dans notre modèle, un sommet instable envoie un grain vers chaque voisin avec probabilité p>0 (indépendamment pour chaque voisin). On donnera une caractérisation des états récurrents de ce nouveau modèle, en termes d'orientations du graphe. De plus, on introduira un polynôme comptant ces états récurrents selon leur nombre (total) de grains de sable, et on verra que celui-ci satisfait une relation de récurrence qui ressemble à celle du polynôme de Tutte.
Vendredi 12 octobre 2012 (Petite École de Combinatoire) : Valentin Féray
Titre : Approche duale des représentations du groupe symétrique (1)
Résumé :
La théorie des représentations du groupe symétrique est un domaine de recherche relativement ancien (initié par Schur et Frobenius autour de 1900).
Une question centrale est de calculer les "caractères irréductibles".
Bien que la question soit de nature algébrique, les réponses ont une saveur combinatoire, faisant intervenir notamment des tableaux de Young et des fonctions symétriques.
Plus récemment, S. Kerov et G. Olshanski ont proposé une nouvelle approche de cette théorie, que l'on pourrait qualifier de "duale".
Il s'agit de considérer tous les groupes symétriques en même temps et de regarder les caractères comme une fonction sur les diagrammes de Young.
Nous allons développer deux aspects de cette théorie :
- premièrement, cette approche fait apparaître une combinatoire nouvelle, à base de cartes, que l'on va présenter ;
- deuxièmement, elle permet de décrire asymptotiquement la forme limite d'un diagramme de Young sous la mesure de Plancherel, faisant ainsi un pont avec les probabilités.
~~~~~
Vendredi 12 octobre 2012 (Groupe de Travail) : Mathieu Bogaerts (Faculté des Sciences Appliquées, Université Libre de Bruxelles, Belgique) http://homepages.ulb.ac.be/~mbogaert/
Titre : Décompositions de graphes en 1-facteurs
Résumé :
Un 1-facteur d'un graphe G est un sous-graphe couvrant dont tous les sommets ont degré 1, aussi nommé perfect matching (ou couplage parfait).
Une 1-factorisation de G est une partition de ses arêtes en 1-facteurs disjoints.
Un groupe d'automorphisme d'une 1-factorisation de G est un groupe de permutations des sommets de G qui envoie 1-facteurs sur 1-facteurs.
Dans cet exposé, nous discuterons le problème suivant : étant donné un graphe G, existe-t-il une 1-factorisation de G qui soit préservée par un groupe dont l'action est strictement transitive sur les sommets du graphe ?
Ce problème a été traité pour des graphes complets et des groupes cycliques/abéliens/dihédriques, et, plus récemment, étendu aux graphes complets multipartis.
Nous exposerons nos résultats dans ce domaine, obtenus en collaboration avec G. Mazzuoccolo (Modène, Italie).
Vendredi 5 octobre 2012 : Matteo Silimbani http://www.dm.unibo.it/~silimban/
Titre : Some permutation classes enumerated by the central binomial coefficients
Résumé :
A permutation class is a downset in the subpermutation ordering.
Permutation classes arise naturally in a variety of fields, such as the study of Shubert varieties, Chebyshev polynomials, and ordering algoritms.
A permutation class C may be defined the set of minimal elements not belonging to it, its basis B.
In his Ph.D. thesis, Olivier Guibert introduced eleven different permutation classes, whose basis contains four permutations of length four, each one enumerated by the central binomial coefficients.
It is well known that the binomial coefficients enumerate also the set of Dyck prefixes of a given length.
In the present talk, we define a bijection between the permutation class of basis B={3241,3214,4213,4231} and the set of Dyck prefixes.
This bijection allows us to relate particular features of a Dyck prefix with the occurrences of some statistics in the corresponding permutation (ascents, left-to-right maxima, length of the greatest decreasing sequence, etc).
Moreover, we try to find similar bijections for the other ten classes enumerated by the central binomial coefficients, in order to find generating function for the distribution of some permutation statistics over these classes.
Vendredi 28 septembre 2012 : Yvan Le Borgne
Titre : Sur le calcul du rang dans les graphes et en particulier les cliques (2/2)
Résumé : Cf. (1/2)
Vendredi 21 septembre 2012 : Robert Cori
Titre : Sur le calcul du rang dans les graphes et en particulier les cliques (1/2)
Résumé : En 2007, Baker et Norine ont proposé un théorème de Riemann-Roch pour les graphes. Dans ce théorème, le rang est un paramètre entier se définissant, à l'aide d'une optimisation parmi des compositions, sur tous les étiquetages des sommets par des entiers relatifs. En 2010 et 2011, Robert Cori avait présenté ici une preuve de ce résultat contenant également un algorithme de calcul du rang. Nous la rappellerons dans le cadre du modèle du tas de sable et présenterons comme nouveauté une spécialisation de l'algorithme au cas des cliques. L'analyse des exécutions intéressantes de cette spécialisation gloutonne donne l'occasion de patauger dans la si rare combinatoire des nombres de Catalan, avec pour changer des bistatistiques possédant des distributions avec des symétries.
Vendredi 7 septembre 2012 : Michael Albert http://www.cs.otago.ac.nz/staff/michael.html (Computer Science Department, University of Otago, New Zealand)
Titre : New perspectives on the enumeration of permutation classes
Résumé : A permutation class is a collection of permutations closed downwards in a natural ordering. Early research in this area tended to concentrate on the enumeration of specific classes. I will describe a sequence of ideas which lead to the most general known results about the enumerative properties (specifically, the rationality or algebraicity of generating functions) for a collection of such classes. One particular consequence is that all "small" classes have rational generating functions. I will also illustrate how these ideas can be a guide for the actual enumeration of some specific classes.