Algebraic graph invariant $\mu(G)$ which links Four-Color-Theorem with Schrödinger operators: further topological characterizations of graphs?

Question

30 years ago, Yves Colin de Verdière introduced the algebraic graph invariant $\mu(G)$ for any undirected graph $G$, see [1]. It was motivated by the study of the second eigenvalue of certain Schrödinger operators [2,3]. It is defined in purely algebraic terms as the maximum corank in a set of generalized Laplacian matrices of $G$.

It turned out to be very powerful concept, linking algebraic with topological graph theory (and, by conjecture, with graph coloring). For example,

1. Four Color Theorem: Colin de Verdière conjectures $\chi(G)\leq\mu(G)+1$ where $\chi(G)$ is the chromatic number of $G$, see [4]. If true, this would prove the Four Color Theorem.

2. Graph minor monotone: The property $\mu(G)\leq k$ is closed under taking graph minors of $G$, meaning $\mu(g)\leq \mu(G)$ if $g$ is a minor of $G$, see [1]. So, by the Robertson–Seymour Graph Minor Theorem, the property $\mu(G)\leq k$ can be characterized by a finite number of excluded graph minors.

3. Embeddability: $\mu(G)$ characterizes this topological property for several families of graphs: embeddable in a line $(\mu\leq1)$, outerplanar $(\mu\leq2)$, planar $(\mu\leq3)$, or linklessly i.e. flat embeddable in ${\mathbb R}^3$ $(\mu\leq4)$, see [1,2].

4. Embeddings in more general surfaces: If $G$ embeds in the real projective plane or in the Klein bottle, then $\mu\leq5$. If it embeds in the torus, $\mu\leq6$. If it embeds in a surface $S$ with negative Euler characteristic $\psi$, then $\mu\leq 4−2\psi$, see [4]

Now, I have two questions, the first one being the main one:

MAIN QUESTION: Is someone aware of further embeddability characterizations based on $\mu(G)$ beyond the results in bullet point No. 3? In No. 3, we have full characterizations, while the results in No. 4 are just implications for $\mu(G)$ in case $G$ can be embedded, i.e. just in one direction.

Quoting [3]: "The parameter was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators. These operators are defined on Riemann surfaces. It turned out that in this study one can approximate the surface by a sufficiently densely embedded graph $G$, in such a way that $\mu(G)$ is the maximum multiplicity of the second eigenvalue of the operator, or a lower bound to it."
SECOND QUESTION: So it appears $\mu(G)$ was developed to resolve a problem in Schrödinger operator theory. I wondered when/how the idea emerged to study $\mu(G)$ as a graph invariant in its own right? I looked at [1] and [CV 1] but could not find an answer.

References
[1] Yves Colin de Verdiere (1990): Sur un nouvel invariant des graphes et un critère de planarité, J. Combin. Th. (B) 50, 11–21.
[2] L. Lovasz & A. Schrijver (1998): A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, Proc. Amer. Math. Soc. 126, 1275–1285.
[3] H. van der Holst, L. Lovasz & A. Schrijver (1999): The Colin de Verdière graph parameter, pp. 29– 85 in: Graph Theory and Combinatorial Biology (L. Lovasz et al., eds.), János Bolyai Math. Soc., Budapest.
[4] Andries E. Brouwer, Willem H. Haemers (2011): Spectra of graphs, Springer Monograph.

Earlier work that Colin de Verdière cites in his article [1]:
[CV 1] Y. COLIN DE VERDIÈRE, Spectres de variétés riemanniennes et spectres de graphes, Proc. Intern. Congress of Math., Berkeley 1986, 522-530.
[CV 2] Y. COLIN DE VERDIÈRE, Sur la multiplicité de la premiere valeur propre non nulle du laplacien, Comment. Math. Helv. 61 (1986), 254-270.
[CV 3] Y. COLIN DE VERDIÈRE, Sur une hypothèse de transversalité d’Arnold, Comment. Math. Helv. 63 (1988). 184-193.
[CV 4] Y. COLIN DE VERDIÈRE, Constructions de laplaciens dont une partie finie du spectre est donné, Ann. Sci. École Norm. Sup. 20 (1987), 599-615.

https://en.wikipedia.org/wiki/Colin_de_Verdi%C3%A8re_graph_invariant

Answer 1

Embeddability in any surface but the sphere (or plane) can probably not be characterized via the Colin de Verdière number.

Suppose that $K_n$ is the largest complete graph that embedds into a surface $S$. This shows that the best we can hope for is "$G$ embedds in $S$ $\Leftrightarrow$ $\mu(G)\le\mu(K_n)= n-1$".

The following is still a bit hand-wavy (maybe someone can help): I can imagine, that a disjoint union of sufficiently many $K_n$ can no longer be embedded into $S$ (except if $S$ is a sphere/plane). My intuition is that any additional $K_n$ must embedd in one of the regions given by the embedding of the previous $K_n$, and this region is probably "of a lesser genus" (if the genus is not already 0). For example, this is true for $S$ being the projective plane: $K_5$ embedds in $\Bbb R P^2$, but $K_5+K_5$ does not (see here). Also, a claim in this question seems to support this in the orientable case.

But we also have $\mu(K_n+\cdots +K_n)=\mu(K_n)=n-1$ (see [1]), contradicting the desired characterization.

---

[1] van der Holst, Lovász, Schrijver: "The Colin de Verdière graph parameter", Theorem 2.5

Answer 2

Perhaps I can contribute to the history part the question, since I was quite close to the Institut Fourier at that time and was very interested in their work (I am a physicist). Grenoble now has several different research groups doing graph theory (like G-SCOP, Institut Fourier, GIPSA-lab, LIG) but I think L'Institut Fourier was the early one for graph theory.

Here are two original quotes from Yves Colin de Verdière about the time when $\mu(G)$ evolved; my translation. The quotes give a view about his collaboration with the graph theory team; and his view of graphs as singular Riemannian manifolds, in the context of his differential geometry work.

First quote from Yves Colin de Verdière 2004 [Theorem 5 is about graph minor monotonicity of $\mu$ and Theorem 6 is the characterization of planar graphs. Theorem 17 is from S. Cheng: Eigenfunctions and nodal sets. Comment. Math. Helv., 51:43-55, 1976]:

I discovered theorems 5 and 6, trying to understand Cheng's theorem (Theorem 17) and its possible extension to dimension 3. This theorem was stated in the context of partial differential equations and differential geometry. It took me many years and timely encounters to discover that graph theory was the natural framework for the study of these problems. I was fortunate to benefit in Grenoble from the availability of colleagues in graph theory, in particular François Jaeger (1947-1997), who helped me to discover this subject far away from my original background. It is one of the things I find fascinating in mathematics, these unexpected links between fields that are a priori very far away!

Second quote from Yves Colin de Verdière 1986:

Let $\Gamma_N$ be the complete graph with $N$ vertices ($N\geq4$): each pair of distinct vertices is joined by a single edge. $\Gamma_N$ is considered as a singular Riemannian manifold of dimension 1; if $\cal A$ is the set of $N(N-1)/2$ edges, a Riemannian metric on $\Gamma_N$ is entirely determined (up to isometry) by the length $l(a)$ of any edge $a$ of $\cal A$.

The original quotes are in French

First quote: in SUR LE SPECTRE DES OPÉRATEURS DE TYPE SCHRÖDINGER SUR LES GRAPHES, Exposés à l’Ecole Polytechnique pour les professeurs de Mathématiques Spéciales, Yves Colin de Verdière, 17 mai 2004:
J’ai découvert les théorèmes 5 et 6, en essayant de comprendre le théorème de Cheng (Théorème 17) 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!

Second quote: in Sur la multiplicité de la première valeur propre non nulle du Laplacien, Yves Colin de Verdière, Comment. Math. Helv. 61, 254-270, 1986: Soit $\Gamma_N$ le graphe complet à $N$ sommets ($N\geq4$): chaque couple de sommets distincts est joint par une arête unique. On considère $\Gamma_N$ comme une variété riemannienne singulière de dimension 1; si $\cal A$ est l'énsemble des $N(N-1)/2$ arêtes, une métrique riemannienne sur $\Gamma_N$ est entièrement déterminée (à isométrie près) par la longueur l(a) de toute arête a de si.

Answer 3

The following embeddability characterization for $\mu(G)\le 5$ is merely a conjecture, but I think it fits the question:

Conjecture (van der Holst, [1]): $\mu(G)\le 5$ if and only if $G$ is 4-flat.

A graph is called 4-flat if the following 2-dimensional CW-complex $C(G)$ (PL-) embeds in $\Bbb R^4$: $C(G)$ is obtained from $G$ by attaching a 2-cell along each cycle of $G$.

The 4-flat graphs include all planar and linkless graphs, as well as all cones over such. In fact, these graphs have $\mu(G)\le 5$.

• [1] van der Holst (2006). "Graphs and obstructions in four dimensions".

van der Holst also conjectures the full list of forbidden minors (for either 4-flat or $\mu(G)\le 5$) to consists of the 78 graphs of the Heawood family (graphs obtained from $K_7$ and $K_{3,3,1,1}$ by $\Delta Y$- and $Y\Delta$-tranforms). In fact, all Heawood graphs have $\mu(G)=6$.

Personally, I am somewhat sceptical of the conjectured characterization of $\mu(G)\le 5$, in the sense that if it turns out true, it is most likely a coincidence, in the same way as "linkless $\Leftrightarrow$ $\mu(G)\le 4$" feels like a coincidence that is "only" verified by comparing the list of forbidden minors for linkless and $\mu(G)\le 4$ (slight exaggeration). van der Holst and Pendavingh in [2] even introduced a somewhat more natural graph invariant $\sigma(G)$ that generalizes planarity, linklessness and 4-flatness, but that also diverges from $\mu(G)$ for sufficiently complex graphs. The question is just: are 4-flat graphs already "sufficiently complex"?

• [2] van der Holst, Pendavingh, "On a graph property generalizing planarity and flatness".