Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

´SPECTRE D’OPERATEURS
∗´DIFFERENTIELS SURLESGRAPHES
∗∗Y. Colin de Verdi`ere
27 f´evrier 2006
∗ ”Randomwalksanddiscretepotentialtheory”(Cortona,22-28june1997),
Proceedings `a paraitre.
∗∗ Institut Fourier, Unit´e mixte de recherche CNRS-UJF 5582
BP 74, 38402-Saint Martin d’H`eres Cedex (France)
yves.colin-de-verdiere@ujf-grenoble.fr
Abstract
Dans cet expos´e de survol, nous commenc¸ons par pr´esenter des
ensembles naturels d’op´erateurs de type Schr¨odinger associ´es `a un
graphe fini.
Nous´etudions ensuiteles limites singuli`eres (au sens de laΓ−con-
vergence) de tels op´erateurs et montrons qu’elles sont associ´ees a` des
relations naturelles entre graphes (mineurs, transformation ´etoile-
triangle) ou `a des limites d’un int´erˆet ind´ependant (processus de
Markov (recuit simul´e), r´eseaux ´electriques).
Cela conduit `a introduire la notion de stabilit´e structurelle pour
une valeur propre multiple d’un op´erateur d’une famille en utilisant
la transversalit´e dans les espaces d’op´erateurs sym´etriques.
Les invariants num´eriques de graphes ainsi construits sont li´es `a
des probl`emes classiques de la combinatoire des graphes : planarit´e,
3genre, plongement non-nou´e dansR , largeur d’arbre.
Mots cl´es : graphes, op´erateurs de Schr¨odinger, mineurs, ´etoile-triangle,
arbres, limites singuli`eres
AMS Subject Classification : 05C10, 05C50, 35B25, 35J10.
11 Introduction
La th´eorie spectrale des op´erateurs diff´erentiels dont le prototype est le
laplacien sur une vari´et´e riemannienne compacte a connu un grand d´eve-
loppement durant les 30 derni`eres ann´ees. En particulier, l’asymptotique
des grandes valeurs propres, li´ee `a la dynamique classique (g´eod´esiques
p´eriodiques) a fait l’objet de nombreux travaux. Les propri´et´es purement
spectrales(i.e. nonasymptotiques,purementquantiques)pr´esentent´egalement
un grand int´erˆet ; il se trouve, ainsi que cette conf´erence le montre bien,
qu’un cadre, a priori plus simple, se prˆete bien `a l’´etude spectrale des
op´erateurs diff´erentiels : il s’agit de comprendre le spectre des op´erateurs
diff´erentiels de type laplacien ou Schr¨odinger sur les graphes. En retour, on
attend en particulier de nouveaux r´esultats pour le cas continu !!
Les ensembles d’op´erateurs consid´er´es dans la suite se rencontrent dans
de nombreux domaines des math´ematiques (discr´etisation par ´el´ements fi-
nis [8],[11], effet tunnel semi-classique [21], processus de Markov [12], limi-
tes de laplaciens de surfaces de Riemann `a courbure −1 lorsque certaines
g´eod´esiques ferm´ees simples ont des longueurs qui tendent vers 0 [9]) et
de la physique (supraconducteurs [35], physique quantique [30], spectres
mol´eculaires [24] ou mˆeme plus anciennement [29]).
A chaque graphe fini G = (V,E) (on pose n = |V|), on associe des
ensembles d’op´erateurs diff´erentiels auto-adjoints sur l’espace de Hilbert
V(de dimension finie) H =C muni du produit scalaireG
X
(f|g)= f(i)g¯(i) .
i∈V
Un op´erateur diff´erentiel sur G est un endomorphisme lin´eaire A de HGP
qui est local, c’est-`a-dire que Af(i) = a f(j) ou` les a sont nuls sii,j i,jj
{i,j} n’est pas une arˆete et i = j (on peut consid´erer qu’il y a des arˆetes
{i,i} pour chaquei∈V) ; autrement ditAf(i) ne d´epend que def(j) pour
j voisin de i.
Un op´erateur diff´erentiel A sur G est dit elliptique sia = 0 pour toutei,j
arˆete{i,j}, i =j.
A est dit auto-adjoint s’il l’est comme op´erateur sur H .G
M est l’ensemble de tous les op´erateurs elliptiques auto-adjoints surG
G ; on dira d’un´el´ement deM que c’est un op´erateur de Schr¨odinger avecG
champ magn´etique sur G. M est une sous-vari´et´e de dimension|V|+2|E|G
de l’espace des matrices hermitiennes V ×V.
O est le sous-ensemble de M form´e des matrices sym´etriques r´eellesG G
dont les coefficients a sont < 0 pour toute arˆete {i,j}. On dira d’uni,j
´el´ement de O que c’est un op´erateur de Schro¨dinger sur G. O est uneG G
sous-vari´et´e de dimension|V|+|E|deS(H ), l’espace des endomorphismesG
2
666sym´etriques de H .G
L est le sous-ensemble des A ∈ O tels que A1 = 0. Ce sont lesG G
laplaciens. L est de dimension |E|.G
Les laplaciens canoniques habituellement consid´er´es
X X
Δ f(i) = (f(i)−f(j)), Δ f(i) =− f(j) ,0 1
{i,j}∈E {i,j}∈E
sont des ´el´ements de O , et pour Δ de L . Le laplacienG 0 G
X1
Δ f(i) = (f(i)−f(j)) ,2
di
{i,j}∈E
n’est pas auto-adjoint pour la m´etrique canonique sur H sauf si le degr´eG P
2d du sommet i est constant. Il est auto-adjoint pour la m´etrique dxi i i
sur H . On peut le rendre auto-adjoint pour la m´etrique canonique par laG
1 −1√transformation (Ux) = x ; alors U Δ U est dans O .i i 2 Gdi
Des g´en´eralisations possibles de ces ensembles sont les suivantes :
a) on attribue `a chaque arˆete un signe ± et on impose le signe corre-
spondant aux a . Le lien avec les diagrammes de noeuds et les invariantsi,j
associ´es reste alors `a ´eclaircir : le graphe m´edial d’un diagramme de noeud
est de fac¸onnaturelle ungraphe planaire avec des signes± sur chaque arˆete
qui indique quel brin passe dessus ou dessous.
N Nb) On consid`ere le cas vectoriel, i.e. celui ou` H = ⊕ C . Celai∈VG
intervient aussi comme outil lorsque l’on consid`ere des produits de graphes.
c) Le cas des graphes infinis : on doit alors bien pr´eciser les conditions
de croissance des coefficients si possible de fac¸on `a avoir un spectre discret.
d) Dans le cas de M , il peut ˆetre utile de consid´erer des arˆetes doublesG
et, si {i,j} double, le coefficient a de A ∈ M peut ˆetre nul (a =i,j G i,j
a+(−a), a = 0).
Soit G = (V,E) donn´e. Le probl`eme de d´epart est le suivant :
´etant donn´e une suite λ ≤ ··· ≤ λ et un des 3 ensembles1 n
pr´ec´edents not´es de fac¸on g´en´erique Z , existe-t-il A∈Z dont leG G
spectre soit la suite pr´ec´edente ?
Je vais commenter ce programme :
1)Telquelleprobl`eme est malpos´e(outropdifficile), carnonmonotone
par rapport `a la complexit´e du graphe : la r´eponse est triviale pour un
graphe sans arˆete, car O = M est l’ensemble des matrices diagonalesG G
r´eelles, tout spectre est alors possible pour un op´erateur convenable de O .G
On sait par ailleurs que, si G est connexe et A∈ O la premi`ere valeurG
propre est de multiplicit´e 1 (Perron-Frobenius).
2) On va insister sur l’aspect ensemble d’op´erateurs : ce n’est pas tant
un op´erateur isol´e qui va nous int´eresser, mais la position relative de Z etG
3
6d’une vari´et´eW donn´ee par des conditions spectrales, par exemple λ =λ .2 3
Cela permet d’introduire des id´ees de transversalit´e et donc de gagner une
monotonie: toutcequ’on peut faireavec ungrapheG doitpouvoirˆetrefait
′avec tout graphe G plus complexe que G. On peut aussi rapprocher cela
de la th´eorie des discriminants (Arnold, Vassiliev), qui consiste `a regarder
les objets singuliers de l’ensemble consid´er´e, ici l’ensemble des op´erateurs
dont au moins une valeur propre est multiple.
3) Les arguments de transversalit´e permettent ainsi de construire des
nouveaux invariants des graphes qui sont reli´es `a la th´eorie classique des
graphes : plongements dans les surfaces, arbres, mineurs.
4) Un argument simple permet de montrer que toute suiteλ <···<λ1 n
de n nombres distincts est le spectre d’un A∈O :G
on consid`ere les applications
Φ :{u <u <···<u }→λ (ε)<···<λ (ε)ε 1 2 n 1 n
ou` les λ (ε) sont les valeurs propres (simples pour ε > 0 petit) de la formei
quadratique X X
2 2q = ux +ε (x −x ) .ε,u i i ji
{i,j}∈E
Pour ε = 0, Φ = Id et donc l’application du th´eor`eme des fonctions im-ε
plicites donne le r´esultat.
Le probl`eme se concentre donc sur les multiplicit´es.
On notera W la sous-vari´et´e de S(H) form´ee des op´erateurs A dont lel,k
spectre v´erifie :
···≤λ <λ =···=λ <λ ≤··· .k−1 k k+l−1 k+l
On note W =∪ W .l k l,k
ZOn note aussi m (G) le plus grand l tel que Z ∩W =∅.G l,kk
OPar exemple m (G) est le nombre de composantes connexes de G ;1
Om (G) est d´ej`a un invariant moins trivial (voir plus loin).2
Exemple 1.1 : les chemins.
Soit P le chemin a` n sommets {1,··· ,n} et les arˆetes {i,i+1}, 1 ≤n
i ≤ n− 1. Toutes les valeurs propres d’un op´erateur quelconque de MPn
sont simples, car un vecteur propre x est enti`erement d´etermin´e par x .1
Exemple 1.2 : les graphes cycliques.
Les sommets de ce graphe C sont les ´el´ements de Z/nZ et les arˆetesn
joignent i a` i±1 (mod n). On alors, pour tout A∈O ([21]) :Cn
λ <λ ≤λ <λ ≤λ <··· .1 2 3 4 5
4
6Listes de graphes vus plus loin :
P , C , K , E , K , S , T ,n(n+1)n n n n+1 3,3 2n−1
2
ou` l’indice d´esigne le nombre de sommets.
P5
K5
C9
K3,3
T15
S21
E5
Figure 1: graphes
2 Stabilit´e structurelle
2.1 Perturbations des valeurs propres multiples
Soit H un espace euclidien de dimension n et ε → A une applicationε
2C d’un voisinage de 0 `a valeurs dans S(H) l’espace des endomorphismes
sym´etriques de H.
5
Soit λ une valeur propre de A et E ⊂ H l’espace propre associ´e de0 0 0
dimension l.
SoitI un intervalle ferm´e de centre λ et tel queσ(A )∩I ={λ } ; alors0 0 0
pourε assez petit, I contient exactement l valeurs propres deA (compt´eesε
avec multiplicit´es) et not´ees :
λ (ε)≤···≤λ(ε) .1 l
dSoit B = A et q la forme quadratique sur E d´efinie parε B 0dε|ε=0
q (x) =<x|B|x> ,B
et μ ≤···≤μ le spectre de q .1 l B
Alors, on a [21] :
2∀i tel que 1≤i≤l, λ (ε) =λ +εμ +O(ε ) .i 0 i
λ λ0 0Soit W ={A∈S(H)| dimker(A−λ ) =l}, alors W est une sous-0l l
λ0vari´et´e de S(H) dont l’espace tangent T W est form´e des B∈S(H) telsA0 l
l(l+1)λ0que q = 0. En particulier, W est de codimension .B l 2
Notations :
λ λ λ0 0 0on note aussi W =∪ W , ou` A ∈ W si λ (A) < λ (A) =··· =k k−1 kl l,k l,k
λ0λ (A) (=λ )<···, et W =∪ W .k+l−1 0 l,k λ0 l,k
l(l+1)
W est de codimension −1.l,k 2
Pour l = 2, cette derni`ere codimension vaut 2 : l’observation que la
condition d’avoir une valeur propre double pour une matrice sym´etrique
r´eelleestdecodimension2remonteauxann´ees1930(Wigner-VonNeumann
[41], voir aussi [1], [3]). Donc, si t → A est un chemin g´en´erique danst
S(H), il n’y aura de valeurs propres multiples pour A pour aucun t. Ont
aura typiquement une ´evolution des valeurs propres faisant apparaitre des
croisements ´evit´es.
SoitmaintenantΦ : (u,v)→A unefamille`a2param`etresdematricesu,v
sym´etriques. Supposons que Φ coupe tranversalement W en (u ,v ) ; on2,k 0 0
a donc, en notant A =A , le spectre de A qui v´erifie0 u ,v 00 0
···≤λ <λ =λ <··· ,k−1 k k+1
et le graphe simultan´e de λ et λ a l’allure d’un cˆone.k k+1
Soit γ un lacet du plan des (u,v) qui entoure (u ,v ) sans entourer0 0
d’autres points (u,v) avec A ∈W , soit φ (t) un vecteur propre deAu,v 2,k k γ(t)
correspondant `a la valeur propre simple λ (A ) suppos´e r´eel et de normek γ(t)
1 et que l’on peut donc suivre par continuit´e autour de γ ; lorsqu’on fait un
tour, φ (t) se transforme en−φ (t). Le fibr´e r´eel de dimension 1 donn´e park k
l’espace propre ker(A −λ (t)) est donc non trivial (ruban de M¨obius).γ(t) k
6λ ≤λk k+1
λ
v
v0
γ t
u
u0
Figure 2: point diabolo
Ce fait peut ˆetre mise `a profit pour d´etecter des valeurs propres multiples
dans une famille d’op´erateurs d´ependant de 2 param`etres. Voir [6]. La
transversalit´e joueun grand rˆoleici : sans elle, la monodromiepourraitˆetre
triviale !! C’est cette situation que nous allons g´en´eraliser maintenant.
Le cas hermitien complexe peut ˆetre trait´e de fac¸on analogue. Il faut
l(l+1) 2alors remplacer par l , la dimension de l’espace des matrices hermiti-
2
ennes l×l. La vari´et´eW est alors de codimension 3 et l’argument avec le2,k
lacet γ doit ˆetre remplac´e par un argument avec une petite sph`ere plong´ee.
Le fibr´e associ´e `a une valeur propre simple est alors un fibr´e de rang 1 com-
plexe dont la classe de Chern est 1 si la sph`ere entoure exactement un point
de W . Voir [13] .2
2.2 Stabilit´e structurelle des valeurs propres
On est ainsi conduit `a donner une d´efinition g´en´erale de la stabilit´e struc-
turelle d’une valeur propre relativement `a une vari´et´e Z d’op´erateurs.
D´efinition 1 Soit A ∈ Z ⊂ S(H), ou` Z est une sous-vari´et´e. Sup-
posons que A ∈ Z ∩ W . On dit que la valeur propre λ de A estG l,k k
Z−structurellement stable si W et Z se coupent transversalement en A.l,k
Autrement dit, l’apparition d’une valeur propre de multiplicit´e l dans Z est
un ph´enom`ene stable par perturbation de Z.
On peut tester de fac¸on purement alg´ebrique cette condition de stabilit´e
si on connait l’espace propre :
si Φ : T Z → S(E ) (ou` E est l’espace propre de A consid´er´e) estA 0 0
donn´ee par
Φ(B)(x) =<x|B|x> ,
7
la condition de stabilit´e structurelle ´equivaut `a la surjectivit´e de Φ.
2.3 Exemples
Exemple 2.1 Si Z = O , la premi`ere valeur propre λ n’est stable que siG 1
elle est de multiplicit´e 1.
Exemple 2.2 Soit E l’´etoile a` N branches, A∈ O ou` −A est la ma-N EN
trice d’adjacence. La 2`eme valeur propre de A est de multiplicit´e N −1 et
n’est stable que si N ≤ 3.
Exemple 2.3 : graphes complets. Il s’agit des graphes K dont touten
paire de sommets est connect´ee par une arˆete. Si A est le laplacien canon-
ique, la seconde valeur propre est de multiplicit´e n− 1 et O −stable etKn
mˆeme L −stable.Kn
Exemple 2.4 : graphe de Kuratowski. Il s’agit du graphe not´e K3,3
dont l’ensemble des sommets est V ∪V (union disjointe), avec|V| = 3, et1 2 i
les 9 arˆetes joignent les sommets de V `a ceux de V .1 2
Si A = Δ est le laplacien canonique, son spectre est0
0< 3 = 3 =···= 3< 6 ,
et la valeur propre 3 de multiplicit´e 4 est O −stable.K3,3
Exemple 2.5 : cas complexe. Dans le cas hermitien complexe (A ∈
M ), le th´eor`eme de Perron-Frobenius ne s’applique pas et on peut regarderG
la stabilit´e de λ .1
Soit d’abord S le graphe planaire form´e de n−1 triangles recoll´es en2n−1
une chaine tel que chacun a un sommet commmun avec le suivant. Soit A
tel que la forme quadratique associ´ee est
X
2q(x) = |x +x +x | ,i j k
ou` la somme porte sur les triangles{i,j,k}. On voit facilement que kerA =
−1q (0) est de dimension n et n’est pas M −stable.G
SoitensuiteT legrapheform´eensubdivisantuntriangle´equilat´eraln(n+1)/2
en petits triangles ´equilat´eraux grˆace a` une subdivision des cˆot´es du triangle
initial en n−1 intervalles ´egaux. Colorions en noir ou en blanc les petits
triangles suivant qu’ils pointent vers le haut ou le bas. La mˆeme recette
que pr´ec´edemment, en sommant sur les triangles noirs, donne lieu `a un
fondamental de multiplicit´e n qui est M −stable.G
8Z2.4 Les invariants μ (G)k
On d´efinit maintenant une famille d’invariants num´eriques d’un graphe G
Zgrˆace `a une version stabilis´ee de m (G).k
D´efinition 2 Si Z est un des 3 ensembles d’op´erateurs M , O , LG G G G
d´efinis plus haut, on d´efinit
Zμ (G)k
comme le sup des entiers l tels qu’il existe A ∈ Z avec ··· < λ = ··· =G k
λ <··· et λ (A) est Z −stable.k+l−1 k G
OExemple 2.6 Pour tout G, μ (G) = 1.1
OExemple 2.7 μ (K ) =n−1.n2
MExemple 2.8 μ (T ) =n.n(n+1)/22
OExemple 2.9 μ (K ) = 4.3,32
O OExemple 2.10 μ (E ) = 2 et, pour N ≥ 2, μ (E ) = 2.3 N2 2
OExemple 2.11 μ (C ) = 1 si k est impair et 2 si k est pair.nk
3 Mineurs des graphes et limites singuli`eres
d’op´erateurs
3.1 Monotonie par mineurs
Lapropri´et´eprincipaledesinvariantsintroduitspr´ec´edemment est lamono-
tonie par mineur.
D´efinition 3 Un graphe G = (V ,E ) est dit mineur de G = (V ,E ) si1 1 1 2 2 2
G peut ˆetre construit `a partir de G de la fa¸con suivante : si1 2
V =∪ W2 α∈B α
est une partition deV en sous-ensembles connexes,V est un sous-ensemble2 1
de B et E v´erifie la condition suivante :1
{α,β}∈E implique qu’il existe i∈W , j ∈W tels que {i,j}∈E .1 α β 2
On peut aussi dire que G est un mineur de G si on passe de G `a G1 2 2 1
par une suite finie des op´erations ´el´ementaires suivantes : ˆoter une arˆete,
contracter une arˆete, ˆoter un sommet isol´e.
On a alors le :
9W W1 4
W3
W5
1
4
W2
3
2
Figure 3: mineurs
Th´eor`eme 1 Pour chaque ensemble Z = M,O, si G est un mineur de1
G :2
Z Zμ (G )≤μ (G ) .1 2k k
Pour montrer ce th´eor`eme, ilsuffit delemontrer dansles cas particuliers
ou` l’on ˆote ou contracte une arˆete de G .1
Le cas ou` l’on ˆote une arˆete est simple, car H =H . On utilise alorsG G1 2
1la conservation d’une intersection transversale par perturbation C .
Donnons l’argument plus pr´ecis dans le cas de O . Soit H l’espace deG
Hilbert consid´er´e et supposons que l’on a num´erot´e les sommets de G de2
fac¸on que G s’obtienne en ˆotant l’arˆete {1,2} de G . Soit Z = O +1 2 ε G1
2ε(x −x ) (ou` on a ´ecrit les op´erateurs comme des formes quadratiques),1 2
alors Z ⊂O pour ε> 0.ε G2
On conclut ainsi : si Z = O et W se coupent transversalement en0 G l,λ1
A, il en est de mˆeme pour Z et W en A et donc de O et W en A .ε l,λ ε G l,λ ε2
Il reste `a v´erifier que le num´ero de la valeur propre λ ne change pas.
Lecasou`l’oncontractel’arˆete{1,2}estplusd´elicat,cariln’estplusvrai
que H = H ; on a seulement une inclusion H ⊂ H en identifiantG G G G1 2 1 2
V2H au sous-espace de C dont les ´el´ements sont les vecteurs x tels queG1
x =x .1 2
10