Even maps, the Colin de~Verdi\`ere number and representations of graphs

Van der Holst and Pendavingh introduced a graph parameter $\sigma$, which coincides with the more famous Colin de Verdi`{e}re graph parameter $\mu$ for small values. However, the definition of $\sigma$ is much more geometric/topological directly reflecting embeddability properties of the graph. They proved $\mu (G)\le \sigma (G)+2$ and conjectured $\mu(G) \leq \sigma(G)$foranygraph$G$. We confirm this conjecture. As far as we know, this is the first topological upper bound on $\mu (G)$ which is, in general, tight. Equality between $\mu$ and $\sigma$ does not hold in general as van der Holst and Pendavingh showed that there is a graph $G$ with $\mu (G)\le 18$ and $\sigma (G)\ge 20$. We show that the gap appears on much smaller values, namely, we exhibit a graph $H$ for which $\mu (H)\le 7$ and $\sigma (H)\ge 8$. We also prove that, in general, the gap can be large: The incidence graphs $H_q$ of finite projective planes of order $q$ satisfy $\mu(H_q) \in O(q^{3/2})$and$\sigma(H_q) \geq q^2$.