Stephan Zhechev : Embeddability is undecidable outside the meta-stable range
Time: Wed 2019-05-22 11.15 - 12.15
Location: PlacRoom 3418, math department KTH, floor 4 (bottom floor)
Lecturer: Stephan Zhechev, IST Austria
We will prove that the following question is algorithmically undecidable for k+3 < d < 3(k+1)/2 , and k>4, which covers essentially everything outside the meta-stable range: Given a finite simplicial complex K of dimension k and an embedding f : L -> R^d of a subcomplex L of K, can f be extended to an embedding F : K -> R^d of the whole complex? Here, we assume that the given embedding f of the subcomplex L is linear (on each simplex of L) whereas the desired embedding F of the whole complex is allowed to be piecewise-linear (i.e., linear on an arbitrarily fine subdivision of K); moreover F is not required to be part of the output.
More generally, we prove that the question of deciding embeddability, which is the special case of the question above when we set L to be empty, is also undecidable for k+3 < d < 3(k+1)/2 , and k>4.
The strategy of our proof is to construct a reduction from Hilbert’s tenth problem to both the embeddability and extension of embeddings problems. More specifically, for particular types of systems of quadratic Diophantine equations, we will show how to construct corresponding instances of the two problems we consider, so that an embedding or extension exists if and only if the original system of equations has an integer solution. This is a joint work with Uli Wagner and Marek Filakovsky.