Bijection de Joyal

La bijection de Joyal consiste à "déplier", avec la correspondance principale de Foata, la partie cyclique d'une application de dans pour en faire un arbre de Cayley.



Catégories :

Analyse combinatoire - Probabilités - Théorie des graphes

Page(s) en rapport avec ce sujet :

  • ... sans boucle pourvu d'une bijection entre les sommets et la totalité [n]. Un... L'elément 1 ∈ RT (1) est l'unique arbre enraciné `a un seul sommet qui est la...... [Joy86] André Joyal, Foncteurs analytiques et esp`eces de ... (source : math.univ-paris13)
  • On ordonne ces éléments en parcourant l'arbre sommet par sommet, ...... On a supposé au départ que le domaine t0 = In τ est en bijection avec un ensemble...... [15] A. Joyal, Disks, duality and Θ-categories, prépublication (1997).... (source : arxiv)

La bijection de Joyal consiste à "déplier", avec la correspondance principale de Foata, la partie cyclique d'une application de dans pour en faire un arbre de Cayley. La bijection de Joyal sert à donner une démonstration élégante de la formule, attribuée à Arthur Cayley, selon laquelle le nombre d'arbres étiquetés à n sommets, nommés aussi arbres de Cayley, est :

n (n − 2) .

La bijection de Joyal est aussi particulièrement utile pour l'étude des propriétés métriques des arbres étiquetés à n sommets.

Une application : une démonstration de la formule de Cayley

Notons la totalité des arbres de Cayley à n sommets. Pour calculer le cardinal de une des démonstrations consiste à établir une bijection, nommée bijection de Joyal, entre et la totalité des applications de dans, noté habituellement. On a ainsi

nˆn\ =\ \text{Card}\ [\![1,n]\!]ˆ{[\![1,n]\!]}\ =\ \text{Card}\ \left(\mathcal{C}_n\times[\![1,n]\!]ˆ2\right)\ =\ nˆ2\,\text{Card}\ \mathcal{C}_n.

Cette démonstration est attribuée à André Joyal par Aigner et Ziegler[1], ou encore par Pitman[2].

On peut voir comme la totalité des arbres de Cayley à n sommets, dont deux sommets sont marqués, de deux marques différentes. Le sommet portant la première marque peut être interprété comme la racine de l'arbre. Les deux marques différentes peuvent être portées par le même sommet.

La bijection de Joyal permet aussi de mieux comprendre la topologie d'un arbre de taille n, en étudiant la distance entre 2 sommets au hasard d'un arbre au hasard. En effet, un élément tiré au hasard avec équiprobabilité dans est un arbre de Cayley, avec deux points marqués, tiré au hasard : calculer la loi de différentes statistiques portant sur un arbre de Cayley, avec deux points marqués, tiré au hasard, revient à calculer le cardinal de différentes parties de l'univers Pour cela il peut être plus simple de calculer le cardinal de l'image de ces parties par la bijection de Joyal.

Représentation graphique d'une application

Représentation graphique de l'application ƒ = (12, 15, 2, 13, 10, 10, 13, 9, 19, 17, 18, 12, 15, 16, 20, 14, 2, 2, 13, 8) .

Pour décrire la bijection de Joyal, il est commode d'utiliser une représentation de chaque application ƒ de dans avec un graphe orienté dont la totalité des sommets est et où les arètes relient chaque élément à son image par ƒ. A titre d'exemple, pour ƒ = (12, 15, 2, 13, 10, 10, 13, 9, 19, 17, 18, 12, 15, 16, 20, 14, 2, 2, 13, 8), c'est-à-dire, pour ƒ (1) = 12, ƒ (2) = 15, ƒ (3) = 2, ... on a la représentation graphique ci-contre.

Éléments cycliques et éléments transients

Dans la totalité de définition de ƒ on peut distinguer les éléments cycliques (ou récurrents) des éléments transients : les éléments cycliques, figurés ci-contre en bleu, sont les éléments x pour lesquels il existe nx > 0 tel que :

fˆ{n_x}(x)=x.

A titre d'exemple, ci-contre, n12 = 1, n16 = 2, et n8 = 6. A chaque application ƒ de dans on peut associer la chaîne de Markov dont la probabilité de transition est définie par

p_{i,f(i)}=1,\qquad \forall i\in[\![1,n]\!].

Les éléments récurrents et les éléments transients de ƒ sont alors précisément les éléments récurrents et les éléments transients de cette chaîne de Markov.

Correspondance de Foata

Correspondance de Foata appliquée à la restriction τ de ƒ à C. Les deux points marqués de l'arbre de Cayley (associé à ƒ par la correspondance de Foata) sont ici 9 et 14.

La totalité C des éléments cycliques de ƒ est le plus grand sous-ensemble de ayant la propriété suivante :

On peut alors appliquer la correspondance de Foata à la restriction de ƒ à C, que nous noterons τ, et obtenir ainsi un arrangement (une suite ordonnée) ω de l'ensemble des éléments de C. La correspondance de Foata consiste à écrire la suite des cycles de la décomposition en cycles disjoints de τ, en prenant bien soin :

Le premier et le dernier terme de l'arrangement ω ainsi obtenu sont conçus pour être les deux sommets marqués de l'arbre de Cayley produit, à partir de ƒ, par la bijection de Joyal.

