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

• First Presentation
• Second Presentation

---

Additional Information

• My Mentor
  • Dr. Eric Allender
• My Personal Website