théorème de Cayley

Prenons trois étiquettes, 1, 2 et 3. Les déplacer sans en perdre ni en répéter produit des permutations. Le théorème de Cayley dit qu’un groupe, même défini de façon abstraite, peut toujours agir ainsi sur ses propres éléments.

Avec les mêmes étiquettes comme sommets, la formule de Cayley répond à une autre question : combien d’arbres différents peut-on tracer ? Pour trois sommets, il y en a trois, selon le sommet placé au milieu du chemin.

Le nom de théorème de Cayley recouvre ici deux résultats distincts d’Arthur Cayley (1821–1895). En théorie des groupes, soit G un groupe et S(G) le groupe de toutes les bijections de l’ensemble G vers lui-même. À chaque élément g de G, on associe la permutation qui envoie tout élément x sur le produit gx. Cette action par translations à gauche est injective et respecte le produit. Elle réalise donc G comme un sous-groupe de S(G), à isomorphisme près. Le résultat vaut pour les groupes finis comme infinis.

En théorie des graphes, la formule de Cayley concerne un ensemble fini E de n étiquettes. Un arbre est un graphe simple, connexe et sans cycle dont les sommets sont exactement les éléments de E. Pour n au moins égal à 2, le nombre d’arbres étiquetés est donné par $n^{n-2}n^\{n-2\}$. Pour n = 1, l’unique sommet isolé constitue l’unique arbre. Le comptage dépend des étiquettes : il ne compte ni les formes d’arbres non étiquetées, ni les graphes orientés ou pondérés. La formule admet des généralisations et peut notamment se démontrer par le théorème de la matrice-arbre, fondé sur un déterminant.

Si G est un groupe, alors l’application qui associe à chaque élément g la permutation x ↦ gx est un homomorphisme injectif de G dans S(G). Ainsi, tout groupe est isomorphe à un sous-groupe d’un groupe symétrique.

Si E est un ensemble de n étiquettes, avec n ≥ 2, alors le nombre d’arbres simples ayant exactement E pour ensemble de sommets est $n^{n-2}n^\{n-2\}$.

Pour la version algébrique, il faut un groupe G : le produit doit être associatif, posséder un élément neutre et donner un inverse à chaque élément. L’ensemble sous-jacent peut être fini ou infini. Les translations à gauche doivent agir sur tous les éléments de G ; cette action particulière est toujours fidèle, donc injective.

Pour la formule de dénombrement, les n sommets sont distinctement étiquetés et les arêtes forment un graphe simple, connexe et sans cycle. Un graphe à trois sommets contenant les trois arêtes forme un cycle : ce n’est pas un arbre et il ne doit pas être compté. Pour compter les arbres couvrants d’un graphe dont certaines arêtes sont interdites, on emploie plutôt le théorème de la matrice-arbre.

Utilisons trois éléments étiquetés 1, 2 et 3. Les données sont le groupe cyclique G = {e, r, r²}, où r³ = e, et l’ensemble de sommets E = {1, 2, 3}.

1. Faisons agir G sur ses propres éléments par multiplication à gauche. Après avoir renommé e, r et r² par 1, 2 et 3, l’élément e donne la permutation identité, r donne le cycle (1 2 3) et r² donne le cycle (1 3 2).

2. Les trois permutations sont distinctes et leur composition reproduit le produit dans G. L’application est donc injective : ce groupe cyclique apparaît comme un sous-groupe du groupe symétrique sur trois éléments.

3. Comptons maintenant les arbres sur E. La formule donne $3^{3-2}=33^\{3-2\}=3$. Les trois arbres ont respectivement 1, 2 ou 3 comme sommet central ; la figure les énumère sans omission.

4. Contrôlons le résultat : un arbre à trois sommets possède deux arêtes. Parmi les trois arêtes possibles 12, 13 et 23, choisir n’importe quelle paire produit un chemin connexe sans cycle. Il existe bien trois choix.

En théorie des groupes, on remplace une loi abstraite par des permutations concrètes, point de départ de la représentation des groupes. Si l’on veut conserver toute l’information du groupe, l’action régulière de Cayley est préférable à une action non fidèle, qui peut envoyer plusieurs éléments sur la même permutation.

En combinatoire, la formule donne immédiatement le nombre total d’arbres lorsque toutes les arêtes entre n sommets étiquetés sont permises. Si le réseau de départ interdit certaines arêtes, la formule n’est plus adaptée ; le théorème de la matrice-arbre compte alors les arbres couvrants autorisés.

Théorème de Cayley–Hamilton. Il porte sur une matrice carrée et affirme qu’elle annule son polynôme caractéristique. Si l’objet de départ est une matrice plutôt qu’un groupe ou un ensemble de sommets étiquetés, il s’agit de Cayley–Hamilton.

Théorème de la matrice-arbre. Il calcule le nombre d’arbres couvrants d’un graphe donné à l’aide d’un déterminant. La formule de Cayley compte tous les arbres étiquetés lorsque toutes les arêtes entre les n sommets sont disponibles.

Une action quelconque peut perdre de l’information. Si un élément non neutre fixe tous les points, deux éléments du groupe peuvent produire la même permutation. Il faut alors vérifier la fidélité de l’action ou revenir aux translations sur G, qui sont toujours fidèles.

Le groupe n’a pas besoin d’être fini. Pour un groupe infini, S(G) désigne toutes les bijections de G sur lui-même, et non un groupe symétrique fini S_n. L’inclusion demeure exacte, mais elle ne fournit pas une représentation matricielle de dimension finie.

Les étiquettes changent le comptage. Deux arbres de même forme peuvent être distincts si les numéros occupent des sommets différents. Il faut utiliser nⁿ⁻² pour les arbres étiquetés ; le nombre de formes non étiquetées suit une autre suite.

Le cas n = 1 se traite séparément. Le graphe réduit à un sommet et sans arête est l’unique arbre. Pour n = 0, la notion d’arbre sur l’ensemble vide dépend des conventions ; la formule de Cayley est donc énoncée ici pour n ≥ 2.

L’article Les débuts des groupes replace les permutations et la naissance de la théorie des groupes dans leur contexte mathématique.

La fiche arbre - graphe - précise la connexité, l’absence de cycle et les propriétés structurelles de l’objet compté par la formule de Cayley.