Le vendredi, de 10h40 à 11h40, dans l'amphithéâtre du LaBRI.
9 juillet 2001 : Renzo Pinzani
La moitié du plus grand des binomiaux et ses environs
(About half the middle binomial coefficients)
Nous présentons diverses interprétations combinatoires de la séquence
de nombres positifs ½ C(2n,n), en utilisant des techniques bijectives.
Ces nombres apparaissent souvent quand on travaille avec des classes
d'objets combinatoires tels que les arbres ordonnés, les chemins dans
le plan discret et les polyominos.
6 juillet 2001 : Elisa Pergola
Aires des chemins de Motzkin généralisés
(A bijective approach to the area of generalized Motzkin paths)
Dans le plan à cordonnées entières nous considérons les chemins dont
les pas sont (1,1) (1,-1) et des pas horizontaux (h,0), h>0.
Soit E(n) l'ensemble de ces chemins allant de (0,0) à (n,0) et restant
toujours au-dessus de l'axe x.
Nous démontrons que l'aire totale des régions limitées par les chemins
de E(n) et l'axe x satisfait une récurrence qui dépend seulement de h.
De plus nous donnons une preuve que l'aire totale au dessous des
chemins de E(n) est égale au nombre total de points (x,0), x entier,
qui appartiennent à certains chemins allant de (0,0) à (n-2,0).
29 juin 2001 : Emeric Gioan
Les deux exposés seront indépendants, bien qu'un peu liés.
Le polynôme de Tutte des graphes aux matroïdes
Les matroïdes généralisent les graphes en tant qu'ensembles de cycles.
Ils ont l'intérêt d'avoir une notion de dualité omniprésente et de
permettre de représenter combinatoirement les dépendances linéaires de
vecteurs dans l'espace, ce qui leur donne un important aspect géométrique.
En particulier, le polynôme de Tutte et ses propriétés énumératives se
généralisent très bien aux matroïdes.
Correspondance naturelle entre simplexes et régions d'un arrangement d'hyperplans
Le polynôme de Tutte d'un arrangement d'hyperplans totalement ordonné
peut s'écrire d'une part comme série génératrice des activités de ses
bases (simplexes) et d'autre part comme série génératrice des activités
de ses réorientations (les régions étant les réorientations dites
acycliques).
Il s'agit de prouver « bijectivement » l'égalité de ces formulations.
On obtient en particulier une correspondance naturelle entre certains
simplexes et les régions, qui traduit la façon dont celles-ci se
« cristallisent » sur l'ensemble ordonné d'hyperplans, et qui
généralise la traduction combinatoire de la programmation linéaire.
Dans le cas particulier d'un graphe, on obtient une correspondance
entre forêts couvrantes et orientations.
Cependant l'exposé sera plutôt géométrique, illustré dans le cadre des
arrangements de (pseudo)droites (le cadre général étant celui des
matroïdes orientés).
22 juin 2001 : Xavier Viennot
Gravitation quantique Lorentzienne et chemins de Dyck
La gravitation quantique est actuellement un domaine très actif de la
physique théorique. Il s'agit de réunir deux théories incompatibles :
la relativité générale et la mécanique quantique. Dans cet exposé, je
me propose d'expliquer d'un point de vue combinatoire des articles
récents sur un modèle résoluble de gravitation quantique, à savoir un
modèle discret de « gravitation quantique Lorentzienne » en deux
dimensions [1], [2].
L'espace-temps à deux dimensions (une dimension pour le temps et une
pour l'espace) est discrétisé par des triangulations dites
Lorentziennes, c'est-à-dire que les sommets des triangles sont situés
sur les droites parallèles à temps constant. Résoudre le modèle
revient pour les physiciens à trouver la série génératrice de ces
triangulations.
L'article [1] donne une équation fonctionnelle faisant apparaître la
série génératrice des nombres de Catalan.
L'article [2] en donne l'explication avec de belles bijections faisant
intervenir des chemins de Dyck, des arbres et des empilements de
dominos. Un paramètre est introduit rendant compte de la « courbure »
de l'espace-temps. Ce paramètre est en relation avec certains
paramètres sur les animaux dirigés chers à Mireille B.-M. ...
[1] J. Ambjorn et R.Loll, " Non-perturbative Lorentzian quantum
gravity, causality and topology change ", Nucl.Phys. B536 (1998)
407-434, arXiv : hep-th/9805108
[2] P. Di Francesco, E.Guitter et C. Kristjansen, " Integrable 2D
Lorentzian gravity and random walks ", Nucl.Phys. B567 (2000) 515-553,
arXiv : hep-th/9907084
15 juin 2001 : Eric Sopena
Homomorphismes et colorations de graphes orientés
La notion d'homomorphisme permet de généraliser la notion
de coloration, bien connue dans le cas des graphes non
orientés. En considérant le cas des graphes orientés
(antisymétriques), la notion d'homomorphisme induit une
nouvelle notion de coloration et de nombre chromatique
orienté.
Nous présenterons un survol de quelques résultats obtenus
dans ce cadre, en nous attardant sur des questions
concernant les graphes planaires.
Nous montrerons quelques techniques de preuves sur des
cas particuliers simples et terminerons en mentionnant
plusieurs problèmes ouverts.
18 mai 2001 : Philippe Duchon
(travail en cours avec Maylis Delest et Jean-Marc Fédou)
Nombres de Strahler pour des familles simples d'arbres
On définit pour un arbre enraciné quelconque, le nombre de Strahler de
manière à étendre naturellement sa définition sur les arbres binaires.
Pour des familles simples d'arbres (au sens de Meir et Moon : les
arbres autorisés sont déterminés seulement par l'ensemble possible des
degrés des sommets), je montrerai comment obtenir des équations
portant sur différentes séries génératrices. Si la valeur moyenne de
ce paramètre semble difficile d'accès, on obtient toutefois le
résultat surprenant que, pour toutes les familles d'arbres à degrés
bornés, le ratio
{nombre moyen de segments de Strahler k des arbres de taille n} /
{nombre moyen de segments de Strahler k+1 des arbres de taille n}
tend, lorsque n, puis k tendent vers l'infini, toujours vers la même
limite : 4.
11 mai 2001 : Mireille Bousquet-Mélou
Le périmètre de site des polyominos un peu convexes
Des polyominos ! Ca faisait longtemps qu'on n'avait pas parlé de
polyominos. Faut dire qu'on avait déjà tellement appris... Notamment
que la série génératrice selon le périmètre (usuel) des polyominos
ayant une propriété de convexité était toujours ALGEBRIQUE. Bon.
Pour le périmètre de site (le nombre de cellules adjacentes au
polyomino), les choses se gâtent : pour les polyominos convexes
(verticalement ET horizontalement), la série reste algébrique, mais
si on ne garde que la convexité verticale, changement de décor !
On passera du temps à expliquer :
1. pourquoi c'est plus dur
2. pourquoi c'est quand même pas si dur puisqu'on l'a résolu
(on = Andrew Rechnitzer et moi-même).
27 avril 2001 : Serge Dulucq
Algorithmique des séquences et de structures biologiques
Dans une première partie, nous présenterons quelques motivations qui
conduisent les biologistes à comparer (aligner) des séquences ou des
structures. Dans ce contexte, nous nous intéresserons au problème de
la comparaison de structures secondaires. Nous expliquerons l'approche
que nous utilisons reposant sur une représentation arborescente (plus
ou moins fine) de ces structures secondaires. Nous présenterons en
détail l'algorithme de Zhang et Shasha sur lequel reposent les outils
que nous développons. Nous réaliserons une analyse exacte de cet
algorithme faisant intervenir un nouveau (?) paramètre sur les arbres.
Pour terminer, nous monterons un exemple d'alignement de structures
secondaires reposant sur cet algorithme dans lequel nous avons
introduit un certain nombre de contraintes de nature biologique.
23 mars 2001 : Cédric Chauve
(travail en collaboration avec Serge Dulucq et Philippe Duchon)
Inversion dans les arborescences
On présente quelques constructions combinatoires élégantes
permettant de compter les arborescences de Cayley selon le
nombre d'inversions.
On s'intéresse en particulier à notre famille préférée des
arborescences dont la racine est inférieure à ses fils,
généralisant ainsi des résultats de Kreweras sur les
arborescences de racine 1.
16 mars 2001 : Pierre Leroux
(travail en collaboration avec Pierre Auger et Gilbert Labelle)
Formules d'addition pour l'espèce des polygones (cycles non orientés)
Je vais présenter des formules d'addition liées à quelques
espèces de graphes comme celles des ensembles (graphes discrets),
des listes (chaînes orientées), des chaînes, des cycles (orientés)
et des polygones (cycles non orientés), en insistant plus
particulièrement sur ce dernier cas.
Il s'agit d'un travail en collaboration qui sera présenté au Colloque
SFCA-FPSAC-01 à Tempe, Arizona.
9 mars 2001 : Alain Denise (LRI et IGM)
Deux applications de la génération aléatoire
Je présenterai deux types de travaux en cours à Orsay :
- La génération de jeux de tests de programmes.
Je présenterai les bases du test statistique structurel des logiciels,
puis la façon dont le module CS de génération aléatoire de structures
combinatoires est utilisé dans le cadre de recherches sur la génération
automatique de jeux de tests.
- La génération de séquences génomiques aléatoires pour les biologistes.
Je présenterai les motivations biologiques de ce travail, l'approche
combinatoire utilisée et un logiciel en cours de développement.
Recently, Babson and Steingrímsson have introduced generalised
permutation patterns that allow the requirement that two adjacent
letters in a pattern must be adjacent in the permutation. I will
consider pattern avoidance for such patterns, and give a complete
solution for the number of permutations avoiding any single pattern
of length three with exactly one adjacent pair of letters. For eight
of these twelve patterns the answer is given by the Bell numbers. For
the remaining four the answer is given by the Catalan numbers.
I also give some results for the number of permutations avoiding two
different patterns. These results relate the permutations in
question to Motzkin paths, involutions and non-overlapping
partitions. Furthermore, I define a new class of set partitions,
called monotone partitions, and show that these partitions are in
one-to-one correspondence with non-overlapping partitions.
9 février 2001 : David Renault
A bijection between ordered trees and 2-Motzkin paths and its many consequences
Présentation d'un article d'Emeric Deutsch et Louis W. Shapiro exposé
au LaCIM 2000 : parmi les structures combinatoires classiques, comme
les arbres ou les chemins dans le plan, il existe de nombreux théorèmes
de bijection, liés entre autres aux nombres de Catalan.
Cet article propose un type (a priori) nouveau de bijection entre les
arbres classiques et les chemins de Motzkin bicolorés, bijection qui a
l'avantage de mettre en valeur de manière élémentaire des propriétés
classiques sur les graphes en général.
En appliquant cette bijection, il permet de prouver quelques résultats
ayant trait entre autres aux buissons, aux arbres-{1,2}, aux chemins de
Schröder et aux suites de Davenport-Schinzel.
2 février 2001 : Nasser Saheb
Processus de mort et l'algorithme d'élection dans un arbre
Une élection dans un arbre peut être modélisée par une
suite d'effeuillage qui réduit l'arbre à un sommet unique,
appelé sommet élu. Suivant des algorithmes existants et en
accord avec le principe de distributivité, dans le modèle
proposé, tout sommet qui devient feuille, a une durée de
vie suivant une loi exponentielle. Le sommet qui survit à tous
les autres sera le sommet élu. De façon tout à
fait équivalente, dans ce modèle (temps continu), la
probabilité de mort pour toute feuille $f$, dans un intervalle
du temps $[t,t+h[$ est $\lambda_f h+ o(h)$, où $\lambda_f$,
paramètre du processus de mort pour $f$, est déterminé
par un calcul local à l'instant où $f$ devient une feuille
dans l'arbre. Nous proposons en particulier une structure
de contrôle, via un calcul local de $\lambda_f$, qui accorde
la même chance d'être élus à tous les sommets de l'arbre.
19 janvier 2001 : Akka Zemmari
Élections locales : analyse probabiliste et efficacité
Dans cet exposé, je présenterai des algorithmes probabilistes pour
réaliser des élections locales, ce qui permet d'implémenter des
algorithmes distribués (tels que le calcul d'arbre couvrant,
l'algorithme SSP et l'algorithme de Mazurkiewicz).
Après une introduction au problème, je présenterai une analyse de
ces algorithmes ainsi qu'une étude de leur efficacité, et je
terminerai par quelques perspectives.
12 janvier 2001 : Cédric Chauve
Arbres et couplages (d'après Kenyon, Propp et Wilson)
On présente une extension au cas des graphes planaires pondérés et
orientés d'une bijection classique de Temperley (1974) entre arbres
couvrants et couplages parfaits.
1er décembre 2000 : Philippe Duchon
Un exemple de dérandomisation :
la "méthode des estimateurs pessimistes"
Il est fréquent que la méthode probabiliste donne des résultats
d'existence, sous la forme "la probabilité que tel procédé aléatoire
donne un résultat acceptable est strictement positive".
La dérandomisation consiste à transformer ce genre de résultat en un
algorithme déterministe fournissant un "résultat acceptable".
Je donnerai un exemple d'application (qui, me semble-t-il, est
nouveau) d'une méthode due à Raghavan et connue sous le nom de
"méthode des estimateurs pessimistes" - qui est elle-même une
extension de la "méthode des probabilités conditionnelles".
Dans l'exemple considéré, on se donne une matrice booléenne (à
coefficients 0 et 1), et on cherche une permutation des lignes qui
minimise le maximum, parmi les colonnes, du nombre de facteurs 01
dans la colonne.
L'algorithme que je présenterai garantit non pas l'optimum, mais
trouve, en temps polynomial et de manière déterministe, un résultat
qui est en n/4+o(n) - dont l'existence est assurée par une preuve
à base de comptage de Gavoille et Peleg.
17 novembre 2000 (1er exposé) : Xavier Viennot
La conjecture qt-Catalan
A. Garsia et M. Haiman ont introduit en 1994 un polynôme en variables q et t,
dont la somme des coefficients redonne le nombre de Catalan. Pour certaines
spécifications des variables, on retrouve les deux q-analogues classiques des
nombres de Catalan (nombre d'inversions et indice du majeur).
Un problème célèbre était de trouver une interprétation combinatoire de ces
polynômes. Nous donnons la solution que vient de découvrir J. Haglund,
étudiant de A. Garsia à San Diego. Elle s'exprime en termes de chemins de
Dyck. Un problème reste ouvert pour les amoureux des bijections.
17 novembre 2000 (2nd exposé) : Alexandre Zvonkine
Un exposant critique "exact" (?) pour l'asymptotique des méandres
(d'après Di Francesco et al.)
Pour l'asymptotique des méandres la valeur numérique de l'exposant critique
est estimée à 3.4206...
Récemment les physiciens de Saclay ont donné une "preuve physique" du fait
que sa valeur exacte est (29+sqrt(145))/12 = 3.4201...
Leur preuve utilise les paramètres physiques dont le sens reste à comprendre
(notamment la charge centrale).
Séries détendues : une méthode pour calculer les coefficients
de séries formelles de façon très rapide
Cet exposé concerne l'évaluation rapide de coefficients d'une série formelle.
Classiquement, on distingue l'approche zélée (pour une opération comme la
multiplication de f et g, ceci revient à supposer que l'on connaît les n
premiers coefficients de f et de g et que l'on vise le calcul des n premiers
coefficients de fg) et l'approche paresseuse (on calcule les coefficients un
par un et on ne fait que les calculs nécessaires à chaque étape.
Dans ce cas, le i-ième coefficient de fg sera connu dès que les i premiers
coefficients de f et g seront connus).
Je rappellerai les résultats classiques de complexité pour ces approches.
Ensuite, j'exposerai une nouvelle approche, dite détendue, qui donne les
meilleurs bornes de complexité actuelles pour un grand nombre de problèmes
comme la résolution d'équations fonctionnelles ou aux dérivées partielles.
Je parlerai également d'une implantation provisoire qui confirme ces
résultats théoriques, mais qui pourrait encore grandement être améliorée...
27 octobre 2000 : Jean-Christophe Aval
Sur certains espaces de polynômes quasi harmoniques
Le but de ce travail est l'étude de certains polynômes $\Delta_D(X,Y)$
associés à des diagrammes du réseau carré, introduits par F. Bergeron,
N. Bergeron, A. Garsia, M. Haiman et G. Tesler et d'étendre des résultats
obtenus par J.-C. Aval, F. Bergeron et N. Bergeron.
Rappelons que $M_D$ désigne l'espace engendré par toutes les dérivées
partielles de $\Delta_D$.
Dans ce travail, nous voulons étudier l'espace $M^k_{i,j}(X,Y)$ qui est
défini comme la somme des espaces $M_D$ où $D$ décrit l'ensemble des
diagrammes obtenus en enlevant $k$ cases à une partition donnée, toutes
ces cases étant dans l'ombre de $(i,j)$ dans le diagramme de
Ferrers.
Nous obtenons une majoration pour la dimension de cet espace que nous
conjecturons comme optimale.
Cette majoration est exacte quand on se restreint au seul alphabet $X$,
cas pour lequel nous construisons une base explicite.
20 octobre 2000 : Yvan Le Borgne
Modèle du tas de sable et Polynôme de Tutte
Pour tout graphe G, il y a autant d'arbres couvrants d'activité externe i
que de configurations récurrentes de niveau i dans le modèle du tas de
sable (Merino-Lopez 1997).
"Donc" il existe une bijection naturelle entre ces deux ensembles d'objets.
Après en avoir explicité une, on discutera de son intérêt vis-à-vis du
polynôme de Tutte et du modèle du tas de sable.
Absence de torsion dans les groupes de tresses et leurs généralisations
Une technique de combinatoire des mots appelée retournement permet
d'établir très simplement que les groupes de fractions de monoïdes
admettant des ppcm sont sans torsion (et de construire à l'aide d'un
transducteur rationnel des formes normales).
Ceci s'applique en particulier aux groupes de tresses et aux groupes
d'Artin.
6 octobre 2000 : Mireille Bousquet-Mélou (travail en collaboration avec Gilles Schaeffer)
Chemins discrets du plan évitant une demi-droite
On s'intéresse à l'énumération des chemins sur réseau
carré évitant le demi-axe horizontal négatif, et à
certaines variations sur ce modèle, obtenues en
autorisant des pas plus fantaisistes.
Ces chemins ont une série génératrice algébrique
que l'on comprend, doucettement, de mieux en mieux.
Je présenterai quelques preuves simples tournant
autour de ce résultat.