21.4 Preuve du théorème de Wigner simplifié
291
1
2
3
4
5
6
1
2
3
Fig. 21.3. En haut à gauche le multi-graphe orienté associé au long exemple
E(M12M23M32M24M45M54M46M64M42M21), qui est de type 1. En haut à droite le
multi-graphe orienté associé à E(M12M23M31), qui est de type 2. En bas à gauche
le multi-graphe orienté associé à E(M12M21M13M32M23M31), et en bas à droite le
multi-graphe orienté associé à E(M12M21M12M21), tous deux de type 3.
1
2
3
1
2
Nous abordons à présent la phase finale :
— Les multi-graphes orientés de type 2 ont une contribution nulle. En
effet dans ce cas E(M G ) = 0 par indépendance et centrage ;
— Les multi-graphes orientés de type 3 ont une contribution asymptotiquement nulle. En effet, si G est de type 3 alors il contient au moins
trois arêtes de mêmes extrémités ou un cycle d’arêtes d’extrémités différentes, ce qui implique dans les deux cas l’inégalité 2t r+1, qui donne
la majoration n(n − 1) · · · (n − t + 1) n
t
n
1/2+r/2 . D’autre part,
le nombre de classes d’équivalences de multi-graphes orientés G(r, t)
est majoré par t
r = O(1). Comme les coefficients de M sont bornés à
valeurs dans [−C, C], on a également E(M G ) C
r = O(1), d’où enfin
cl. t. 3
n(n − 1) · · · (n − t + 1)
n 1+r/2
E(M G ) = O(n
−1/2 ) = o n→∞ (1);