Even maps, the Colin de~Verdière number and representations of graphs

Abstract

Van der Holst and Pendavingh introduced a graph parameter $\sigma$, which coincides with the more famous Colin de Verdiè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)\le \sigma (G)$ for any graph $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)\ge q^2$.

28 pages, 4 figures. In v2 we slightly changed one of the core definitions (previously "extended representation" now "semivalid representation"). We also use it to introduce a new graph parameter, denoted eta, which did not appear in v1. It allows us to establish an extended version of the main result showing that mu(G) is at most eta(G) which is at most sigma(G) for every graph G

References in corpus (2)

• Lectures on 0/1-polytopes
• Good covers are algorithmically unrecognizable