Précédent Index Suivant

Chapitre 7   Spectres

Certains paramètres importants des graphes finis sont approchés plus ou moins efficacement par des méthodes spectrales. Par exemple, le nombre de stabilité, le max-cut, le diamètre.

On peut donc se demander si pour les graphes de Cayley le spectre se calcule commodément.

7.1   Spectres

On peut représenter le graphe par sa matrice d'adjacence A : il y a autant de lignes et colonnes que de sommets, chaque arête {ij} donne les coefficients Aij=Aji=1, les autres coefficients sont nuls. Le spectre de cette matrice ne dépend pas de l'ordre dans lequel on a mis les sommets. C'est le spectre du graphe.

On peut également prendre la matrice Laplacienne L=D-A où D est la matrice diagonale avec Dii égal au degré du sommet i. La aussi, le spectre de la matrice Laplacienne est attaché au graphe, et non à l'ordre choisi pour les sommets. C'est le spectre Laplacien du graphe.

Pour un graphe régulier, chacun de ces spectres se calcule aisément à partir de l'autre.

7.2   Paramètres liés au spectre

Le nombre d'arêtes entre deux parties de taille t et n-t de l'ensemble des sommets s'encadre avec µ t(n-t)/n et l t(n-t)/n, où µ et l sont la plus plus petite et la plus grande valeur propre, après suppression d'une occurrence de 0 dans le spectre Laplacien. Voir [128].

Le nombre de stabilité est majoré pour un graphe k-régulier selon a£ (l-k)/l, où l est la plus grande valeur propre du Laplacien. Voir [123].

Le diamètre (non orienté) se majore avec les valeurs extrêmes du spectre Laplacien : si l1=0£l2<···£ln sont ces valeurs propres, le diamètre est au plus ëargcosh(n-1)/argcosh(ln+l1/ln-l1) û+1 (pour un graphe connexe non complet). Voir [35].

Pour des raffinements, voir [64, 63].

Le diamètre est majoré par le nombre de valeurs propres distinctes du graphe, diminué de 1. Voir [24].

7.3   Groupes abéliens

La réponse est franchement oui si le groupe est abélien. Car alors les valeurs propres de Cay(G,S) sont tous simplement les åsÎ Sc(s), où c parcourt les caractères du groupe. On sait que tout groupe abélien fini se met sous la forme
/a1×/a2×···×/ak
et alors ses caractères sont les fonctions
(x1,x2,...,xk)|® exp(2p iå xiyi/ai)
Ainsi chaque caractère est déterminé par les k éléments yiÎ/ai. On sait que tout groupe abélien fini se met sous cette forme.

7.3.1   Exemple

Les valeurs propres de la matrice d'adjacence du graphe de la figure 1.7 sont 4 (multiplicité 1) et chacune des trois valeurs de 2cos(2p p/13)+2cos(10p p/13) obtenues pour 0<p<13, soit 0.2738, 1.3772, -2.6510 environ, avec multiplicité 4.

On en déduit, par exemple, que le nombre de stabilité est au plus 132.6510/6.6510~ 5.18, donc au plus 5. (la vraie valeur est 4), et le max-cut au plus (6*7/13)*6.6510~ 21.48, donc au plus 21. (la vraie valeur est 20).

7.4   Autres groupes finis

On n'a plus autant de caractères de degré 1, il faut donc se rabattre sur les représentations de degré plus grand.

Par exemple pour le groupe 3, on a en choisissant le générateur {(12),(13)} et le générateur {(12),(13),(23)} le 6-cycle et le biparti complet K3,3 respectivement, ce qui donne, en considérant les 4 représentations irréductibles les cas suivants (les deux cas de dimension 2 donnent la même chose),
I 123 132 13 12 23 12,13 12,13,23
1 1 1 1 1 1 2 3
1 1 1 -1 -1 -1 -2 -3
é
ë
1 0
0 1
ù
û
é
ë
0 -1
1 -1
ù
û
é
ë
-1 1
-1 0
ù
û
é
ë
-1 0
-1 1
ù
û
é
ë
0 1
1 0
ù
û
é
ë
1 -1
0 -1
ù
û
é
ë
-1 1
0 1
ù
û
é
ë
0 0
0 0
ù
û
Ce qui donne le spectre [-2,-1,-1,1,1,2] pour le 6-cycle et [-3,0,0,0,0,3] pour le biparti complet. On peut aussi avoir ces graphes avec le groupe /6 et les générateurs {-1,1} et {-1,1,3}

