A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs

Abstract:

For any undirected graph $G$, let $\mu (G)$ be the graph parameter introduced by Colin de Verdière. In this paper we show that $\mu (G)\leq 4$ if and only if $G$ is linklessly embeddable (in $\mathbb {R}^3$). This forms a spectral characterization of linklessly embeddable graphs, and was conjectured by Robertson, Seymour, and Thomas. A key ingredient is a Borsuk-type theorem on the existence of a pair of antipodal linked $(k-1)$-spheres in certain mappings $\phi :S^{2k}\to \mathbb {R}^{2k-1}$. This result might be of interest in its own right. We also derive that $\lambda (G)\leq 4$ for each linklessly embeddable graph $G=(V,E)$, where $\lambda (G)$ is the graph parameter introduced by van der Holst, Laurent, and Schrijver. (It is the largest dimension of any subspace $L$ of $\mathbb {R}^V$ such that for each nonzero $x\in L$, the positive support of $x$ induces a nonempty connected subgraph of $G$.)