### University of Arkansas Topology Seminar: 9/14/2017

### Speaker: Yo'av Rieck

### Title: Embeddability of 2– and 3–complexes in ℝ^{3} is NP-hard

Abstract: for positive integers *d* ≥ *k*, consider the following decision problem: given a (finite) *k*–complex *X*, does *X* embed in ℝ^{d}? This generalizes graph planarity, which is the case *k* = 1, *d* = 2. Known results exhibit a variety of phenomena (a few references are listed):

*d* = 1: is farily easy to see that this is linear.
*d* = 2, *k* = 1 (graph planarity): decidable in linear time (the original algorithm is due to Hopcroft and Tarjan 1974, but has been simplified significantly since).
*d* = 2, *k* = 2: decidable in linear time (J Gross and R Rosen 1979).
*d* ≥ 4, *k* < (2*d*−2)/3: decidable in polynomial time.
*d* ≥ 4, *k* ≥ (2*d*−2)/3: NP-hard (Matoušek, Tancer and Wagner 2011).
*d* ≥ 5, *k* = *d* or *k* = *d*−1: undecidable (Matoušek, Tancer and Wagner 2011).

This leaves wide open the cases *d* = 3 and *k* = 2, *k* = 3. Recently, Matoušek, Sedgwick, Tancer, and Wagner showed that this problem is decidable and, moreover, the two problem are equivalent.

In this talk we will show that these cases are NP-hard. This is joint work with Arnaud de Mesmay, Eric Sedgwick, and Martin Tancer.

BACK TO SCHEDULE