General Information
Project Description
We try to prove that it is NP-hard to decide whether a given 2D simplicial complex can
be linearly embedded into 3D space.
Weekly Log
- Week 1:
-
We tried solving the problem head-on by constructing a polynomial reduction to our problem
from a different NP-hard problem. We tried many possible approaches which turned out not
to be useful since they did not make use of the linearity of the embedding.
- Week 2:
-
We read an article by Ulrich Brehm presenting a triangulation of a Möbius strip which cannot
be linearly embedded in $\R^3$. We discussed the implications: what are the limitations of
linear embeddings of simplicial complexes compared to topological or piecewise linear?
- Week 3:
-
We studied the article by Brehm in greater detail and added the concept of linking number of closed curves
into our toolbox. We found some limitations of linking number values of curves in a linear embedding compared
to a more general embedding.
- Week 4:
-
This week, we have got exciting news! My colleagues Martin and Jakub
finalised a first version of a reduction construction which seems like
it might work. We will attempt to go through the details and rigorously
prove the correctness of our approach in the following weeks
and hopefully we will not encounter any unrepairable mistakes.
- Week 5:
-
- Week 6:
-
- Week 7:
-
Presentations
Additional Information