Abstract:
A cover in $R^d$ is a set of open domains $U=\{U_1,\dots,U_n\}$ in $R^d$. Their nerve is a simplicial complex $N(U)$ whose $k$-dimensional faces correspond to collections of $k$ open domains in $U$ which have nonempty intersection, with natural incidence of faces.
A cover $U$ is said to be convex if all $\{U_i\}$ are convex. A cover $U$ is said to be good if the intersection of any collection of domains in $U$ is empty or contractible. For good/convex covers, the well-known nerve theorem states that $N(U)$ is homotopy equivalent to the union of all $\{U_i\}$.
The following problem was raised by specialists in combinatorics: given a simplicial complex and an integer $d$, to determine whether it is a nerve of a convex/good cover in $R^d$. For convex covers, this problem is algorithmically solvable and is NP-hard (Wegner 1967, Kratochvil–Matousek 1994). For good covers, the algorithmic status of the problem remained unknown up to now, although many results on necessary conditions for a complex to be a nerve of a good cover were known (e.g., Alon, Kalai, Matousek, Meshulam 2002). We prove that for good covers, the problem is algorithmically undecidable for $d\ge5$. Our proof relies on Novikov's result on algorithmic unrecognizability of the $d$-dimensional sphere, $d\ge5$.
|
