\documentclass[XUPS,XML,SOM,Unicode,francais,NoFloatCountersInSection]{cedram} \setcounter{tocdepth}{2} \usepackage{xups04-02} \graphicspath{{xups04-02_figures/}} \begin{document} \frontmatter \title[Opérateurs de type Schrödinger sur les graphes] {Sur le spectre des opérateurs de~type~Schrödinger sur les graphes} \author[\initial{Y.} \lastname{Colin de Verdière}]{\firstname{Yves} \lastname{Colin de Verdière}} \address{Institut Fourier, UMR 5582 du CNRS, Université de Grenoble I, BP 74, 38402 Saint-Martin d'Hères, France} \email{yves.colin-de-verdiere@ujf-grenoble.fr} \urladdr{http://www-fourier.ujf-grenoble.fr/~ycolver/} \thanks{Journées X-UPS 2004. Graphes. Éditions de l'École polytechnique, 2004} \maketitle \vspace*{-.5\baselineskip} \tableofcontents \mainmatter \Changel \section*{Introduction} Il y a un analogue naturel sur les graphes des opérateurs de Schrödinger qui gouvernent la mécanique quantique: ce sont certaines endomorphismes symétriques de $\R^ V$ où $V$ est l'ensemble des sommets du graphe fini $G$. On notera $O_G$ l'ensemble de ces opérateurs de \og type Schrödinger\fg sur $G$. On écrira sous la forme \[ \gl_1 \leq \gl_2 \leq \cdots \leq \gl_{|V|} \] les valeurs propres de $A\in O_G$ répétées suivant leur multiplicité. Si $A \in O_G$, $A$ admet beaucoup de propriétés communes avec les opérateurs de Schrödinger. Après avoir motivé et introduit cette classe d'opérateurs, je montrerai des propriétés de leurs spectres pour des graphes simples (cycles, graphes linéaires, arbres,...) ainsi que quelques propriétés générales. Je décrirai ensuite des résultats plus récents concernant la topologie différentielle de $O_G$ relativement à la stratification naturelle des matrices symétriques en termes de leurs propriétés spectrales. Cette étude permet d'introduire un invariant numérique entier $\mu (G)$ qui reflète la \og complexité spectrale du graphe\fg: $\mu(G)$ est la multiplicité maximale de la seconde valeur propre d'un $A\in O_G$ satisfaisant une propriété naturelle de \emph{stabilité structurelle}. Je montrerai en particulier que l'inégalité $\mu(G) \leq 3$ caractérise les graphes planaires. Comme référence générale, on pourra consulter mon livre \og Spec\-tres de graphes\fg publié par la SMF \cite{CV8}. Je n'aurai pas le temps de donner des démonstrations détaillées des résultats principaux (théorèmes \ref{theo:mineur} et \ref{theo:planaire}). Je donnerai les définitions qui permettent de donner un sens précis aux énoncés de ceux-ci. Les idées essentielles des méthodes utilisées sont contenues dans deux points que j'expliquerai: \begin{itemize} \item Comment la topologie intervient grâce à la caractérisation variationnelle des valeurs propres d'un endomorphisme symétrique (le \emph{minimax}): je déduirai de cette caractérisation le théorème de Perron-Frobenius et un cas particulier du théorème nodal de Courant. \item Comment faire vivre ensemble les opérateurs associés à des graphes distincts. J'introduirai à cet effet des opérateurs symétriques non partout définis et leur convergence au sens des graphes: la $\Gamma$-convergence. \end{itemize} Comme vous le verrez, il y a aussi une mine d'exercices d'algèbre linéaire! \smallskip \begin{small}\renewcommand{\baselinestretch}{.95}\normalfont \emph{J'ai découvert les théorèmes \ref{theo:mineur} et \ref{theo:planaire}, en essayant de comprendre le théorème de Cheng (Théorème \ref{theo:cheng}) et son éventuelle extension à la dimension $3$. Ce théorème était énoncé dans le contexte des équations aux dérivées partielles et de la géométrie différentielle. Il m'a fallu de nombreuses années et des rencontres opportunes pour découvrir que la théorie des graphes était le cadre naturel pour l'étude de ces problèmes. J'ai eu la chance de bénéficier à Grenoble de la disponibilité des collègues de théorie des graphes, en particulier de François Jaeger (1947--1997), qui m'ont aidé à découvrir ce sujet loin de ma culture de base... C'est une des choses que je trouve fascinantes en mathématiques que ces liens imprévus entre des domaines a priori très lointains!} \end{small} \section{Complexité d'un graphe et mineurs} \subsection{Notations} Les graphes considérés dans ces exposés sont des graphes finis. Si $G$ est un tel graphe, on note $V$ l'ensemble fini de ses sommets et $E$ l'ensemble de ses arêtes; une arête est un ensemble $\{i, j\} $ de deux sommets distincts de $G$. \emph{Les graphes considérés sont donc finis, sans boucles, ni arêtes multiples, et non orientés.} On notera ainsi $G=(V,E)$. On s'intéressera à des opérateurs liné\-aires symé\-triques de $\R^V $ dans lui-même. Il sera pratique de voir les \hbox{éléments} de $\R^V$ comme des fonctions $\vec{x}: V \to\R $. Si $\vec{x} \in \R^V$ et $i \in V$, on \hbox{notera} souvent $\vec{x}(i)$ la composante d'indice $i$ de $\vec{x}$. Il sera aussi très utile d'identifier les endomorphismes symétriques d'un espace euclidien à des formes quadratiques sur cet espace. Si $A$ est un tel endomorphisme, on posera souvent $q_A(\vec{x})=\ $ où $\<\cbbullet\mid \cbbullet\>$ est le produit euclidien. \subsection{Espace topologique associé à un graphe} Soit $G=(V,E)$ un graphe fini. Soit $e_i$, $i \in V$, la base canonique de $\R^V$. Soit $X_G$ le compact de $\R^V$ qui est la réunion des segments $[e_i, e_j]$ où $\{i, j\}$ est une arête de $G$. Notons que les segments $[e_i, e_j]$ ne se rencontrent (éventuellement) qu'en leurs extrémités. $X_G$ est l'\emph{espace topologique} associé à $G$. \subsection{Connexité} Un graphe $G=(V;E)$ est dit \emph{connexe} si deux sommets $i,j$ quelconques peuvent être joints par un chemin, \ie une suite $i_0=i, i_1, \dots, i_{k-1}, i_k=j $ de sommets de $G$ telle que, pour tout entier $l$ tel que $ 0\leq l \leq k-1$, on ait $ \{i_l, i_{l+1}\} \in E $. Il revient au même de dire que l'espace topologique $X_G$ est connexe. Si $V_1 \subset V$, $V_1$ est dit connexe si le graphe $G_1$ dont les sommets sont ceux de $V_1$ et les arêtes celles de $G$ qui joignent deux sommets de $V_1$ est connexe. \subsection{Complexités} Il existe beaucoup de façons de mesurer la \emph{complexité} d'un graphe, par exemple: \begin{itemize} \item nombre de sommets $+$ nombre d'arêtes, \item genre, \item largeur d'arbre, \item nombre chromatique. \end{itemize} Toutes ne sont pas équivalentes, mais il est souhaitable que la complexité soit monotone vis-à-vis de la relation de mineurs: \begin{defi} Un graphe $G_1=(V_1,E_1)$ est dit \emph{mineur} de $G_2=(V_2,E_2)$ si $G_1$ peut être construit à partir de $G_2$ de la fa{ç}on suivante: si $$ V_2=\bigcup_{\alpha \in B} W_\alpha $$ est une partition de $V_2$ en sous-ensembles connexes, $V_1$ est un sous-ensemble de $B$ et $E_1$ vérifie la condition suivante: $$ \{\alpha , \beta\} \!\in\! E_1 \hbox{~implique~qu'il~existe~} i\!\in\! W_\alpha,~j\!\in\! W_\beta~\hbox{tels~que~}\{i,j\}\!\in\! E_2.$$ On note $G_1 \leq G_2$ la propriété \og $G_1$ est un mineur de $G_2$\fg. \end{defi} \begin{figure}[htb] \begin{center} \includegraphics[scale=.7]{xups04-02_fig1} \caption{Mineurs} \label{fig: mineurs} \end{center} \end{figure} On peut montrer que $G_1$ est un mineur de $G_2$ si on passe de $G_2$ à~$G_1$ par une suite finie des opérations élémentaires suivantes: \begin{itemize} \item Ôter une arête \item Contracter une arête, \ie identifier deux sommets voisins de $G_2$ à un seul sommet de $G_1$ et supprimer l'arête qui les joignait et qui n'a plus de sens \item Ôter un sommet isolé. \end{itemize} On vérifie sans difficulté que la relation $G\leq G'$ est une relation d'ordre sur l'ensemble des graphes. Une notion de complexité raisonnable se doit d'être croissante pour cette relation d'ordre. Le genre et la largeur d'arbre sont croissants pour la relation de mineurs. Le nombre chromatique ne l'est pas: tout graphe est mineur d'un graphe dont le nombre chromatique vaut $2$ (exercice). \subsection{Mineurs et topologie de Hausdorff-Gromov} Une remar\-que clé dans la suite est que la relation de mineur peut être lue de façon purement topologique au lieu de l'être de façon purement combinatoire. On le verra au moyen des opérateurs de Schrödinger, on peut le voir directement avec la topologie de Hausdorff-Gromov. Hausdorff a défini une distance $d_H$ entre les compacts d'un espace métrique $(X,d)$: \[ d_H (K_1, K_2)=\max \Bigl(\max_{x \in K_1} \min_{y\in K_2} d(x,y), \max_{x \in K_2} \min_{y \in K_1} d(x,y) \Bigr);\] autrement dit, $d_H (K_1, K_2) \leq \ge $ équivaut à: \begin{gather*} \forall x \in K_1,~ \exists y \in K_2,~d(x,y)\leq \ge \\ \tag*{et} \forall x \in K_2,~ \exists y \in K_1,~d(x,y)\leq \ge. \end{gather*} Gromov (\cite{Gro} chap.\,3) a défini, à partir de la distance de Hausdorff, une distance $\gd_{\rm Gro}$ entre deux espaces métriques compacts $(X,d)$ et $(X',d')$: \[ \gd_{\rm Gro} \left((X,d),(X',d')\right) = \inf_{\substack{j:X\to Y\\j':X' \to Y}} d_H (j(X), j'(X')),\] où $Y$ est un espace métrique et $j$ (\resp $j'$) est une isométrie injective de $(X,d)$ (\resp $(X',d')$) dans $Y$. Si $G$ est un graphe connexe, à tout ensemble de poids $p= (p_{i,j}) \in ] 0, +\infty [^E $ on associe une distance $d_p$ sur $V$: on identifie chaque arête à un segment de longueur $p_{i,j}$ et la distance $d_p (i,j)$ est la longueur du plus court chemin de $i$ à $j$. On pose $d_p (i,j)=+\infty $ si $i$ et $j$ sont dans deux composantes connexes différentes de $G$. Un exemple est le réseau du métro parisien et $p_{i,j}$ est le temps de parcours entre les deux stations $i$ et $j$. La distance $d_p(i,j)$ représente alors le temps minimal entre les stations $i$ et $j$ (sans tenir compte des changements!). \begin{rem} \label{rem:inj} Cependant, si $G$ est donné, l'application $F_G $ qui, au poids $p$, associe l'espace métrique $(V, d_p)$ n'est pas injective (pourquoi?). \end{rem} On a cependant le: \begin{theo} Pour tout mineur $G'=(V',E')$ de $G=(V,E)$, $V'$ muni d'une distance $d_{p'}$ est la limite au sens de Gromov d'une suite $(V, d_{p_n})$. Réciproquement, si $(V, d_{p_n})$ converge vers un espace métrique, celui-ci est donné par un mineur de $G$. \end{theo} L'idée de la démonstration est de prendre des $p_{i,j}$ qui valent $\ge$ sur les arêtes contractées et $\ge^{-1}$ sur les arêtes ôtées. Pour la réciproque, on compactifie en prenant $p \in K:=[ 0, +\infty ]^E $. On définit alors une application continue surjective $\Phi:K \to{\cal M} $ où ${\cal M}$ est l'ensemble des espaces métriques associés à des graphes qui sont des mineurs de $G$. $\Phi (p) $ est obtenu en prenant le mineur de $G$ défini suivant la règle précédente: contracter les arêtes de poids $0$ et ôter celles de poids $\infty $, puis associer à toute arête du mineur $G'$ le poids donné par le minimum des poids des arêtes de $G$ correspondante. La relation de mineur devient alors une relation topologique: à chaque mineur $G'$ de $G$ est associé un sous-ensemble ${\cal M}_{G'} $ de ${\cal M}$. $G''$ est mineur de $G'$ si ${\cal M}_{G''} $ est contenu dans l'adhérence de ${\cal M}_{G'} $. Dans ce qui suit, j'introduis une version plus sophistiquée de la construction précédente qui ne présente pas le défaut d'injectivité de la remarque \ref{rem:inj} et permet vraiment de voir la relation de mineur comme une relation topologique, et même différentielle (stratification). \Subsection{Genre} \begin{defi} Le \emph{genre} ${\rm g}(G)$ est le plus petit entier $ k$ tel que l'espace topologique $X_G$ se plonge continûment dans la surface orientable de genre $k$ (une sphère avec $k$ anses). Un graphe est \emph{planaire} si et seulement si il est de genre $0$. \end{defi} \begin{exo} Montrer la majoration \[ {\rm g}(G) \leq \frac{|E|(|E|-1))}{2}. \] \end{exo} On aura besoin plus tard du fameux théorème de Kuratowski \cite{KI}: \begin{theo} \label{theo:kura} Un graphe $G$ est planaire si et seulement si il n'admet comme mineur ni le graphe complet à cinq sommets $K_5$, ni le graphe de Kuratowski $K_{3,3}$ (voir la définition dans l'exemple \ref{ex:kura}). \end{theo} Une telle caractérisation s'appelle \emph{caractérisation par mineurs exclus.} La relation d'ordre des mineurs satisfait le (difficile) théorème de finitude suivant prouvé par Robertson et Seymour: \begin{theo} Soit ${\cal E}$ un ensemble de graphes tel que, si $G'\leq G $ et $G\in {\cal E} $, alors $G'\in {\cal E} $. Il existe une caractérisation des graphes de ${\cal E}$ par exclusion comme mineurs d'un ensemble \emph{fini} de graphes $G_1,\dots ,G_N$: \[ (G\in {\cal E}) \ssi (\forall i=1,\dots, N,~ G_i \text{~n'est~pas~un~mineur~de~} G). \] \end{theo} Par exemple, si $X$ est une surface, on peut prendre pour ${\cal E}_X$ l'ensemble des graphes qui se plongent dans $X$ (pourquoi?). L'entier $N$ croît alors très vite avec la topologie de $X$. Par exemple, $N=103$ pour le plan projectif! \Subsection{Largeur d'arbre} \begin{defi} La \emph{largeur d'arbre} $\lar(G)$ est le plus petit $k$ tel que $G$ est mineur de $T \times K$ où $T$ est un arbre et $K$ un graphe à $k$ sommets. \end{defi} Par exemple, $\lar(G)=1$ si et seulement si $G$ est une forêt (réunion disjointe d'arbres). La largeur d'arbre du graphe $P_p \times P_q $ où $P_l$ est le chemin à $l$ sommets (voir exemple \ref{ex:path}) est à peu près $\min (p,q)$. La largeur d'arbre n'est donc pas contrôlée par le genre. \subsection{Nombres chromatiques} Le problème du coloriage d'une carte peut être posé ainsi: on considère une carte représentant un certain nombre de pays supposés \emph{connexes}. On veut attribuer une couleur à chaque pays de façon que deux pays qui ont une frontière commune soient de couleurs différentes. Si on considère le graphe~$G$ dont les sommets sont ces pays et ayant une arête entre deux pays si et seulement s'ils ont une frontière commune, le problème de coloriage se lit sur le graphe $G$. On pose alors la: \begin{figure}[htb] \begin{center} \includegraphics[scale=.7]{xups04-02_fig2} \caption{Une carte, le graphe associé et un coloriage minimal} \label{fig:color} \end{center} \end{figure} \begin{defi} Le \emph{nombre chromatique} $\chi (G)$ du graphe $G$ est le nombre minimum de couleurs nécessaires pour colorier les sommets d'un graphe de fa{ç}on que deux sommets voisins quelconques soient de couleurs différentes. Le \emph{nombre chromatique $\chi (X)$ d'un espace topologique $X$} est le sup des nombres chromatiques des graphes plongés dans $X$. \end{defi} On a le résultat non trivial suivant (\cf \cite{RI}): \begin{theo} Si $X$ est une surface compacte, \[ \chi (X)= \max \{n\mid K_n \text{~se~plonge~dans~} X\} ,\] où $K_n$ est le graphe complet à $n$ sommets. \end{theo} Si $X=S^2$, c'est le fameux \emph{théorème des quatre couleurs} (voir \cite{A-H} et aussi une preuve indépendante dans \cite{RSST}) dont on ne connaît pas de preuves évitant l'usage de calculs par ordinateurs! Les autres cas sont plus simples. On a une formule explicite en fonction de la caractéristique d'Euler $e(X)$ de la surface: si $X$ n'est pas la bouteille de Klein $K_2$ \[ \chi (X)={\rm Int}\biggl(\frac{7+\sqrt{49-24e (X)}}{2}\biggr), \] (${\rm Int}(t)$ est la partie entière du réel $t$) et $\chi (K_2)=6$. \begin{exo} Si $X= \R^3$ ou si $X$ est la surface \emph{singulière} obtenue comme produit d'un $Y$ par un intervalle, $\chi (X)= +\infty $. \end{exo} \subsection{Complexité spectrale} C'est notre sujet aujourd'hui. On va introduire un invariant numérique $\mu(G)$ attaché à un graphe qu'on pourrait appeler \emph{complexité spectrale de $G$}. La définition de $\mu(G)$ utilise de la topologie différentielle et on a les deux principaux résultats suivants: \begin{theo} \label{theo:mineur} L'invariant $\mu$ est monotone pour la relation de mineurs: si $G \leq G'$, $\mu(G) \leq \mu(G') $. \end{theo} \begin{theo} \label{theo:planaire} Le graphe $G$ est planaire si et seulement si \hbox{$\mu(G)\!\leq\! 3$}. \end{theo} Le résultat central dont tout découle est le théorème \ref{theo:mineur}. Un des problèmes les plus excitants est de relier $\mu (G)$ au nombre chromatique de $G$. J'ai fait la conjecture suivante: \begin{conj} \label{conj:super} Pour tout graphe $G$, on a: $$ \chi (G) \leq \mu (G)+1.$$ \end{conj} Le théorème des quatre couleurs est une conséquence (via le théorème \ref{theo:planaire}) de cette conjecture. \section{Opérateurs de type Schrödinger sur les graphes} Si on considère une particule de masse $m$ soumise à un potentiel $V:\R^d \to\R $, sa trajectoire classique est gouvernée par les équations de Newton $m {\vec{x}}^{\,\prime\prime}= -\grad V(\vec{x})$. Dans la mécanique quantique, la particule a une fonction d'onde $u: \R^d \to\C$ qui obéit à l'équation de Schrödinger \begin{equation} \label{schro} i \hbar \frac{du}{dt}= -\frac{\hbar^2}{2m} \Delta u + Vu=: \hat{H}u , \end{equation} où $\hbar $ est la constante de Planck et $\Delta = \sum_{j=1}^d \sfrac{\pa^2}{\pa x_j^2}$ est le laplacien. On étudie souvent la version stationnaire de l'équation de Schrödinger \begin{equation} \label{stat} \hat{H}u=Eu \end{equation} qui est une équation aux valeurs propres car, dans les bons cas (par exemple, si $\lim_{\vec{x}\to\infty} V(\vec{x})=+\infty $), toute solution de (\ref{schro}) est superposition de solutions stationnaires $u(\vec{x},t)=\exp(-it E/\hbar) u (\vec{x},0)$. Les $E$ pour lesquels (\ref{stat}) a une solution $L^2$ non triviale forment le spectre de la particule et sont souvent détectables expérimentalement. On~parle ainsi du spectre d'un atome ou d'une molécule. Quelles sont les caractéristiques claires des opérateurs différentiels~$\hat{H}$? Ces opérateurs sont \begin{itemize} \item symétriques: $\int_{\R^d} (\hat{H}u) v \,|dx|= \int_{\R^d} u (\hat{H} v)\,|dx|$ pour tout couple $u,v$ de fonctions d'ondes $C^\infty $ à supports compacts; \item locaux: $\hat{H}u (\vec{x}) $ ne dépend que de $u $ dans un voisinage aussi petit qu'on veut de $\vec{x}$; \item positifs: la partie différentielle de $\hat{H}$, le laplacien, vérifie \[ \int_{\R^d} (-\Delta u) u \,|dx| = \int_{\R^d} \| \grad u \|^2\, |dx| \geq 0.\] \end{itemize} On va préserver ces trois propriétés dans le cas des graphes. Il n'est pas étonnant que l'on retrouve fréquemment ces propriétés dans des réductions à la dimension finie des opérateurs de Schrödinger. Les opérateurs considérés dans la suite se rencontrent dans de nombreux domaines des mathématiques (discrétisation par éléments finis, processus de Markov, limites de laplaciens de surfaces de Riemann à courbure $-1$ lorsque certaines géodésiques fermées simples ont des longueurs qui tendent vers $0$) et de la physique (système de pendules couplés, effet tunnel semi-classique, supraconducteurs, physique quantique, spectres moléculaires). À chaque graphe fini $G=(V,E)$, on associe un \emph{ensemble} d'opérateurs différentiels symétriques sur l'espace euclidien ${\cal E}_G= \R^V $ muni du produit scalaire canonique $$ (\vec{x}\mid \vec{y})=\sum_{i\in V}\vec{x}(i)\,\vec{y}(i).$$ Un \emph{opérateur différentiel} sur $G$ est un endomorphisme linéaire $A$ de ${\cal E}_G $ qui est \emph{local}, c'est-à-dire que $A\vec{x}(i)=\sum_j a_{i,j}\vec{x}(j)$ où les $a_{i,j}$ sont nuls si $\{i,j\}$ n'est pas une arête et $i\ne j $ (on peut considérer qu'il y a des arêtes $\{i,i\}$ pour chaque $i\in V $); autrement dit $A\vec{x}(i)$ ne dépend que de $\vec{x}(j)$ pour $j$ voisin de $i$. Un opérateur différentiel $A$ sur $G$ est dit \emph{elliptique} si $a_{i,j}\ne 0$ pour toute arête $\{i, j\}$. \begin{defi}[Les opérateurs de type Schrödinger] Un opérateur de type Schrödinger sur $G$ est un opérateur linéaire $A: \R^V \to\R^V$, de matrice $A=(a_{i,j}) $, sur $G$ dont les coefficients $a_{i,j}$ satisfont: \begin{itemize} \item si $\{i, j\} \in E$, $a_{i,j}<0$, \item si $\{i, j\} \notin E$ et $i\ne j$, $a_{i,j}=0$ ($A$ est un \emph{opérateur différentiel} sur~$G$), \item $A$ est symétrique \end{itemize} On notera $O_G$ l'ensemble de ces opérateurs lorsque le graphe $G$ est donné. \end{defi} L'ensemble $O_G $ est une sous-variété de dimension $\vert V \vert + \vert E \vert $ de ${\cal S}({\cal E}_G)$, l'espace des endomorphismes symétriques de ${\cal E}_G $. \begin{exem} La matrice d'adjacence d'un graphe $G$ est la matrice symétrique $\Ad_G=(a_{i,j})$ telle que $a_{i,j}=1$ si $\{i, j\} \in E(G)$ et $a_{i,j}=0$ sinon. Il est clair que $-\Ad_G $ est dans $ O_G$ ainsi que le laplacien $\Delta_G= \diag(\valence(i))-\Ad_G $. \end{exem} \begin{exem}[Pendules couplés] Je me souviens avoir vu de tels systèmes mécaniques autrefois au Palais de la découverte à Paris! On~con\-sidère un système de $n$ pendules de masse $m_i >0$ dans un potentiel \[ V(\vec{x})=\ha \sum_{i=1}^n v_i \vec{x}(i)^2 +\ha \sum_{\{i, j\} \in E} c_{i,j}\left(\vec{x}(i)-\vec{x}(j) \right)^2 ,\] où les $v_i$ et les $c_{i,j}$ sont $>0$. $E$ est l'ensemble des arêtes d'un graphe tel que $V =\{1,\dots, n\}$. Les $c_{i,j}$ représentent le couplage du pendule~$i$ avec le pendule $j$. Les équations de Newton: \[ m_i x''_i = -\frac{\pa V}{\pa x_i} \] s'écrivent $ {\vec{y}}^{\,\prime\prime}=-A \vec{y} $ où $M=\diag (m_i)$, $\vec{y}=M^{\sha} \vec{x} $ et $A\in O_G $ est la matrice $>0$ (pourquoi?) donnée par \[ A =M^{-\sha} \left( \begin{array}{cccc}v_1+ \sum c_{1,j}&-c_{1,2}&\cdots & - c_{1,n}\\ -c_{1,2}& \cdots & \cdots & \cdots \\ \cdots & \cdots & \cdots & \cdots \\ -c_{1,n}& \cdots & \cdots & \cdots \end{array}\right) M^{-\sha}.\] Les fréquences des oscillations propres sont les $\go_j =\sqrt{\gl_j}$ où les $\gl_j$ sont les valeurs propres de $A$. \end{exem} Soit $G=(V,E)$ donné. Le problème de départ est le suivant: \noindent \emph{Étant donné une suite $\lambda_1 \leq \cdots \leq \lambda_{|V|} $, existe-t-il $ A\in O_G$ dont le spectre soit la suite précédente?} Je vais commenter ce programme: \begin{itemize} \item Tel quel le problème est mal posé (ou trop difficile), car non monotone par rapport à la relation de mineur: la réponse est triviale pour un graphe sans arête, car $O_G$ est l'ensemble des matrices diagonales réelles, tout spectre est alors possible pour un opérateur convenable de $O_G$. \item On va insister sur l'aspect ensemble d'opérateurs: ce n'est pas tant un opérateur isolé qui va nous intéresser, mais la position relative de $O_G$ et d'une variété $W$ donnée par des conditions spectrales, par exemple $\lambda_2= \lambda_3$. Cela permet d'introduire des idées de transversalité et donc de gagner une monotonie: tout ce qu'on peut faire avec un graphe $G$ doit pouvoir être fait avec tout graphe $G'$ tel que $G$ est mineur de $G'$. On peut aussi rapprocher cela de la théorie des discriminants (Arnold, Vassiliev), qui consiste à regarder les objets singuliers de l'ensemble considéré, ici l'ensemble des opérateurs dont au moins une valeur propre est multiple. \item Les arguments de transversalité permettent ainsi de construire des nouveaux invariants des graphes qui sont reliés à la théorie classique des graphes: plongements dans les surfaces, arbres, mineurs. \item L'argument suivant montre que, si $G$ est un graphe à $n$ sommets, toute suite $\lambda_1 < \cdots < \lambda_n $ de $n$ nombres distincts est le spectre d'un $A \in O_G$: on considère les applications $$\Phi_\varepsilon:\{u_1< u_2 <\cdots 0$ petit) de la forme quadratique $$q_{\varepsilon , u}(\vec{x})=\sum u_i \vec{x}(i)^2 +\varepsilon \sum_{\{i,j\}\in E} (\vec{x}(i)-\vec{x}(j))^2. $$ Pour $\varepsilon =0$, $\Phi_\varepsilon =\mathrm{Id}$ et, comme $\Phi_\ge (u)\in O_G$ pour $\ge >0$, l'application du théorème des fonctions implicites donne le résultat. \end{itemize} Le problème se concentre donc sur les multiplicités. \begin{exem}[les chemins]\label{ex:path} Soit $P_n$ le chemin à $n$ sommets $\{1,\dots ,n\}$ et les arêtes $\{i, i+1\}$, $1\leq i \leq n-1$. Toutes les valeurs propres d'un opérateur quelconque de $O_{P_n}$ sont simples, car un vecteur propre $\vec{x}$ est entièrement déterminé par $\vec{x}(1)$. Les matrices correspondantes à ce cas sont appelées \og matrices de Jacobi\fg. Une étude très précise de leurs spectres et de leurs déformations à spectre constant est possible. \end{exem} \begin{exem}[les graphes cycliques] Les sommets de ce graphe $C_n$ sont les éléments de $\Z/n\Z$ et les arêtes joignent $i$ à $i\pm 1 \pmod n$. Commençons par étudier le cas où $A=-\Ad_{C_n}$. Les vecteurs propres sont les $\vec{v}_l (i)=\go_l^i $ où $\go_l= \exp(2i\pi l /n)$ et donc $\go_l^n =1$. Les valeurs propres associées sont les $-2 \cos \sfrac{2\pi l}{n}$, $l=0,\dots, n-1$. La décomposition d'un vecteur $\vec{x}$ suivant la base des $\vec{v}_l $ est la série de Fourier discrète de ce vecteur. Les vecteurs $\vec{v}_l $ sont deux à deux orthogonaux et de norme $\sqrt{n}$. On en déduit des formules simples pour le transformation de Fourier discrète et son inverse. \begin{theo} Pour tout $A\in O_{C_n}$~(\cite{CV8}): $$ \la_1 < \la_2\leq \la_3< \la_4\leq \la_5 < \cdots.$$ \end{theo} \begin{demo} Le jeu consiste à introduire le spectre impair obtenu en faisant agir $A$ sur les fonctions $f:\Z \to\R$ telles que $f(k+n)=-f(k) $. On note $\mu_1 \leq \cdots \leq \mu_n $ ces valeurs propres. \begin{itemize} \item Les deux spectres sont disjoints: on introduit la matrice $2\times 2$ $P(t)$ qui à $(\vec{x}(0), \vec{x}(1))$ associe $(\vec{x}(n), \vec{x}(n+1))$ où $\vec{x}$ satisfait $(A-t)\vec{x}=0$ sur $\Z$. On vérifie, par récurrence, que $\det (P(t))>0$. De plus $1$ est valeur propre de $P(t)$ si et seulement si $t$ est valeur propre de $A$ alors que $-1$ est valeur propre de $P(t)$ si et seulement si $t$ est valeur propre impaire de $A$. \item Pour $A=-\Ad_{C_n}$, on a: \[ \gl_1 < \mu_1=\mu_2 < \gl_2= \gl_3 < \mu_3 = \mu_4 < \cdots. \] \item Les inégalités strictes entre les $\gl_i $ et les $\gm_j$ sont préservées par déformation (non croisement et continuité des valeurs propres).\qedhere \end{itemize} \end{demo} \end{exem} \section{Le théorème de Perron-Frobenius et ses extensions} \Subsection{Minimax et uniforme continuité des valeurs propres} \label{sec:minimax} Si ${\cal E}$ est un espace euclidien, il est classique que les valeurs propres de $A\in {\cal S}({\cal E})$ sont les valeurs critiques de la restriction $f_A$ de $q_A$ à la sphère unité de ${\cal E}$. La première valeur propre $\gl_1$ est le minimum de $f_A$. La seconde $\gl_2$ correspond à un point col que l'on peut attraper par un principe de type minimax; voici l'idée: supposons qu'on veuille aller d'un point $A$ à un point $B$ dans l'espace topologique $X$ en montant le moins possible, on va alors passer par un col dont l'altitude $h$ est donnée par \[h = \inf_{\gg \in \Omega_{A,B}}\Bigl(\sup_{0\leq t \leq 1} f(\gg(t)) \Bigr) \] où $\Omega_{A,B}:=\{\gg: [0,1]\to X\mid \gg(0)=A,~\gg(1)=B,~ \gg~ {\rm continu}\} $ et $f:X\to\R $ est l'altitude. Ici on joue sur le fait que $f_A$ vient d'une forme quadratique pour simplifier l'approche précédente: \begin{theo}[Minimax]\label{theo:minimax} Soit ${\cal E}$ un espace euclidien, $A \in {\cal S}({\cal E})$ et $\gl_1\leq \gl_2 \leq \cdots \leq \gl_n $ les valeurs propres de $A$ répétées suivant leur multiplicité. On a: \[ \gl_k = \min_{\substack{F\subset {\cal E}\\\dim F =k}} \biggl(\max_{\substack{\vec{x}\in F\\ \| \vec{x}\|=1}} \ \biggr).\] La première valeur propre $\gl_1$ est donnée par \[ \gl_1= \min_{\vec{x}\ne 0} \frac{\}{\<\vec{x}\mid\vec{x}\>} ,\] et le $\min$ est atteint exactement pour les vecteurs propres de valeur propre $\gl_1$. \end{theo} \begin{demo} Soit $(e_1,\dots, e_n)$ une base orthonormée de vecteurs propres associés aux $\gl_k$. Si $F_0= {\rm vec}(e_1,\dots ,e_k)$, on a $$ \max_{\substack{\vec{x}\in F_0\\ \| \vec{x}\|=1}} \ = \gl_k. $$ Si $\dim F =k$, il existe dans $F$ un vecteur $\vec{x}$ orthogonal à $e_1,\dots, e_{k-1} $ de norme $1$. On a $\ \geq \gl_k $. \end{demo} On en déduit: \begin{theo} \label{theo:continu} Si on définit la norme $\|\cbbullet\| $ sur $ {\cal S}({\cal E})$ par: \[ \| A \| = \max_{\substack{\vec{x}\in {\cal E}\\ \| \vec{x} \|=1}} | \ | ,\] on a, pour tout $A,B \in {\cal S}({\cal E})$: \[ |\gl_k (B)-\gl_k (A) | \leq \| B-A \|.\] Chaque valeur propre est donc uniformément continue et même lipschitzienne de coefficient $1$. \end{theo} Attention, comme on le verra plus bas, $A\to\gl_k (A) $ n'est pas différentiable aux points où $\gl_k$ est de multiplicité $\geq 2$. \Subsection{Le théorème de Perron-Frobenius} \begin{theo}[Perron-Frobenius]\label{theo:PF} Si $G$ est connexe et $A\in O_G$, la valeur propre $\gl_1$ est simple et l'espace propre est engendré par un vecteur propre dont toutes les coordonnées sont $>0$. \end{theo} \begin{demo} Il suffit de montrer (pourquoi?) que, si \hbox{$\vec{x} \in E_{\gl_1} \setminus 0$}, on a: \begin{itemize} \item $|\vec{x}| \in E_{\gl_1}$; \item si $\vec{x}\geq 0$, $\vec{x}$ ne s'annule pas \end{itemize} La première assertion vient de ce que $\ \leq \ $ (les coefficients non diagonaux de $A$ sont $\leq 0$), alors que $\|\, |\vec{x}|\,\| = \| \vec{x} \| $. Montrons la seconde assertion par l'absurde: par connexité de $G$, si $\vec{x} \ne 0$, il existe une arête $\{i, j\}$ telle que $\vec{x}(i)=0$ et $\vec{x}(j) > 0$. On a $A\vec{x}(i)<0$. On pose $\vec{x}_\ge =\vec{x} + \ge \gd (i)$, on a: $\= \ + 2\ge A\vec{x}(i)+O(\ge^2)$, alors que $\| \vec{x}_\ge \|^2= \| \vec{x}\|^2 +O(\ge^2)$. On a donc \[ \frac{\}{\| \vec{x}_\ge \|^2}< \frac{\}{\| \vec{x}\|^2} \] pour $\ge >0$ petit. \end{demo} \begin{exo} Si $G$ est un arbre à $n$ sommets, déduire du théorème précédent que $\gl_n$ est simple. \end{exo} \subsection{Le théorème nodal de Courant} On peut étendre ce résultat de connexité aux valeurs propres suivantes: \begin{theo}[théorème nodal de Courant]\label{theo:minsupp} Soit $A\!\in\!O_G$ et \hbox{$\vec{x} \!\in\! E_{\gl_2}\setminus 0$} de support minimal\footnote{Le support $s(\vec{x})$ d'un vecteur est l'ensemble des sommets $i$ tels que $\vec{x}(i)\ne 0$. $\vec{x}$~est de support minimal si $y \in E_{\gl_2}\setminus 0$ et $ s(\vec{y})\subset s(\vec{x})$ implique $s(\vec{y})=s(\vec{x})$}, alors les ensembles \hbox{$V_\pm =\{i\mid \pm \vec{x}(i) >0\}$} sont connexes. \end{theo} \begin{demo} Par l'absurde, supposons $V_+$ non connexe. Soient $V_+= V_1 \cup V_2$ où $V_1$ et $V_2$ sont non vides et ne sont joints par aucune arête. Supposons que $\gl_2=0$. Soient, pour $j=1,2$, $\vec{x}_j=\vec{x} \chi_{V_j}$ et $Q(u,v)= q_A (u\vec{x}_1+ v \vec{x}_2)$. On a $Q \leq 0$: en effet, comme il n'y a pas d'arête de $V_1$ à $V_2$, $Q(u,v)= u^2 q_A (\vec{x}_1)+ v^2 q_A (\vec{x}_2)$. De plus $q_A (\vec{x}_1) \leq 0$, car, pour toute arête $\{i, j\}$ avec $i\in V_1$, $j \notin V_1$, $\vec{x} (j)\leq 0$ et donc $A\vec{x}_1(i)= A\vec{x} (i)- \sum_{j \notin V_1} a_{i,j}\vec{x} (j) \leq 0$. On en déduit, par le minimax, qu'il existe $\vec{x} = u_0 \vec{x}_1+ v_0 \vec{x}_2 \in \ker A \setminus 0 $ ce qui contredit la minimalité, car le support de $\vec{x}$ contient aussi des points où $\vec{x}(i)<0$ (pourquoi?). \end{demo} \section{Stabilité structurelle} \Subsection{Transversalité} \begin{defi} Soient $x_0 \in Y \cap Z $ où $Y$ et $Z$ sont deux sous-variétés de $\R^N$. On dit que $Y$ et $Z$ se coupent \emph{transversalement} en $x_0$, si $\R^N = T_{x_0} Y + T_{x_0} Z $. Attention, on n'exige pas une somme directe. \end{defi} Si $Y$ et $Z$ se coupent transversalement en $x_0$, $\dim Y+ \dim Z \geq N $. De plus $Y \cap Z $ est au voisinage de $x_0$ une sous-variété de dimension $\dim Y + \dim Z - N $. À quoi sert la transversalité? La transversalité est une propriété robuste, on dit plutôt \emph{structurellement stable}. \begin{theo} \label{theo:transv} Si $Y_0$ et $Z_0$ se coupent transversalement en $x_0$ et $Y $ est $C^0$ proche de $Y$, $Y$ et $Z_0$ se coupent près de $x_0$. \end{theo} C'est assez difficile à montrer pour $C^0$ proche, mais c'est une conséquence du théorème des fonctions implicites pour $C^1$ proche. \subsection{Coordonnées locales adaptées}\label{sec:coord} Soient ${\cal E}$ un espace euclidien de dimension $n$, $A \in {\cal S}({\cal E})$ et $E_0= \ker A $ supposé de dimension~$l$. Soit $F_0= E_0^\perp $ l'orthogonal de $E_0$. Soit \[ \Phi:{\cal S}(E_0)\oplus {\cal S}(F_0)\oplus L(E_0, F_0) \to{\cal S}({\cal E})\] définie par \[ \Phi (B,C,D)=\exp(-\tilde{D}) \left( \begin{array}{cc} B &0\\ 0 &C \end{array} \right) \exp(\tilde{D}) \] où $\tilde{D}$ est l'endomorphisme antisymétrique de ${\cal E}$ donné par \[ \tilde{D}= \left( \begin{array}{cc} 0 &-D^t\\ D &0 \end{array} \right).\] \begin{theo} Soit $C_0$ inversible, $\Phi $ est un difféomorphisme local d'un voisinage de $(0,C_0, 0)$ sur un voisinage de la matrice \[A_0= \left( \begin{array}{cc} 0 &0\\ 0 &C_0 \end{array} \right) \] Les matrices voisines de $A_0$ dont le noyau est de dimension $l$ forment donc une sous-variété de codimension $l(l+1)/2$ donnée par l'image de $B=0$. Le spectre de $\Phi (B,C,L)$ est la réunion du spectre de $B$ (les $l$ petites valeurs propres) et du spectre de $C$ (les autres valeurs propres). De plus, la différentielle de la coordonnée locale $B$ qui donne les petites valeurs propres est égale à la différentielle du bloc $E_0 \times E_0$ de~$A$. La forme quadratique associée à ce bloc est la restriction à $E_0$ de la forme quadratique associée à $A$. \end{theo} \begin{demo} La différentielle de $\Phi$ en $A_0$ est \[ d\Phi= \left( \begin{array}{cc} dB & dL^t C_0\\ C_0dL & dC \end{array} \right) \] qui est visiblement bijective. \end{demo} \subsection{Perturbations des valeurs propres multiples} Soit ${\cal E}$ un espace euclidien de dimension $n$, $A_0 \in {\cal S}({\cal E})$ et $\Lambda_0:=\gl_{k+1}=\gl_{k+2}=\cdots = \gl_{k+l}$ une valeur propre de $A_0$ de multiplicité $l$. Soit $E_0= \ker (A_0-\Lambda_0)$ et pour $B \in {\cal S}({\cal E})$, $q_B (\vec{x})=\$ vue comme forme quadratique sur $E_0$. \begin{theo} Les valeurs propres de $A_0+B \in {\cal S}({\cal E})$ satisfont, pour $1\leq j \leq l $, \[ \gl_{k+j} (A_0+B)=\Lambda_0 + \gl_j (q_B) +O(\| B\|^2).\] Les matrices qui satisfont $\gl_{k+j} (A) =\Lambda_0$ pour $1\leq j \leq l $ et $ \gl_k(A)< \Lambda_0 < \gl_{k+l+1}(A)$ forment une sous-variété $W_{l,k} $ de codimension \hbox{$l(l+1)/2$} de $ {\cal S}({\cal E})$ dont l'espace tangent est donné par les $B$ tels que $q_B=0$. \end{theo} On peut aussi introduire d'autres sous-variétés analogues à celle qui précède. Celle qui va nous servir aujourd'hui est \[ W_l=\{A\mid \dim \ker (A -\gl_2(A))=l\}. \] La codimension de $W_2$ vaut $2$: l'observation que la condition d'avoir une valeur propre double pour une matrice symétrique réelle est de codimension $2$ remonte aux années 1930 (Wigner-Von Neumann \cite{vN-W}, voir aussi \cite{AR1}). Donc, si $t\to A_t $ est un chemin générique dans $S({\cal E})$, il n'y aura de valeurs propres multiples pour $A_t$ pour aucun $t$. On aura typiquement une évolution des valeurs propres faisant apparaître des \emph{croisements évités.} Soit maintenant $\Phi:(u,v)\to A_{u,v}$ une famille à deux paramètres de matrices symétriques. Supposons que $\Phi $ coupe transversalement $W_{2,k} $ en $(u_0,v_0)$; on a donc, en notant $A_0=A_{u_0,v_0}$, le spectre de $A_0$ qui vérifie $$\cdots \leq \la_{k-1}< \la_k =\la_{k+1}< \cdots ,$$ et le graphe simultané de $\la_k$ et $ \la_{k+1}$ a l'allure d'un cône. \begin{figure}[htb] \begin{center} \includegraphics[scale=.8]{xups04-02_fig3} \caption{Point diabolo} \label{fig: diabolo} \end{center} \end{figure} Soit $\gamma $ un lacet du plan des $(u,v)$ qui entoure $(u_0,v_0)$ sans entourer d'autres points $(u,v)$ avec $A_{u,v}\in W_{2,k}$, soit $\phi_k(t)$ un vecteur propre de $A_{\gamma (t)}$ correspondant à la valeur propre simple $\la_{k}(A_{\gamma(t)})$ supposé réel et de norme 1 et que l'on peut donc suivre par continuité autour de~$\gamma $; lorsqu'on fait un tour, $\phi_k(t)$ se transforme en $-\phi_k(t)$. Le fibré réel de dimension 1 donné par l'espace propre $\ker (A_{\gamma (t)}-\la_k (t))$ est donc non trivial (ruban de Möbius). Ce fait peut être mise à profit pour détecter des valeurs propres multiples dans une famille d'opérateurs dépendant de deux paramètres. Voir \cite{B-W}. La transversalité joue un grand rôle ici: sans elle, la monodromie pourrait être triviale!\string! C'est cette situation que nous allons généraliser maintenant. \subsection{Stabilité structurelle des valeurs propres} On est ainsi conduit à donner une définition de la stabilité structurelle d'une valeur propre: \begin{defi} Soit $A\!\in\! O_G \!\subset\! {\cal S}({\cal E})$. Supposons que la valeur propre~$\gl_2$ de $A$ est de multiplicité $l$ ($A\!\in\! O_G \cap W_{l}$). On dit que la valeur propre~$\la_2$ de $A$ est structurellement stable si $W_{2}$ et $O_G $ se coupent transversalement en $A$. Autrement dit, l'apparition d'une valeur propre $\gl_2$ de multiplicité $l$ dans $O_G $ est un phénomène stable par perturbation de~$O_G$. \end{defi} On peut tester de fa{ç}on purement algébrique cette condition de stabilité si on connaît l'espace propre: si $\Phi: O_G \to{\cal S}(E_0)$ (où $E_0= \ker(A-\gl_2)$ est l'espace propre de $A$ considéré) est donnée par\enlargethispage{\baselineskip} $$ \Phi (B)(\vec{x})=\<\vec{x}\mid B \mid \vec{x}\> ,$$ la condition de stabilité structurelle équivaut à la surjectivité de $\Phi $. On peut reformuler la stabilité de la façon suivante: \begin{theo} La valeur propre $\gl_2 (A)$ avec $A\in O_G$ est \emph{stable} si les restrictions à $E_0= \ker(A-\gl_2)$ des formes quadratiques $x_i x_j$ ($\{i,j\} \in E_G$) et $x_i^2$ ($i\in V_G$) engendrent l'espace ${\cal Q}(E_0)$ des formes quadratiques sur $E_0$. \end{theo} \subsection{Exemples} Les assertions suivantes sont des exercices: \begin{exem} La \emph{première} valeur propre $\lambda_1$ n'est stable que si elle est de multiplicité 1. \end{exem} \begin{exem} Soit $E_n$ \emph{l'étoile} à $n$ branches, $A\in O_{E_n}$ où $-A$ est la matrice d'adjacence. La deuxième valeur propre de $A$ est de multiplicité $n-1$ et n'est stable que si $n\leq 3$. \end{exem} \begin{exem}[graphes complets] Il s'agit des graphes $K_n$ dont toute paire de sommets est connectée par une arête. Si $A$ est le laplacien canonique, la seconde valeur propre, de multiplicité $n-1$, est stable. \end{exem} \begin{exem}[graphe de Kuratowski]\label{ex:kura} Il s'agit du graphe noté $K_{3,3}$ dont l'ensemble des sommets est $V_1\cup V_2$ (union disjointe), avec \hbox{$\vert V_i \vert \!=\!3 $}, et les 9 arêtes joignent les sommets de $V_1$ à ceux de $V_2$. Si $A$ est le laplacien canonique, son spectre est $$ 0< 3=3=3 =3 < 6,$$ et la valeur propre $3$ de multiplicité $4$ est stable. \end{exem} \subsection{L' invariant \texorpdfstring{$\mu (G)$}{muG}} On définit maintenant un invariant numérique d'un graphe $G$: \begin{defi} Si $G$ est un graphe fini, $ \mu (G)$ est défini comme le maximum des entiers $l$ tels qu'il existe $A \in O_G$ avec $\la_2 (A) $ de multiplicité~$l$ et stable. \end{defi} \begin{exem} $\mu (K_n)=n-1$. \end{exem} \begin{exem} $\mu (K_{3,3})=4$. \end{exem} \begin{exem} Pour $n\geq 2$, $\mu (E_n)=2 $. \end{exem} \begin{exem} $\mu (C_n)=2$ si $n\geq 3$. \end{exem} \begin{exos}\mbox{} \begin{enumeratea} \item Montrer que $\ha \mu(G)(\mu(G)+1) \leq |E|+|V| $. \item Montrer que $\ha \mu(G)(\mu(G)+1) \leq |E|+1 $ (plus dur!). \item Si $G$ admet plusieurs composantes connexes, $G_i$, on a: $\mu (G)=\max \mu (G_i)$. \end{enumeratea} \end{exos} \section{Mineurs des graphes et limites singulières d'opérateurs} \subsection{Monotonie par mineurs} La propriété principale de l'invariant $\mu $ est la monotonie par mineur (\cf théorème \ref{theo:mineur}). Pour montrer ce théorème, il suffit de le montrer dans les cas particuliers où l'on ôte ou contracte une arête de $G_1$. Le cas où l'on ôte une arête est simple, car ${\cal E}_{G_1}={\cal E}_{G_2}$. On utilise alors la conservation d'une intersection transversale par perturbation~$C^1$. Donnons l'argument plus précis: soit ${\cal E} $ l'espace euclidien considéré et supposons que l'on a numéroté les sommets de $G_2$ de fa{ç}on que $G_1$ s'obtienne en ôtant l'arête $\{1,2\}$ de $G_2$. Soit $Z_{\varepsilon}=O_{G_1}+\varepsilon (\vec{x}(1)-\nobreak\vec{x}(2))^2 $ (où on a écrit les opérateurs comme des formes quadratiques), alors $Z_\varepsilon \subset O_{G_2}$ pour $\varepsilon >0$. On conclut ainsi: si $O_{G_1}$ et $W_{l}$ se coupent transversalement en $A$, il en est de même pour $Z_\varepsilon $ et $W_{l}$ en $A_\varepsilon $ et donc de $O_{G_2}$ et $W_{l}$ en $A_\varepsilon $. Le cas où l'on contracte l'arête $\{1,2\}$ est plus délicat, car il n'est plus vrai que ${\cal E}_{G_1}={\cal E}_{G_2}$; on a seulement une inclusion $ {\cal E}_{G_1}\subset {\cal E}_{G_2} $ en identifiant ${\cal E}_{G_1}$ au sous-espace de $\R^{V_2}$ dont les éléments sont les vecteurs $\vec{x}$ tels que $\vec{x}(1)=\vec{x}(2)$. On doit pour faire marcher l'argument précédent mettre dans une même variété les opérateurs non partout définis. C'est le but du paragraphe suivant. Une autre difficulté est que la structure euclidienne du sous-espace de ${\cal E}_{G_2}$ n'est pas la structure canonique de ${\cal E}_{G_1}$. \subsection{\texorpdfstring{$\Gamma$}{G}-convergence} Soit ${\cal E}$ un espace euclidien de dimension finie $n$. Soit $A$ un opérateur symétrique sur ${\cal E}$. On note $q_A$ la forme quadratique associée. Soit $\Gamma (A)=\{(\vec{x},A\vec{x})\mid \vec{x}\in {\cal E}\}\subset {\cal E}\oplus {\cal E} $ le graphe de $A$. Soit $Y\subset {\cal E} $ un sous-espace euclidien de ${\cal E}$ et $B: Y\rightarrow Y $ un opérateur symétrique sur $Y$, on dira que le couple $(Y,B)$ est un opérateur non borné sur ${\cal E}$ si $Y\ne {\cal E} $. On étend la définition du graphe aux opérateurs non bornés de la façon suivante. $$\Gamma (Y,B)=\{(\vec{y},\vec{z})\in Y\oplus {\cal E}\mid \forall \vec{w}\in Y, \<\vec{z} \mid \vec{w}\, \>=\\}.$$ Comme cas particulier, $\Gamma (A)=\Gamma ({\cal E},A)$. Il est clair que $\Gamma (Y,B) $ est toujours un sous-espace de dimension $n$ de ${\cal E}\oplus {\cal E} $. Soit $\omega$ la forme bilinéaire antisymétrique non dégénérée (forme symplectique) définie par $$ \omega ((\vec{x},\vec{y}), ({\vec{x}}^{\,\prime},{\vec{y}}^{\,\prime}))= \< {\vec{y}}^{\,\prime}\mid \vec{x}\, \> -\<{\vec{x}}^{\,\prime} \mid \vec{y}\,\>. $$ Un sous-espace de ${\cal E}\oplus {\cal E} $ de dimension $n$, qui est isotrope pour la forme $\omega $ est dit \emph{lagrangien}. On vérifie que tout sous-espace lagrangien est le graphe d'un unique opérateur symétrique, borné ou non, et que réciproquement tout graphe $\Gamma (Y,B)$ est lagrangien. L'ensemble des opérateurs symétriques avec domaine sur ${\cal E}$ est ainsi une compactification $\Lambda_{\cal E} $ de l'espace $S({\cal E})$ des endomorphismes symétriques de ${\cal E}$ en une variété compacte de classe $C^\infty $. On définit, pour $\gl \in \R \cup \infty $, le sous-espace lagrangien $I_\gl $ de ${\cal E}\oplus {\cal E}$ par: \begin{itemize} \item si $\gl \in \R $, $I_\gl=\{(\vec{x}, \gl \vec{x})\mid \vec{x}\in {\cal E}\}$; \item $I_\infty =0\oplus {\cal E}$ \end{itemize} \begin{defi} Le spectre de $A$ est l'ensemble des $\gl \in \R \cup \infty $ tels que $\Gamma (A) \cap I_\gl \ne 0 $. la multiplicité de $\gl$ est la dimension du sous-espace précédent. \end{defi} Par exemple la multiplicité de la valeur propre $\infty$ est la codimension du domaine. La somme des multiplicités vaut $n= \dim {\cal E}$. Il est clair que cette définition prolonge la définition pour les opérateurs partout définis. \begin{defi} On dira qu'une famille $A_\e$, $\e >0 $, d'opérateurs symétriques sur ${\cal E}$ $\Gamma$-converge vers $(Y,B)$ si $\Gamma (A_\e)$ converge vers $\Gamma (Y,B)$ quand $\e \rightarrow 0$ au sens de la topologie naturelle de la grassmannienne des sous-espaces de dimension $n$ de ${\cal E}\oplus {\cal E} $. On note $$ A_\e \gra (Y,B).$$ \end{defi} \begin{exem} Considérons les matrices $A_\ge $ sur $\R^2$ associées aux formes quadratiques $q_\ge({x},y)= (x-\sfrac{y}{\ge})^2 $. On a: \[ \gl_1(\ge)=0 < \gl_2(\ge)=1+\frac{1}{\ge^2}.\] Considérons successivement les limites de $A_\ge$ pour la convergence simple et pour la $\Gamma$ convergence. \begin{itemize} \item $q_\ge (x,y) \to+\infty $ si $y\ne 0$ et $q_\ge (x,0)=x^2$. La limite simple est donc la forme quadratique $x^2$ sur $y=0$. Son spectre est $\gl_1 =1 < \gl_2= +\infty $. Ce spectre \emph{n'est pas la limite de celui de $q_\ge$}! \item Le graphe $\Gamma_\ge $ de $A_\ge $ est donné par \[ \Gamma_\ge = \Big\{\Big(x,y; \xi=x-\frac{y}{\ge},\eta=-\frac{x}{\ge}+ \frac{y}{\ge^2}\Big)\Big\} \] qu'on peut réécrire \[ \Gamma_\ge = \{(x,\ge(x+\ge \eta);-\ge \eta, \eta)\} \] dont il est clair que la limite est \[ \Gamma_0 = \{(x,0;0, \eta)\} \] graphe de la forme quadratique $0$ sur le domaine $y=0$. Le spectre de cette forme est $\gl_1=0 < \gl_2=\infty $ qui \emph{est la limite de celui de $q_\ge$.} \end{itemize} \end{exem} Le résultat suivant étend au cadre de la $\Gamma$-convergence les résultats classiques de Kato \cite{KO} sur la convergence des spectres de formes quadratiques. \begin{theo} Supposons $ A_\e \gra (Y,B)~$. Soient $$ \lambda_1 (\e) \leq \cdots \leq \lambda_n (\e)$$ les valeurs propres de $A_\e $. Alors le spectre de $A_\e $ converge vers celui de $(Y,B)$ au sens de la topologie de $P^1(\R)=\R \cup \infty $. \end{theo} \begin{demo} Il suffit de monter que, si $I \cap \gs (A_0)=\emptyset $ où $I $ est un compact de $\R \cup \infty $, il existe un voisinage $U$ de $A_0$ tel que si $A \in U$, $I \cap \gs (A)= \emptyset $. C'est quasi trivial, car $I \cap \gs (A)=\emptyset $ équivaut à dire que le graphe de $A$ ne rencontre pas la réunion (compacte) des $I_\gl\cap B$, $\gl \in I $, où $B$ est la sphère unité de ${\cal E}\oplus {\cal E} $. \end{demo} \begin{exem}[contraction d'une arête] Soit $$ q_\e (\vec{x})=Q(\vec{x})+ \frac{1}{\e}(\vec{x}(1)-\vec{x}(2))^2. $$ Lorsque $\e \to0$, $q_\e \gra (Y,B)$ où $Y= \{\vec{x}(1)=\vec{x}(2)\}$ et $q_B$ est la restriction de $Q$ à $Y$. Cet exemple permet de traiter la contraction d'une arête comme le cas où l'on ôte une arête. \end{exem} \begin{exem}[transformations étoile-triangle] Voir \cite{C-B} pour ce qui suit. Plaçons-nous sur ${\cal E}=\R^4$, avec la forme quadratique $$Q_\e (\vec{x})= \<\vec{x} \mid A_\e \mid \vec{x} \>=\sum_{i=1}^3 \Bigl(\vec{x}(i)-\frac{\vec{x}(0)}{\e}\Bigr)^2.$$ L'opérateur $A_\e $ associé est dans $O_{E_3}$. La $\Gamma$-limite $Q_0$ de $Q_\e$ a pour domaine $Y_0 =\{\vec{x}(0)=0\} $ et $$ Q_0(\vec{x})= \frac{1}{3}\sum_{i=1}^3 (\vec{x}(i) -\vec{x}(i+1))^2. $$ On peut interpréter $Q_0$ comme un élément de $O_{C_3}$. On a ainsi remplacé une étoile à trois branches par un triangle. Aucun des deux graphes n'est mineur de l'autre! On dit que $G'$ s'obtient de $G$ par une transformation \emph{étoile-triangle} si on remplace un sommet $0$ de degré $3$ de $G$ et les arêtes $\{0,i\}$, $1\leq i \leq 3$, qui s'y accrochent par le triangle $(1,2,3)$. \begin{figure}[htb] \begin{center} \includegraphics[scale=.8]{xups04-02_fig4} \caption{Transformation étoile-triangle} \label{fig: etoile-triangle} \end{center} \end{figure} $O_{G'}$ est alors une strate de l'adhérence de $O_G$ dans $\Lambda_{{\cal E}_G}$. \end{exem} \section{Plongements de graphes dans les surfaces} \subsection{Le théorème de Cheng et sa réciproque} Cheng \cite{CH} a prouvé une variante du résultat suivant: \begin{theo} \label{theo:cheng} Si $A=-\Delta +V $ est un opérateur de Schrödinger dans le plan avec $V(x) \to+\infty $ quand $x \to\infty $, la multiplicité de $\la_2 (A)$ est inférieure ou égale à $3$; cette borne est optimale. \end{theo} Les ingrédients de la preuve sont le théorème de Jordan et le théorème de Courant sur les domaines nodaux. La preuve s'appuie sur la structure locale des lignes nodales des fonctions propres. Hein van der Holst a donné une version graphes du théorème de Cheng basée sur le théorème \ref{theo:minsupp}: \begin{theo} Si $G$ est le $1$-squelette d'une triangulation de $S^2$ et $A\in O_G$, la multiplicité de $\la_2(A)$ est au plus $3$. Cette borne est optimale et atteinte pour le laplacien canonique de $K_4$. \end{theo} Un point essentiel est que le théorème de Van der Holst ne s'applique pas à tout graphe planaire, par exemple à l'étoile à $n$ branches. \begin{demo} Raisonnons par l'absurde. Soit $A \in O_G$ telle que la multiplicité de $\gl_2 $ soit $\geq 4$. Soit $E_0= \ker (A -\gl_2)$ et $\{a,b, c\} $ un triangle de la triangulation dont $G$ est le $1$-squelette. Il existe $\vec{x} \in E_0 \setminus 0$ tel que $\vec{x}(a)=\vec{x}(b)=\vec{x}(c)=0$ qu'on peut supposer de support minimal. Supposons pour simplifier que $a,b$ et $c$ ont chacun au moins un voisin dans $G$ où $\vec{x}$ ne s'annule pas. Soit $V_\pm =\{i \mid \pm \vec{x}(i) >0\}$. Ce sont des ensembles connexes de $G$ d'après le théorème \ref{theo:minsupp}. Il suit de $A\vec{x}(a)=0$ que $a$ admet au moins un voisin $a_+ \in V_+$ et un voisin $a_- \in V_-$. De même pour $b$ et $c$. On en déduit facilement (figure \ref{fig:holst}) que $K_{3,3}$ est planaire, d'où contradiction. \begin{figure}[htb] \begin{center} \includegraphics[scale=.7]{xups04-02_fig5} \caption{Construction d'un $K_{3,3}$} \label{fig:holst} \end{center} \end{figure} \end{demo} Utilisant le fait que tout graphe planaire est mineur du $1$-squelette d'une triangulation de $S^2$, on en déduit que, si $G$ est planaire, \hbox{$\mu (G)\leq 3$}. En utilisant la théorème de Kuratowski (théorème \ref{theo:kura}) qui caractérise les graphes non planaires comme ceux dont $K_5$ ou $K_{3,3}$ est mineur, on montre la réciproque et donc le théorème \ref{theo:planaire}. \subsection{Extension aux autres surfaces} Les résultats pour les autres surfaces ont fait l'objet de nombreux travaux de Cheng, Besson, Nadirashvili et Sévennec. Ces travaux soutiennent la conjecture suivante: \begin{conj} \label{conj:chromsur} Si $X$ est une surface et $G$ se plonge dans $X$, \[ \mu(G) \leq \chi (X)-1.\] \end{conj} J'ai montré qu'une telle borne serait optimale. \begin{theo} La conjecture \ref{conj:chromsur} est vraie pour la sphère, le tore, le plan projectif, la bouteille de Klein, le tore à deux trous, les surfaces non orientables $S$ telles que $e(S)=-1,-2,-3$. \end{theo} La meilleure majoration générale est celle de Sévennec \cite{SC} qui est encore loin de la conjecture \ref{conj:chromsur}: \begin{theo} Si $G$ se plonge dans la surface $S$ avec $e(S)<0$, on~a: \[ \mu(G) \leq 5-e(S). \] \end{theo} \subsection{Les graphes ayant un plongement non noué et le résultat de Lovász-Schrijver} Une généralisation intéressante de la classe des graphes planaires est la classe des graphes $G$ admettant un plongement non noué dans $\R^3$, \ie tel que deux circuits disjoints quelconques de $G$ ne soient pas entrelacés comme lacets de $\R^3$. L'exemple le plus simple est $K_5$ qui n'est pas planaire, mais n'admet aucune paire de circuits disjoints. L'analogue du théorème de Kuratowski est que ces graphes admettent une caractérisation par mineurs exclus: les graphes exclus étant les transformés par étoile-triangle de $K_6$. On montre dans \cite{C-B} que $\mu (G)=5$ pour ces graphes et Lovász et Schrijver \cite{L-S} ont réussi à montrer le joli: \begin{theo} $\mu (G)\leq 4$ si et seulement si $G$ admet un plongement non noué dans $\R^3$. \end{theo} \section{Spectres et largeurs d'arbre} Il existe des analogues hermitiens de l'invariant $\mu(G)$. Un invariant simple $\nu(G)$ utilise la multiplicité de la première valeur propre et j'ai montré dans \cite{CV10} que $\nu(G)$ est contrôlé par la largeur d'arbre de $G$. \Changelback \backmatter \nocite{*} \bibliographystyle{jepplain+eid} \bibliography{xups04-02} \end{document}