7.4.1   Cas du générateur stable par conjugaison

On note que si S est une réunion de classes de conjugaisons de G, (c'est-à-dire que si sÎ S alors gsg-1Î S pour tout g]in G), alors le spectre est assez facile à calculer, vu la théorie des schémas d'association. Voir par exemple [29].

7.4.2   Exemple

Les 6 transpositions dans le groupe 4 donnent en rangeant les classes de conjugaison des permutations dans l'ordre {I}, {3-cycles}, {bitranspositions}, {transpositions}, {4-cycles}. la matrice d'intersection suivante:

0 0 0 1 0
0 0 0 4 4
0 0 0 1 2
6 3 2 0 0
0 3 4 0 0

ce qui signifie que pour toute bitransposition b il y a 2 transpositions telles que bt soit une transposition et 4 transpositions t telles que bt soit un 4-cycle etc. D'où le spectre ±61, ±29, 04.

La table est la même en échangeant les transpositions et les permutations circulaires. Le graphe de Cayley défini avec le générateur formé des 6 permutations circulaires a donc le même spectre, mais il n'est pas isomorphe au précédent, car il ne contient pas de sous-graphe induit isomorphe à K3,3. La figure 7.1 montre les points à distance au plus 2 de l'identité dans les deux cas.



Figure 7.1 : Voisinages de l'identité dans deux graphes de Cayley sur 4

7.5   Groupes engendrés par des transpositions

On considère un graphe connexe G. À chaque arête est associée la transposition qui échange ses extrémités. Le groupe engendré par ces transpositions est le groupe V des permutations de l'ensemble des sommets.

On peut considérer le graphe de Cayley défini par le groupe V et l'ensemble des transpositions attachées aux arêtes de G.

Un problème est de montrer que le spectre Laplacien de G est inclus dans celui du graphe de Cayley. Voir [14] ou [72].

7.5.1   Exemples

Le chemin de longueur n a pour spectre {2cos(p/(n+1)),1£ k£ n} et pour spectre Laplacien {4sin2(kp/(2n)),0£ k£ n-1}

Le graphe de Cayley correspondant à ces transpositions, pour n=3 est le 6-cycle, dont le spectre Laplacien est {0,1,1,3,3,4}, qui contient bien {0,1,3}.

Pour n=4, on obtient le permutoèdre sur 4 éléments (fig 7.2).



Figure 7.2 : Le permutoèdre sur 4 éléments

Le spectre laplacien est alors {0,2±Ö(2),2}, il est bien contenu dans celui du permutoèdre, qui est {0,(3±Ö(3))2,(4±Ö(2))3,(2±Ö(2))3,23,43,6}, où les indices représentent les multiplicités. Remarquons que le sous groupe B à deux éléments de 4 correspondant à l'automorphisme du chemin fournit un automorphisme du graphe. Le quotient par ce sous-groupe (les sommets sont les gB, gÎ4) est dessiné sur la figure 7.3).



Figure 7.3 : Le quotient du permutoèdre sur 4 éléments

Pour plus de renseignements sur les permutoèdres, voir par exemple [114, 115].

Pour K1,3 le spectre est {02,±Ö(3)}, le spectre Laplacien est {0,12,4}, et le graphe de Cayley correspondant est le star-graphe de la figure 7.4. Le spectre Laplacien de ce star-graphe est {0,16,23,34,43,56,6}, les indices représentent les multiplicités.



Figure 7.4 : Le graphe de Cayley associé à K1,3

Pour le n-cycle, n³3, le spectre est le multi-ensemble {2cos2kp/n,k=0..n-1}, et le spectre Laplacien le multi-ensemble {4sin2kp/n,k=0..n-1}.

Le graphe attaché au 3-cycle (spectre Laplacien {0,32}) est K3,3 (spectre Laplacien {0,34,6}). Pour le 4-cycle (spectre Laplacien {0,22,4}), on obtient le graphe de la figure 7.5. Ces deux graphes ont (de façon exceptionnelle) plus d'automorphismes que ne le laisse prévoir le groupe d'automorphismes du graphe de départ (voir [67]).



Figure 7.5 : Le graphe de Cayley associé à C4

Précédent Index Suivant