Résumé: We present the construction of a bigraded family
of groups (A-groups) associated to graphs, and simplicial
complexes. This theory resembles classical homotopy theory of
spaces and satisfies many of the same properties. However, it
depends heavily on the combinatorial structure of the objects; for
instance, it is not invariant under subdivisions of simplicial
complexes.
We shall also discuss some of the applications of
A-theory to computer sciences, and sociology!
Résumé: I will give a survey of the interaction between partitions and number theory. How does one prove identities or congruences between combinatorial and number theoretic functions? What are the natural partition theoretic objects that arise? What can number theory tell us about these objects? I will address these questions by giving several examples of current research.
Résumé: We study generating functions for the number of involutions of length n avoiding (or containing exactly once) 132, and avoiding (or containing exactly once) an arbitrary permutation tau on k letters. In several interesting cases the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind. In particular, we establish that involutions avoiding both 132 and 12...k have the same enumerative formula according to the length as involutions avoiding both 132 and any double-wedge pattern possibly followed by fixed points of total length k.
Résumé: Travail en collaboration avec Gilbert Labelle et Cédric Lamathe.
Dans ce travail, nous généralisons les 2-arbres en remplaçant les triangles par des quadrilatères, des pentagones ou des polygones à k cotés (k-gones), où k>=3 est fixe. Cette généralisation, aux 2-arbres k-gonaux, est naturelle et est étroitement liée dans le cas planaire aux arbres cellulaires. Notre objectif est le dénombrement, étiqueté et non etiqueté, des 2-arbres k-gonaux selon le nombre n de k-gones. Nous donnons des formules explicites dans le cas étiqueté, et, dans le cas non étiqueté, des formules de récurrence et des formules asymptotiques.
Résumé: Linear recurrences (and, with them, ordinary generating functions) are ubiquitous in combinatorics, as part of a broad general framework that is well-studied and well-understood; in contrast, bilinear recurrences such as sn+4 = (sn+1sn+3+sn+22)/sn are encountered far less often, and these encounters tend to be viewed in isolation from one another.
The bilinear recurrence relation quoted above is the Somos-4 recurrence, part of a general family of "n/2"-degree sequences. Although these have received a fair bit of attention in the past few years, until recently algebra remained one step ahead of combinatorics, leaving us temporarily in the unusual position of being able to enumerate combinatorial objects for which we lack a combinatorial description.
In this talk, we produce a family of graphs whose perfect matchings are enumerated by the Somos-4 sequence, and a second family whose perfect matchings are enumerated by Somos-5. The recurrences that govern these sequences are also special cases of the Gale-Robinson family of recurrences: S(n)=[S(n-i1)S(n-i2)+S(n-j1)S(n-j2)]/S(n-k), where k=i1+i2=j1+j2. The results for Somos-4 and Somos-5 thus give us some hope that a similar family of graphs can be constructed for any Gale-Robinson recurrence.
This is joint work with Jim Propp and Mireille Bousquet-Mélou. Many of these results have also been obtained independently by Propp's team of undergraduate researchers at Harvard.
Résumé: Je présenterai un travail réalisé en collaboration avec N. Bonichon et N. Hanusse sur le codage des graphes planaires. Si p(n) représente le nombre de graphes planaires à n sommets (graphes sans boucle ni multi-arête, non étiquetés et non dessinés), je montrerai que pour n assez grand: b*n+O(logn) < log_2(p(n)) < a*n+O(logn) où a et b sont des constantes telles que b=4.71 et a=5.01. Mis à part le résultat numérique qui découle de notre approche plutôt "algorithmique", je présenterai les principaux ingrédients de cette recette qui sont : les triangulations du plan, les arbres de Schnyder, les mots de Dyck, les feuilles et les bourgeons. Et vive le printemps !
Résumé: Le groupe symétrique
généralisé G_{n,m} peut être défini
comme l'ensemble des matrices de pseudo-permutations pour lesquelles
les entrées non nulles sont des éléments du
groupe des racines m-ièmes de l'unité.
Nous
parlerons de différentes actions de G_{n,m} sur l'espace
Q[x_1,...,x_n] des polynomes en n variables, de
polynomes invariants et covariants sous ces actions. Le
résultat principal est l'analogue du théorème de
Chevalley "La dimension de l'espace covariant est égale
à l'ordre de G_{n,m}." pour une action
quasi-symétrisante.
We study the generating function for the number of permutations on n letters containing exactly r>=0 occurrences of 132. It is shown that finding this function for a given r amounts to a routine check of all permutations in S_{2r}.
Résumé: Le polynôme de Tutte d'un graphe est une généralisation du polynôme chromatique à deux variables duales. Pour un ordre total de l'ensemble des arêtes, il en existe un modèle d'état en termes d'arbres couvrants (les activités des arbres couvrants de Tutte mesurent en bref une distance aux arbres couvrants minimaux et maximaux pour l'ordre lexicographique) et un modèle d'état en termes d'orientations (les activités des orientations de Las Vergnas comptent le nombre de plus petits éléments de cycles ou cocycles orientés).
Il s'agit de prouver bijectivement l'égalité de ces formulations, bijection active signifiant bijection préservant les activités.
Deux algorithmes duaux (l'un en termes de cycles, l'autre en termes de cocycles) définissent une bijection active entre les arbres couvrants d'activités (1,0) et les orientations acycliques ayant un unique puits adjacent à une unique source fixés.
Via une partition de l'ensemble des orientations en classes d'activités, on en déduit une bijection active entre arbres couvrants et classes d'activités, et pour certains ordres qui existent toujours une bijection active entre arbres couvrants d'activités (i,0) et orientations acycliques ayant un unique puits fixé.
Pour ces dernières orientations, la décomposition en classes d'activités rappelle les composantes de Viennot qui reposaient par contre sur un ordre total des sommets. Le fait de ne s'occuper que des arêtes permet de faire ressortir des propriétés de dualité et de prendre en compte toutes les orientations. Ce point de vue est celui des matroïdes orientés, objets combinatoires et géométriques plus généraux, auxquels se généralisent les constructions précédentes.
En 1985, Rodica Simion et Frank Schmidt ont donné une bijection entre les permutations sans sous-séquence 123 et celles sans sous-séquence 213. C'est-à-dire que S_n(123) <--> S_n(213). Ici on donne une généralisation à S_n(12...t,p_{t+1}...p_m) <--> S_n(t...21,p_{t+1}...p_m). En même temps, on voit que la même bijection est valable pour les "permutations" dans un diagramme de Young arbitraire.
Un modèle de percolation simple des physiciens conduit naturellement à s'intéresser à la serie double aire/périmètre des animaux. Une simplification usuelle de ce modèle consiste à se restreindre aux animaux dirigés de source unique. Si on dispose de multiples démonstrations pour l'énumération selon l'aire de ces objets, le périmètre, lui, reste énigmatique. Toutefois A.R. Conway a conjecturé une expression algébrique pour l'évaluation partielle d'une dérivée (partielle) de cette série double. Je présenterai mes diverses tentatives pour prouver cette conjecture.
Les polygones sur le réseau carré sont des chemins qui se terminent à l'origine. Si toute ligne horizontale ou verticale croise le périmètre deux fois exactement, le polygone est convexe. La longueur du périmètre du polygone est alors toujours égale à celle du rectangle minimal qui contient le polygone (appelé MBR, ou minimum bounding rectangle).
Les polygones sont dits presque convexes si la différence entre leur périmètre et celui du MBR est égale à deux fois "l'indice de concavité", m. Ces polygones sont appelés m-convexes. Cette classe de polygones est le sujet de ma recherche.
Dans cet exposé, je présenterai les sous-classes différentes des polygones convexes, avec lesquelles on peut énumérer les polygones presque convexes auto-évitants. Je montrerai la méthode, celle qu'on utilise pour énumérer toutes ces classes, qui est appelée celle d'inclusion-exclusion et est basée sur l'article de Bousquet-Mélou et Guttmann: "Enumeration of Three-dimensional Convex Polygons"; Annals of Comb., 1997(1).
Si le temps me permet, je présenterai aussi des résultats intéressants supplémentaires.
Two succession rules are defined to be equivalent if they generate the
same number sequence.
The problem of determining classes of equivalent rules is still
open. In this talk we give some hints about equivalent ECO-systems
(i.e. succession rules as originally defined) by means of some
examples involving Dyck and Schroeder numbers.
Résumé: Tous les problèmes d'énumération de chemins confinés dans un demi-plan peuvent être décrits par une équation fonctionnelle linéaire, très simple à établir, qui fait intervenir des dérivées discrètes par rapport à une variable. Ces modèles sont en fait, par essence, uni-dimensionnels, et équivalents à l'énumération des chemins sur une demi-droite. La "méthode du noyau", qui remonte aux années 70, permet de résoudre les équations associées. C. Banderier et Ph. Flajolet viennent d'écrire sur le sujet un bel article exhaustif.
De façon similaire, tous les problèmes d'énumération de chemins confinés dans un quadrant peuvent être décrits par une équation fonctionnelle linéaire qui fait intervenir des dérivées discrètes par rapport à deux variables. Il n'existe pas de technique permettant de résoudre systématiquement ces équations. Je propose un exposé explorant (partiellement) ce problème. Je présenterai notamment une nouvelle solution d'un modèle où, pour des raisons mystérieuses, la série génératrice est algébrique, un critère garantissant l'holonomie de cette même série, et enfin, un cas très simple où la série n'est pas holonome.
Résumé: Le quotient de l'anneau Q[x_1,...,x_n] par l'idéal Sym_n engendré par les fonctions symétriques sans terme constant est de dimension n! (Artin).
Nous nous intéressons ici au quotient de Q[x_1,...,x_n] par l'idéal QSym_n engendré par les fonctions quasi-symétriques sans terme constant. Nous prouvons que sa dimension est C_n=1/(n+1)(2n \choose n) le n-ième nombre de Catalan et décrivons une base explicite de ce quotient naturellement indexée par les chemins de Dyck.
Résumé: On donne une démonstration combinatoire directe de la formule de Harer-Zagier sur les nombres de manières d'obtenir une surface de Riemann de genre g par identification par paires des cotés d'un 2m-gone. Notre méthode reprend l'approche combinatoire imaginée par Harer et Zagier et évite d'utiliser l'intégration sur un ensemble gaussien de matrices aléatoires. En fait, nous montrons qu'il suffit de relier deux théorèmes fondamentaux de la combinatoire énumérative, à savoir le calcul des arborescences remontant à Cayley et le théorème dit BEST sur les cycles eulériens.
S'il reste assez de temps, nous esquisserons une application à la génération aléatoire des cartes de genre g.
Let S_n be the symmetric group, C_r the cyclic group of order r, and let S_n^(r) be the wreath product of S_n and C_r, which is the set of all coloured permutations on the symbols 1,2,...,n with colours 1,2,...,r, which is the analogous of the symmetric group when r=1, and the hyperoctahedral group when r=2.
We prove, for every 2-letter coloured pattern phi in S_2^(r) , that the number of phi-avoiding coloured permutations in S_n^(r) is given by the formula sum_{j=0}^n j!(r-1)^j{\binom n j}^2. Also we prove that the number of Wilf classes of restricted coloured permutations by two patterns with r colours in S_2^(r) is one for r=1, is four for r=2, and is six for r>= 3.
(en collaboration avec Mike Zabrocki)
Les fonctions de stationnement pondérées ("parking functions" pour les informaticiens) apparaissent naturellement dans l'étude des espaces harmoniques. Les arrangement préférentiels pondérés apparaissent de façon parallèle dans l'étude "non-commutative" des espaces harmoniques. Nous définirons ces objets, tout en tentant de motiver les statistiques qui nous intéressent de façon naturelle.
Un p-uplet de chemins de Dyck (resp. Grand Dyck) qui ne se coupent pas est formé de p chemins composés de pas Nord-Est et Sud-Est partant du point (0,0) et arrivant au point (2n, 0). Le i-ème chemin ne doit pas passer sous le (i-1)-ème chemin. Ces chemins ne peuvent pas (resp. peuvent) couper l'axe des abscisses.
Ces objets sont en bijection avec de nombreux autres objets combinatoires : les polyominos parallélogrammes, les permutations de baxter, les réaliseurs, ....
C'est pourquoi nous nous intéressons à leur génération aléatoire. Je présenterai un algorithme de génération aléatoire uniforme de p chemins de Dyck (ou Grand Dyck) qui ne se coupent pas. Cet algorithme est basé sur celui de Arnold et Sleep qui construit un chemin de Dyck pas à pas. Quelques résultats expérimentaux sur les réaliseurs seront aussi présentés.
Classiquement, quand on analyse les algorithmes travaillant sur le texte (les algorithmes de dictionnaire par exemple), on se limite à des modèles où les mots sont produits par des sources "simples" : sources de Bernoulli, où il y a totale indépendance entre les symboles successifs, ou cha,bn(Bnes de Markov, où la dépendance est limitée à une portion bornée de l'histoire précédente. Les méthodes classiques d'analyse en moyenne sont alors bien établies, et beaucoup reposent sur l'outil essentiel que sont les séries génératrices.
Mais, bien s,b{(Br, les sources de la vie "réelle" ne rentrent pas dans ce cadre simplificateur: la mémoire est non bornée, et l'émission de la source à un moment donné peut dépendre de toute l'histoire précédente. Dans ce cas, les séries génératrices ne sont plus adaptées à l'analyse, car elles ne peuvent prendre en compte cette histoire trop complexe.
Je décrirai d'abord un modèle de source, fondé sur les systèmes dynamiques, qui présente un certain nombre d'avantages:
Je prendrai alors quelques exemples d'algorithmes sur les mots (dictionnaire, recherche de motifs), et je montrerai comment ces algorithmes peuvent être analysés dans ce cadre de sources "dynamiques".
La combinaison de diverses techniques, mais surtout l'étude des géométries projectives finies et de leurs automorphismes, permet d'achever une classification des orbites de l'action du groupe de tresses sur les générateurs des groupes de monodromie, quand les groupes de monodromies sont "exceptionnels" (c'est-à-dire, primitifs et différents de S_n et A_n).
Le fait que les arbres de familles simples (au sens de Meir et Moon) correspondent à des processus de branchement conditionnés par une taille fixée, est relativement bien connu; l'extension à des structures combinatoires dont les séries génératrices satisfont des équations algébriques ne pose pas de problèmes. Dans cet exposé, je présenterai un moyen extrêmement simple de tirer parti de cette relation pour obtenir des générateurs aléatoires efficaces d'arbres (et d'autres structures).
Ces générateurs aléatoires sont qualifiés de "laxistes", car, bien que la condition d'uniformité à taille fixée soit conservée ("pour tout n, tous les arbres de taille n ont la même probabilité d'être tirés"), on est typiquement amené à relacher les conditions sur la taille (l'objectif "obtenir un arbre de taille n" est remplacé par "obtenir un arbre de taille comprise entre n et n+f(n)").
Les arbres de Schnyder ont été introduits par Walter Schnyder en 1989. Ces triplets d'arbres, ou realizers, sont à la base de nombreux algorithmes de dessins de graphe. Pour leur part, les paires (g,h) de mots de Dyck (sur l'alphabet {a,b}) ne se coupant pas, sont des mots de Dyck tel que pour toute paire de préfixes gauches (g',h') de (g,h) tel que |g'| =|h'|, h' contient plus de a que g'.
Lors de cet exposé, je présenterai une bijection entre les realizers et ces mots de Dyck. Cette bijection permet de dénombrer les realizers de taille n.
Let $\alpha\in S_n$ and $\tau\in S_k$ be two permutations, we say that $\alpha$ contains $\tau$ if there exists a subsequence $1\leq i_1\leq\dots\leq i_k\leq n$ such that $(\alpha_{i_1},\dots,\alpha_{i_k})$ is order-isomorphic to $\tau$; in such a context $\tau$ is usually called a pattern. We say $\alpha$ avoids $\tau$, or is $\tau$-avoiding, if such a subsequence does not exist.
We study generating functions for the number of permutations on $n$ letters avoiding 132 (or containing 132 exactly once) and an arbitrary pattern $\tau$ on $k$ letters, or containing $\tau$ exactly once. In several cases the generating function depends only on $k$ and is expressed via Chebyshev polynomials of the second kind.
Many combinatorial problems spawn from questions about certain traits of structures. Attribute grammars provide a concise way to describe such traits, like path length of trees, and furthermore are sufficiently structured that they give easy access to the related multivariate generating function equations. These equations can then be probed for information about averages and higher moments.
This approach has been well explored for structures arising from context free grammars. However, I will talk about a wider class of structures and I will give examples of their usage. In particular, I will demonstrate a Maple implementation, consider searching and sorting algorithms, and automatic average case complexity analysis.
Les problèmes de génomique comparative ont soulevé depuis une dizaine d'années de beaux problèmes combinatoires, dont le tri de permutations signées par renversements de segments, qui constitue le sujet principal de cet exposé.
Dans un premier temps, je présenterai le problème, ses applications en biologie, ainsi que l'historique des travaux combinatoires et algorithmique qu'il a suscités. Dans un second temps, je décrirai un algorithme, simple et élégant, du à Anne Bergeron, permettant de trier une permutation signée en temps optimal. Finalement, je décrirai des travaux en cours portant sur l'ensemble des suites de renversements triant une permutation en temps optimal. Ces travaux font intervenir des objets classiques et appréciés ici à Bordeaux, comme les monoïdes partiellement commutatifs, les empilements et les ensembles partiellement ordonnés.
La conjecture de Rogers et Shapiro affirme que, pour tout n>=2, il existe au moins un pavage du carré ayant côté 2n-2 au moyen de la classe Pn des polyominos parallélogrammes ayant demi-périmètre n. Dans cet exposé nous validons la conjecture pour n = 7, 8 et 9. Pour faire cela on étudie les propriétés de symétrie des éléments de Pn pour réduire le pavage à seulement un quart du carré initial, celui de côté 2n-3 et correspondant à Pn-1. On montre aussi une idée pour chercher à résoudre la conjecture pour tout n. Si n est pair, n=2p, le nombre des cellules sur la diagonale parallèle à la bissectrice des deuxième etquatrième quadrants (diagonale secondaire) des polyominos symétriques par rapport à cette diagonale, est 2n-2, c'est-à-dire la longueur de la diagonale du carré. Car 2n-2 = 22p-2 = 22(p-1) = 4p-1, l'aire du carré correspondant au cas p+1, on cherche une bijection entre toutes les cellules des polyominos de Pn et les cellules sur la diagonale secondaire des polyominos de P2(n-1) symétriques par rapport à la même diagonale.