Bijection de Joyal

Image de l'application ƒ par la bijection de Joyal. Le "début" (x=9) est coloré en vert, et la "fin" (y=14) en orange.
Image réciproque, par la bijection de Joyal, de l'arbre marqué obtenu en intervertissant les deux marques de l'arbre précédent.

On observe qu'une fois effacées les arètes entre les éléments cycliques de ƒ, la représentation de ƒ ainsi modifiée devient une forêt (un graphe sans cycles, peut-être non connexe, dont les composantes connexes sont exactement des arbres), chaque arbre de la forêt pouvant être vu comme enraciné en un des éléments cycliques de ƒ. En "replantant" chacun de ces arbres sur le sommet correspondant du graphe linéaire associé à l'arrangement de l'ensemble des éléments de C produit par la correspondance de Foata, on obtient un arbre de Cayley avec deux sommets marqués.

Réciproquement, la donnée d'un arbre de Cayley T avec deux points x et y marqués, peut-être égaux, l'un marqué "début" et l'autre "fin", par exemple, définit

A cette suite ω on peut appliquer la correspondance de Foata, pour trouver une permutation τ des nombres constituant ω, permutation dont le graphe est une collection de cycles. Ces cycles sont délimités par les records vers le bas de la suite obtenue en renversant la suite ω, i. e. les records observés en parcourant le chemin de y vers x.

Sur l'exemple ci-contre, x = 9 et y = 14, et le chemin minimal est ω = (9, 19, 13, 15, 20, 8, 12, 16, 14) . Les records de la suite renversée (14, 16, 12, 8, 20, 15, 13, 19, 9) sont successivement 14, 12 et 8, ce qui conduit à la décomposition de τ en cycles disjoints :

\tau\ =\ (9, 19, 13, 15, 20, 8) (12) (16,14).

On retrouve bien ainsi les cycles de ƒ.

Une fois effacées les arètes composant le chemin de longueur minimale entre x et y, l'arbre de Cayley T ainsi modifié devient une forêt, chaque arbre de la forêt pouvant être vu comme enraciné en un des sommets du chemin entre x et y. En "replantant" chacun de ces arbres sur le sommet correspondant du graphe de τ, on obtient le graphe de ƒ.

A titre d'exemple, si on intervertit les rôles de x et y, on obtient un nouvel élément de Examinons son image réciproque g par la bijection de Joyal : la totalité des étiquettes des sommets apparaissant sur le chemin de y à x reste le même, mais la suite η obtenue est la suite inverse de la suite ω observée auparavant. Les records vers le bas de la suite renversée de η (à savoir la suite ω) sont alors 9 puis 8, conduisant à une décomposition en cycles (14, 16, 12, 8) (20, 15, 13, 19, 9) de la partie cyclique de g. On récupère alors, comme attendu, une application g = (12, 15, 2, 13, 10, 10, 13, 14, 20, 17, 18, 8, 19, 16, 13, 12, 2, 2, 9, 15) différente de l'application ƒ qu'on avait au départ (voir ci-dessus).

Distance entre deux points au hasard d'un arbre de Cayley aléatoire

Comme autre application, on peut citer le calcul de la loi de la distance entre deux points au hasard d'un arbre de Cayley aléatoire, qui, en vertu de la bijection de Joyal, est aussi la loi du nombre de points cycliques d'une application de dans. Notons le nombre d'éléments de tels que les deux points marqués soient à distance k l'un de l'autre. Pour on a :

d_{n,k}\ =\ {n\choose k+1}\times (k+1)!\times nˆ{n-k-1}\times \frac{k+1}n,

où compte les choix envisageables de la totalité des étiquettes des k+1 points sur le chemin entre les deux points marqués, où compte les manières d'ordonner ces k+1 étiquettes le long du chemin entre les deux points marqués, le facteur restant comptant les forêts de k+1 arbres comportant au total n-k-1 sommets (sans compter les k+1 racines) qu'on pourrait planter le long de ce chemin. Il suit que, toujours pour

\mathbb{P}\left(D_n=k\right)\ =\ nˆ{-n}d_{n,k}\ =\ \frac{(k+1)\times(n)_{\downarrow k+1}}{nˆ{k+2}}.

Cette loi discrète apparaît aussi dans des problèmes d'allocations (boules et urnes), dont le fameux problème des anniversaires. On peut montrer, par exemple à l'aide du lemme de Scheffé, que converge en loi vers la loi de Rayleigh, ce qui indique que la distance "typique" entre deux points d'un arbre de taille n est de l'ordre de

Voir aussi

Pages liées

Notes

  1. (en) Martin Aigner et Günter M. Ziegler, Proofs from THE BOOK, Springer-Verlag, 8 octobre 2003, 3e éd. , 240 p. (ISBN 3540404600)  , pp. 141–146.
  2. (en) Jim Pitman, Combinatorial Stochastic Processes : Ecole d'Eté de Probabilités de Saint-Flour XXXII - 2002, Springer, coll. «Lecture Notes in Mathematics», 6 juillet 2006, 1re éd. , 256 p. (ISBN 354030990X)  .

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Bijection_de_Joyal.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu