Conjecture of van der Holst and Pendavingh related to bound for Colin de Verdière invariant

Question

In their 2009 paper (“On a graph property generalizing planarity and flatness”. In: Combinatorica 29.3 (May 2009), pp. 337–361. issn: 1439-6912. doi: 10.1007/s00493-009-2219-6.), van der Holst and Pendavingh defined a new minor monotone graph invariant $\sigma(G)$ for a graph $G$: the minimal integer $k$ such that every CW-complex whose 1-skeleton is $G$ admits a certain even mapping into $\mathbb R^k$.

They were able to prove $\mu(G)\leq\sigma(G)+2$, where $\mu(G)$ is the Colin de Verdière number of $G$ which is minor monotone as well (Colin de Verdière. “Sur un nouvel invariant des graphes et un critère de planaritè”. In: Journal of Combinatorial Theory, Series B 50.1 (1990), pp. 11–21. issn: 0095-8956. doi: 10.1016/0095-8956(90)90093-F.)

My main interest is in the conjecture of van der Holst and Pendavingh in that paper. They conjectured that actually $\mu(G)\leq\sigma(G)$ might hold. Question: What is known about the status of this conjecture? (I have difficulties tracing it as their new invariant $\sigma(G)$ does not seem to have a commonly agreed name yet).

Answer 1

Kaluza and Tancer have actually proved $\mu(G)\leq\sigma(G)$ in 2019: See their proof in the preprint "Even maps, the Colin de Verdière number, and representations of graphs" on arxiv. Here is the link https://arxiv.org/pdf/1907.05055.pdf

You are right, the invariant $\sigma(G)$ of Holst and Pendavingh does not seem to have an established name yet.

Answer 2

I would like to add one important aspect: it was known that $\mu(G)$ and $\sigma(G)$ can deviate by a large amount for larger values $k$. Now we have the proof of the improved (sharper) bound $\mu(G)\leq\sigma(G)$, but even though this is an improvement, Kaluza and Tancer also showed that a large gap exists already for small values of $k$: They showed there is a graph $G$ such that $\mu(G)\leq7$ and $\sigma(G)\geq8$ ("Even maps, the Colin de Verdière number, and representations of graphs" on arxiv. Here is the link https://arxiv.org/pdf/1907.05055.pdf).
Now, a suspension of $G$ (adding a new vertex to $G$ and connecting it to all vertices of $G$) increases both $\mu(G)$ and $\sigma(G)$ by exactly one (unless $G$ is the complement of $K_2$). Therefore $\mu(G)\leq7$ and $\sigma(G)\geq8$ implies that for every $k \in\mathbb N$, $k \geq 7$, there must exist a graph $G_k$ with $\mu(G)\leq k$ and $\sigma(G)\geq k+1$, i.e. strict inequality for all large values of $k$. Finally, the authors also show that the gap between $\mu(G)$ and $\sigma(G)$ is asymptotically large.