On the null space of a Colin de Verdière matrix

Lovász, Lászlo  ; Schrijver, Alexander 

Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 1017-1026

Abstract (VO)

Let $G=(V,E)$ be a 3-connected planar graph, with $V=\{1,...,n\}$. Let $M=\left(m_{i,j}\right)$ be a symmetric $n\times n$ matrix with exactly one negative eigenvalue (of multiplicity 1), such that for $i,j$ with $i\ne j$, if $i$ and $j$ are adjacent then $m_{i,j}<0$ and if $i$ and $j$ are nonadjacent then $m_{i,j}=0$, and such that $M$ has rank $n-3$. Then the null space $kerM$ of $M$ gives an embedding of $G$ in $S^2$ as follows: let $\{a,b,c\}$ be a basis of $kerM$, and for $i\in V$ let $\phi \left(i\right):=(a_i,b_i,c_i{)}^T$; then $\phi \left(i\right)\ne 0$, and $\psi \left(i\right):=\phi \left(i\right)/\parallel \phi \left(i\right)\parallel$ embeds $V$ in $S^2$ such that connecting, for any two adjacent vertices $i,j$, the points $\psi \left(i\right)$ and $\psi \left(j\right)$ by a shortest geodesic on $S^2$, gives a proper embedding of $G$ in $S^2$.

We prove similar results for outerplanar graphs and paths. They apply to the matrices associated with the parameter $\mu \left(G\right)$ introduced by Y. Colin de Verdière.

Résumé

Soit $G=(V,E)$ un graphe planaire 3-connexe, avec $V=\{1,...,n\}$. Soit $M=\left(m_{i,j}\right)$ une matrice symétrique $n\times n$ ayant exactement une valeur propre $<0$ (de multiplicité 1), telle que, pour toute arête $\{i,j\}$, $m_{i,j}<0$ et, si $\{i,j\}$ n’est pas une arête, $m_{i,j}=0$, et supposons que le rang de $M$ soit $n-3$. Alors le noyau $kerM$ de $M$ définit un plongement de $G$ dans $S^2$ de la façon suivante : soit $\{a,b,c\}$ une base de $kerM$ ; pour $i\in V$, on pose $\phi \left(i\right):=(a_i,b_i,c_i{)}^T$ ; alors $\phi \left(i\right)\ne 0$, et $\psi \left(i\right):=\phi \left(i\right)/\parallel \phi \left(i\right)\parallel$ est un plongement de $V$ dans $S^2$. Si on connecte, pour toute paire de sommets adjacents $i,j$, les points $\psi \left(i\right)$ et $\psi \left(j\right)$ par une géodésique minimisante dans $S^2$, on obtient un plongement de $G$ dans $S^2$.

Nous prouvons des résultats analogues pour les graphes extérieurs planaires et pour les chemins. Ces résultats s’appliquent aux matrices associées à l’invariant $\mu \left(G\right)$ introduit par Y. Colin de Verdière.

Détail

DOI : 10.5802/aif.1703