SPECTRE D'OPERATEURS DIFFERENTIELS SUR LES GRAPHES

De
Publié par

SPECTRE D'OPERATEURS DIFFERENTIELS SUR LES GRAPHES? Y. Colin de Verdiere?? 27 fevrier 2006 ? ”Random walks and discrete potential theory” (Cortona, 22-28 june 1997), Proceedings a paraitre. ?? Institut Fourier, Unite mixte de recherche CNRS-UJF 5582 BP 74, 38402-Saint Martin d'Heres Cedex (France) Abstract Dans cet expose de survol, nous commenc¸ons par presenter des ensembles naturels d'operateurs de type Schrodinger associes a un graphe fini. Nous etudions ensuite les limites singulieres (au sens de la ??con- vergence) de tels operateurs et montrons qu'elles sont associees a des relations naturelles entre graphes (mineurs, transformation etoile- triangle) ou a des limites d'un interet independant (processus de Markov (recuit simule), reseaux electriques). Cela conduit a introduire la notion de stabilite structurelle pour une valeur propre multiple d'un operateur d'une famille en utilisant la transversalite dans les espaces d'operateurs symetriques. Les invariants numeriques de graphes ainsi construits sont lies a des problemes classiques de la combinatoire des graphes : planarite, genre, plongement non-noue dans R3, largeur d'arbre. Mots cles : graphes, operateurs de Schrodinger, mineurs, etoile-triangle, arbres, limites singulieres AMS Subject Classification : 05C10, 05C50, 35B25, 35J10.

  • operateurs elliptiques

  • auto-adjoints sur l'espace de hilbert

  • idees de transversalite

  • dit auto-adjoint

  • auto-adjoint pour la metrique canonique par la transformation

  • auto-adjoint pour la metrique canonique sur hg sauf


Publié le : mercredi 1 février 2006
Lecture(s) : 26
Source : www-fourier.ujf-grenoble.fr
Nombre de pages : 27
Voir plus Voir moins

´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

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.