2008-2009

Vendredi 3 juillet : Philippe Narbel

Résumé:

Vendredi 26 juin : Nicolas Bonichon- Liens étroits entre triangulations de TD-Delaunay et demi-Thêta-graphes

Résumé:Un s-spanner est un sous-graphe H d’un graphe G, tel que pour tout couple de sommets, la distance dans H soit au plus s fois la distance dans G. Les Thêta-graphes sont une famille classique de spanner du graphe Euclidien (graphe complet sur n sommets du plan dont la longueur d'une arête est égale à la distance Euclidienne entre ses extrémités). Nous montrons qu’un demi-Thêta-graphe avec thêta = pi/3 est un 2-spanner du graphe Euclidien.

Pour obtenir ce résultat nous étudions les liens étroits qu’il y a entre les 1/2-théta-graphes, les surfaces orthogonales coplanaires et les triangulations de TD-Delaunay.

Nous présenterons également plusieurs résultats secondaires et généralisations possibles liés à ces correspondances.

(Travail réalisé en collaboration avec Cyril Gavoille, Nicolas Hanusse et David Ilcinkas).

Vendredi 19 juin : Mireille Bousquet-Mélou- Comptage de chemins confinés dans le quart de plan (travail en commun avec Marni Mishna, Vancouver)

Résumé: Soit S un sous-ensemble de {-1,0,1}2 ne contenant pas (0,0). On s'intéresse au comptage des chemins du plan à pas dans S, issus de l'origine et confinés au premier quadrant. En particulier, on voudrait connaître la nature de la série génératrice associée : est-elle rationnelle, algébrique, différentiellement finie ? A priori, on a 28 problèmes de ce type à étudier. Cependant, certains sont triviaux ; d'autres sont équivalents à un problème de chemin dans un demi-plan et peuvent donc être résolus par la "méthode du noyau", qui conduit systématiquement à des séries génératrices algébriques.

On se concentre sur les cas restants, et montrons qu'il y a 79 problèmes inhéremment différents à étudier. Suivant les préceptes du petit livre jaune de Fayolle et al., on associe à chacun d'eux un groupe de transformations birationnelles, et montrons que celui-ci est fini (d'ordre au plus 8) dans 23 cas, infini sinon.

On présente une façon unifiée de résoudre 22 des 23 problèmes associés à un groupe fini. Dans chaque cas, la série trouvée est D-finie. Bostan et al. ont récemment prouvé que la série associée au 23 ème problème, connu comme "les chemins de Gessel", est algébrique (donc D-finie). On conjecture que les séries associés à des groupes infinis ne sont pas D-finies. Notre approche retrouve des résultats connus, en raffine certains, et apporte aussi des résultats neufs. Par exemple, nous montrons que les chemins à pas N, E, W, S, SW et NE ont une série génératrice algébrique.

Let S be a subset of {-1,0,1}2 not containing (0,0). We address the enumeration of plane lattice walks with steps in S, that start from (0,0) and always remain in the first quadrant. A priori, there are 28 problems of this type, but some are trivial. Some others are equivalent to a model of walks confined to a half-plane: such models can be solved systematically using the kernel method, and are known to have algebraic generating functions. We focus on the remaining cases, and show that there are 79 inherently different problems to study. To each of them, we associate a group G of birational transformations. We show that this group is finite (of order at most 8) in 23 cases. We give evidence that it is infinite in the 56 other cases. We present a unified way of solving 22 of the 23 models associated with a finite group. For all of them, the generating function is found to be D-finite. The 23rd model, known as Gessel's walks, has recently been proved by Bostan et al. to have an algebraic (and hence D-finite) solution. Our approach allows us to recover and refine some known results, and also obtain new results. For instance, we prove that walks with N, E, W, S, SW and NE steps have an algebraic generating function.

Vendredi 5 juin: Nantel Bergeron (York U.) - Algèbres de Hopf combinatoires et tours d’algèbres

Résumé: Il y a quelques années nous avons montré comment construire une algèbre de Hopf combinatoire à partir des représentations d’une tour d’algèbres {A_n}. Plus récemment, Hivert et Nzeutzhap, et indépendamment Lam et Shimozono, ont montré comment construire des graphes gradués duaux (Dual Graded Graphs) à partir d’une d’algèbre de Hopf combinatoire. En combinant ces deux résultats nous montrons que l’on doit avoir dim(A_n)=rⁿ n! pour r=dim(A₁).

Je ferai un rappel des notions importantes et des exemples clefs.

Ceci est un travail conjoint avec T. Lam et H. Li

Vendredi 29 mai: Robert Cori - Involutions sans point fixe indécomposables et mots de Dyck

Résumé: On s'intéresse à ces involutions sans point fixe (spf, aussi appelées couplages indécomposables) car elles sont en bijection avec les cartes pointées. Le paramètre nombre de sommets de la carte se traduit par nombre de maxima partiels pour l'involution. Se pose ainsi la question de déterminer le rapport entre les nombres a_{m,k} et c_{m,k} comptant respectivement les involutions spf sur 2m éléments ayant k maxima partiels et celles parmi elles qui sont indécomposables.

Grâce à une bijection popularisée par X. Viennot et (certains de) ses élèves sous le nom d'Histoires d' Hermite on se ramène à une question sur les mots de Dyck. Une factorisation classique liée à ces mots permet d' obtenir alors

       (4k+m) c_{m,k} >  m a_{m,k}

mais cette inégalité est loin d'être satisfaisante

L'orateur espère que l'exposé motivera certains des auditeurs à améliorer ce résultat, ce qui a été le cas lors de sa dernière intervention qui concernait les permutations indécomposables et qui a suscité une brillante note de Mike Robson.

Vendredi 15 mai: Valentin Féray - Caractères irréductibles du groupe symétrique et énumération de cartes

Résumé: On s'intéresse dans cet exposé aux valeurs des caractères irréductibles du groupe symétrique. On regardera cette quantité comme une fonction de la partition indexant la représentation, la permutation sur laquelle on calcule le caractère étant fixée. Si l'on écrit le caractère en fonction de certains paramètres naturels de la partition, on trouve une expression polynomiale dont les coefficients comptent des cartes dont les sommets sont étiquetés et qui vérifient certaines conditions.

Dans le cas des termes de plus haut degré (cartes planaires), une preuve bijective permet de trouver des formules simples pour ces nombres de cartes. La méthode ne fonctionne pas pour les termes de degré inférieur, mais une récente construction combinatoire de G. Chapuy permet d'obtenir une formule de récurrence sur le genre des cartes.

Vendredi 24 avril 2009: Vlady Ravelomanana - Optimisation, algorithmique distribuée, graphes aléatoires: approches analytiques

Résumé: Dans cet exposé, nous donnons un aperçu des apports de la combinatoire énumérative, de l'analyse complexe et des méthodes probabilistes sur plusieurs problèmes fondamentaux en informatique.

Notamment, nous allons traiter
a/- les composantes géantes des graphes aléatoires,
b/- les problèmes d'élection et d'initialisation ("naming") dans les réseaux et
c/- le problème du stable maximum.

Pour chacune des trois parties, nous discuterons des perspectives possibles. En particulier, on pourra envisager des problèmes tels que la génération aléatoire de graphes connexes (partie a/) ou encore d'autres problèmes d'optimisation difficile (NPO, parties a/ et c/).

Vendredi 10 avril 2009: Damien Regnault - Minorité stochastique sur les graphes

Résumé: Nous considérons un graphe où les cellules sont caractérisées par un état qui est soit noir, soit blanc. À chaque pas de temps, une cellule, choisie aléatoirement, se met à jour et passe dans l'état minoritaire dans son voisinage. L'évolution globale de ce processus ne semble pas dépendre de la topologie du graphe: dans un premier temps des régions, pavées par des motifs dépendant de la topologie du graphe, se forment rapidement. Puis dans un deuxième temps, les frontières entre ces régions évoluent jusqu'à devenir relativement stables. Nous étudions ce processus sous différentes topologies: arbres, anneaux, grilles, cliques. Ceci nous permet de montrer que même si ce processus se comporte à priori globalement de la même manière sur n'importe quel graphe, modifier la topologie influence la façon dont les régions sont pavées (rayures, damiers), la structure et les mouvements des frontières entre les régions, l'ensemble limite, le temps de relaxation (le temps nécessaire pour que le processus atteigne une configuration de l'ensemble limite). Ainsi, Minorité entraîne des comportements riches et variés qui se révèlent difficile à analyser. Comprendre cette règle simple est néanmoins nécessaire avant de considérer des règles plus compliquées.

Vendredi 3 avril 2009: Guoniu Han - Hook length formulas : Combinatorics and Number Theory

Résumé: (Combinatorics) We introduce the hook length expansion technique and explain how to discover old and new hook length formulas for partitions and plane trees. In particular, we derive an expansion formula for the powers of the Euler Product in terms of partition hook lengths, discovered by Nekrasov and Okounkov. We also obtain an extension by adding two more parameters, which appears to be a discrete interpolation between the Macdonald identities and the generating function for t-cores.

(Number Theory) Our formula unifies the classical Jacobi and Gauss identities when t=2. We proved some arithmetical properties for t=3 and made a general conjecture. In the case t=5, the conjecture implies the long standing Lehmer conjecture which says that the Ramanujan tau-function never takes the zero value.

Vendredi 27 mars 2009: Igor Pak (U. Minnesota) - Geometry and complexity of partition bijections

Résumé: The study of partition identities has a long history going back to Euler, with applications ranging from Analysis to Number Theory, from Enumerative Combinatorics to Probability. Partition bijections is a combinatorial approach which often gives the shortest and the most elegant proofs of these identities. These bijections are then often used to generalize the identities, find "hidden symmetries", etc. In the talk I will present a new approach to partition bijections based on the geometry of random partitions and complexity ideas. Special attention will be paid to the Rogers-Ramanujan identities

Vendredi 13 mars 2009 - Jean-François Marckert - L'arbre continu d'Aldous est la limite des arbres binaires enracinés non ordonnés de taille n.

Résumé : Il s'agit ici d'étudier l'asymptotique des arbres binaires non ordonnés à n feuilles, sous la loi uniforme, lorsque n tend vers l'infini. Comme d'habitude, on cherche à prouver que soigneusement normalisée (en racine de n, ici), notre structure discrète possède une limite non triviale (et aléatoire) : un arbre continu aléatoire.

Évidemment, se pose la question de la signification des mots "limite" et "converger". Ici, il s'agit d'une convergence en distribution pour la topologie de Gromov-Hausdorff, topologie très à la mode en probabilité actuellement (car très utilisée en lien avec la limite d'échelle des cartes combinatoires). Je rappelerai/expliquerai la définition et l'intérêt de cette topologie.

Le but de cet exposé est d'expliquer pourquoi, à un facteur constant près, la limite des arbres binaires non ordonnés est la même que celle des arbres binaires ordonnés (planaires) à n feuilles, qui elle est connue et "simple à prouver", à savoir l'arbre continu d'Aldous (dont une représentation est une "excursion Brownienne recollée").

En fait, en dehors de détails techniques sordides, l'idée de la preuve qui consiste à effectivement comparer les deux familles d'arbre est simple. J'essaierai donc dans cet exposé d'expliquer cette idée, en restant autant que faire se peut, à un niveau élémentaire.

Travail en commun avec Grégory Miermont

Vendredi 6 mars 2009 - De nouvelles classes de chemins auto-évitants - Axel Bacher .

Résumé : Un chemin auto-évitant sur le réseau carré est un chemin ne visitant pas deux fois le même sommet. Compter les chemins auto-évitants de longueur arbitraire est très difficile, et à l'heure actuelle seules des conjectures asymptotiques sont connues. Notre but sera de définir des classes naturelles de chemins auto-évitants à la fois grandes et qu'il soit possible de compter. Jusqu'à présent, la classe connue la plus grande est celle des chemins dits prudents trilatères (comptés par Bousquet-Mélou), avec une constante de croissance de 2,48. Nous présenterons deux nouvelles classes de chemins, basées sur l'idée de chemins dirigés, que nous avons pu dénombrer. Nous montrerons que leur constante de croissance est d'environ 2,54.

vendredi 13 février - Ordres d'intervalles, involutions sans emboîtement de voisins, et permutations à motifs exclus - Mireille Bousquet-Mélou.

Résumé : L'étude d'une certaine classe de permutations à motifs exclus a attiré l'attention sur deux autres familles d'objets : les ordres d'intervalles, et certaines involutions introduites par Stoimenow en lien avec les invariants de Vassiliev des noeuds, et dénombrées ensuite par Zagier.

Nous établissons des bijections entre ces 3 familles, puis avec une quatrième famille, dotée d'une structure récursive simple. En utilisant ladite structure, nous énumérons tous ces objets, retrouvant ainsi le résultat de Zagier (d'une manière qu'on espère plus simple). La série obtenue est assez curieuse.

Travail réalisé avec Mark Dukes, Anders Claesson et Sergey Kitaev.

vendredi 30 janvier - Algèbre de Loday-Ronco et tableaux alternatifs de Catalan (suite) - Jean-Christophe Aval et Xavier Viennot .

Résumé : Tout d'abord, nous rappellerons les trois exemples basiques d'algèbres de Hopf combinatoires: l'algèbre des descentes, celle de Loday-Ronco et celle de Malvenuto-Reutenauer, définies respectivement sur les mots à deux lettres, les arbres binaires et les permutations. Nous donnerons une façon simple et élégante de décrire le produit de l'algèbre de Loday-Ronco en termes de tableaux alternatifs de Catalan, objets combinatoires déjà introduits dans des groupes de travail précédents. Enfin, nous ferons le lien entre cette approche et les jeux de taquin sur les arbres qui faisaient l'objet du groupe de travail du 19 Décembre 2008.

vendredi 23 janvier - Algèbre de Loday-Ronco et tableaux alternatifs de Catalan - Jean-Christophe Aval et Xavier Viennot .

approche et les jeux de taquin sur les arbres qui faisaient l'objet du groupe de travail du 19 Décembre 2008.

vendredi 16 janvier (9h30) - Ordre d'Ehresmann-Bruhat sur le groupe symétrique - Vincent Pasquier.

Résumé : Le groupe symétrique est un ensemble pour lequel la géométrie ou la théorie des groupes de Coxeter impose un ordre partiel, dont la première définition est due à Ehresmann. Pour comprendre les propriétés de cet ordre, on peut plonger le groupe dans un treillis distributif dont les sommets correspondent aux matrices à signe alternant. Un deuxième outil est d'utiliser des relations entre ensembles de tableaux qui étendent une propriété d'Eulérianité de l'ordre. Nous résumerons ces deux constructions, qui sont en fait liées, et que j'ai obtenues en collaboration avec M.P. Schützenberger.

vendredi 16 janvier (10h40)- TITRE- Vincent Pasquier.

Résumé : Je montrerai que les fonctions d'ondes de la conjecture de Razumov Stroganov sont des polynômes de Macdonald pour des valeurs particulières des constantes de définition. Cela conduit a une généralisation de la conjecture dont il manque une interprétation combinatoire.

vendredi 19 décembre - Des jeux de taquin pour les arbres- Xavier Viennot.

Résumé : Le "jeu de taquin" de M.P.Schützenberger, algorithme non-déterministe transformant une permutation en un tableau de Young, est un grand classique de la combinatoire algébrique. D'une manière analogue, avec des "glissements" de pièces, nous introduisons des "jeux de taquin" pour trois familles d'arbres binaires. Tour d'abord, nous rappelons comment construire l'arbre binaire croissant associé à une permutation par un "jeu de taquin", en liaison avec la notion de forme ("up-down sequence") d'une permutation,

La nouveauté de cet exposé (travail en commun avec Philippe Nadeau) est d'introduire un "jeu de taquin" pour les "arbres binaires alternatifs". Ces arbres, en bijection avec les permutations, ont déjà été introduits dans ce groupe de travail par P. Nadeau, en liaison avec un travail de A. Burstein sur les "tableaux de permutations". Ce jeu de taquin est un algorithme non-déterministe, avec "glissements" et "éclatements" donnant une bijection entre les "tableaux alternatifs" et les arbres binaires alternatifs. Une autre bijection entre ces arbres et les permutations, basée sur un parcours des arbres binaires en ordre symétrique "twisté", donne le lien avec la notion de "forme de Genocchi" des permutations. En combinant ces deux bijections, nous retrouvons alors "La bijection canonique" entre tableaux et permutations, décrites sous diverses formes équivalentes par S. Corteel, P. Nadeau, A. Burstein et l'orateur.

vendredi 12 décembre- Permutations à motifs exclus et arbres de génération- Mireille Bousquet-Mélou.

Résumé : L'énumération de permutations à motifs exclus combine souvent deux étapes : --- une étape bijective, qui transforme les permutations en d'autres objets, que l'on espère plus simples à dénombrer, --- une description récursive desdits objets, traduite en une relation de récurrence ou en une équation fonctionnelle sur la série génératrice.

On étudiera des exemples où la traduction de la structure récursive en équations oblige à introduire d'autres paramètres d'énumération (dits "catalytiques"). Par exemple, on peut construire récursivement les permutations évitant 123 en insérant à chaque instant la plus grande valeur, mais il faut garder en mémoire la position de la première montée pour exploiter cette construction récursive et en tirer une équation fonctionnelle. Plus généralement, les classes de permutations étudiées ici sont telles que l'arbre de génération associé (qui décrit l'insertion de la plus grande valeur) est isomorphe à un arbre décrit par un nombre fini d'étiquettes. Ceci inclut des arbres à une étiquette (permutations évitant 123), deux étiquettes (permutations évitant 1234, permutations et involutions de Baxter...), mais aussi des arbres à un nombre arbitraire d'étiquettes, comme ceux pour les involutions évitant k(k-1)... 321 récemment décrits par Jaggard and Marincel. On montrera comment une même approche permet de dénombrer ces différentes classes.

vendredi 5 décembre- Autour de formules d'énumération de matrices à signes alternants verticalement symétriques- Philippe Duchon.

Résumé : Parmi les nombreuses formules d'énumération de matrices à signes alternants présentant des symétries, dûes à Kuperberg, on en trouve qu'il est difficile de laisser passer sans vouloir les redémontrer de manière combinatoire ou bijective. Un exemple est fourni par la formule liant les nombres d'ASM verticalement symétrique, de taille 2N+1, et les "USASM" de taille 2N (ou "ASM quasi-verticalement symétriques" de taille 2N+2):

    A_V(2N+2) = 2^N A_V(2N+1),

qui se raffine encore si l'on tient compte du nombre de coefficients -1 "non fixés" (comptés par la variable x), et d'un paramètre supplémentaire sur les USASM (compté par la variable y):

    A_V(2N+2;x,y) = (1+y)^N A_V(2N+1;x)

Manifestement, une telle identité mérite une preuve combinatoire. Je décrirai mes tentatives en cours pour trouver une telle preuve, qui pour l'instant n'ont abouti que pour les termes, en x, de plus bas degré (facile) et de plus haut degré (moins facile).

vendredi 28 novembre- Jeux avec (de) permutations- Julian West.

Résumé : Nous considérons un jeu dans lequel les deux joueurs ajoutent, en alternance, des nombres à la fin d'une séquence initialement vide, le jeu terminant soit quand la séquence contient une sous-séquence croissante de longueur a, soit quand elle contient une sous-séquence décroissante de longueur d. Nous montrons comment transformer ce jeu pour simplifier son analyse, et montrons comment bien jouer quand min(a,d)<7.

DATE - Structure des tableaux alternatifs- Philippe Nadeau .

Résumé : Dans ce travail nous étudions les tableaux alternatifs, objets introduits par X. Viennot lors de l'étude des probabilités stationnaires du PASEP.

Le cœur de ce travail est une description récursive simple de la structure de ces tableaux. Cela nous permet d'abord de donner facilement des formules d'énumération à plusieurs paramètres de ces tableaux. D'autre part, cette approche donne très naturellement une bijection avec certaines familles d'arbres, et de là avec les permutations. Nous montrons que cette bijection est équivalente à d'autres bijections dues à Viennot, Corteel ou Burstein.

vendredi 14 novembre - Tableaux alternatifs et permutations avec motif interdit- Xavier Viennot.

Résumé : Nous donnons la preuve d'un joli résultat de Olivier Bernardi: les permutations n'ayant aucune sous-séquence du type (y+1), x, y, (x+1) sont dénombrées par les nombres de Catalan. Cette preuve repose sur les tableaux alternatifs, objet combinatoire introduit lors de trois exposés à ce groupe de travail en Février 2008. Je décrirai la bijection canonique entre permutations et tableaux alternatifs sous la forme d'un algorithme de "fusion-échange", puis introduirai les tableaux alternatifs de Catalan, en bijection avec les permutations mentionnées, ainsi que les arbres binaires.

vendredi 7 novembre- Cycles universels pour classes de permutations- Julian West.

Résumé : Le mot cyclique 1,6,7,8,4,3,2,5 est universel pour la classe de permutations Av_4(132,312), au sens où les réductions de ses 8 facteurs (1678),(6784),...(5167) forment les 8 permutations qui appartiennent à la classe. Nous cherchons d'autres exemples de ce phénomène.

 (travail en commun avec Michael Albert, Otago)

vendredi 24 octobre- The insertion encoding for permutations, with some applications- Michael Albert.

Résumé : The insertion encoding of permutations, which is closely related to the method of generating trees, provides an alternative method of attack on certain enumeration problems in permutation classes. In this (hopefully self-contained!) talk, I will introduce the coding itself, the notion of a "permutation class", and then show how it can be used to provide a uniform attack on the enumeration of a wide variety of such classes. In particular, the class of 4231-avoiding permutations, whose exact enumeration remains unknown can be shown to have a "larger than expected" growth rate, by approximating it from below with certain classes which are represented by regular languages in the insertion encoding.

vendredi 10 octobre- Une preuve bijective d'une identité de Bauer sur les chemins à boucles effaçantes (suite) - Xavier Viennot .

Résumé : Les chemins à boucles effaçantes ("loop-erased random walks") sont des chemins auto-évitants générés à partir de chemins aléatoires en effaçant les cycles ou boucles qui peuvent se produire. Ils apparaissent dans plusieurs études de physiciens et de probabilistes. Une identité, établie par Michel Bauer (physicien au CEA de Saclay), exprime leur distribution probabiliste en fonction de l'inverse d'un déterminant. Je donnerai une preuve bijective en termes d'empilements de pièces.

Après quelques nouvelles du front (sur les empilements), la première partie de l'exposé sera d'ordre pédagogique, en rappelant quelques lemmes fondamentaux, la bijection entre chemins et empilements, ainsi que la bijection entre "réarrangements" et empilements de cycles, ce qui nous conduira à rappeler la preuve en terme d'empilements du "théorème Maître" de MacMahon. L'identité de Bauer a en effet un fort "parfum" de ce dernier théorème célèbre.

La deuxième partie de l'exposé introduit la nouvelle notion de "substitution" d'un empilement dans un autre, notion nécessaire pour bien comprendre le passage du théorème Maître de MacMahon à l'identité de Bauer.

vendredi 26 septembre- Une preuve bijective d'une identité de Bauer sur les chemins à boucles effaçantes- Xavier Viennot .

vendredi 19 septembre- La bijection des cartes boisées: extension en genre supérieur et spécialisation - Olivier Bernardi.

Résumé : Dans cet exposé nous rappelons la bijection des cartes boisées (présentée il y a quelque temps à ce même GT) et étudions les propriétés de certaines extensions et spécialisations.

Rappelons qu'une carte de genre ⚠ $g$ est un graphe connexe plongé dans le tore à ⚠ $g$ anses. Une carte est dite unicellulaire si elle a une unique face. Par exemple, les cartes unicellulaires de genre 0 sont les arbres planaires. Une carte couverte est une carte dont une sous-carte couvrante unicellulaire est distinguée. Dans le cas particulier où la sous-carte est un arbre (couvrant), on parle de carte boisée. Ainsi, dans le cas planaire, les cartes recouvertes sont toutes des cartes boisées.

La bijection des cartes boisées transforme une carte planaire boisée (à ⚠ $n$ arêtes) en un couple d'arbres (à ⚠ $n$ et ⚠ $n+1$ arêtes respectivement). Dans un premier temps nous étudions des spécialisations de cette bijection à des familles particulières de cartes (triangulations, cartes bipartites...). Nous recouvrons alors des bijections classiques dues à Schaeffer, Bouttier-DiFrancesco-Guitter et al. Dans un deuxième temps (si celui-ci le permet) nous présentons une extension de la bijection qui transforme une carte couverte de genre ⚠ $g$ en un couple formé d'un arbre (à ⚠ $n$ arêtes) et d'une carte unicellulaire bipartite de genre ⚠ $g$ (à ⚠ $n+1$ arêtes). Nous déduisons de cette bijection une équivalence entre les formules énumératives d'Harer et Zagier sur les carte unicellulaires générales et une formule d'Adrianov sur les cartes unicellulaires bipartites. (Travail en commun avec Guillaume Chapuy)

vendredi 12 septembre- Permutations indécomposables par nombre de cycles, application au tirage de cartes. - Robert Cori.

Résumé : Les permutations indécomposables (appelées aussi connexes) ont été rencontrées par de nombreux auteurs. L. Comtet a démontré (avant 1970) que la probabilité pour qu'une permutation de ⚠ $S_n$ soit décomposable est de l' ordre de ⚠ $2/n$ lorsque ⚠ $n$ tend vers l'infini. En examinant de plus près ce résultat on constate que cette probabilité dépend fortement du nombre de cycles de la permutation (ou du nombre de maxima partiels): plus ce nombre est grand et plus la probabilité que la permutation soit décomposable est grand. Je montrerai (travail en collaboration avec Claire Mathieu) que la probabilité pour qu'une permutation de ⚠ $S_n$ ayant ⚠ $m$ cycles soit décomposable est en ⚠ $O(log(n-m)/(n-m))$.

Des résultats de même type pour les involutions sans point fixe de ⚠ $S_{2m}$ ayant ⚠ $k$ maxima partiels seront aussi présentés, leur nombre est aussi celui des cartes (de genre quelconque) ayant ⚠ $m$ arêtes et ⚠ $k$ sommets.

Combinatoire et interactions

Equipe du département Combinatoire et Algorithmique

du LaBRI