Geometry, Topology, and Physics Seminar, Winter 2020

Organizers: Dave Morrison and Zhenghan Wang.
Meets 4:00 - 5:30 p.m. on selected Fridays in South Hall 6635.

January 10

### Embeddability of simplicial complexes is undecidable

We consider the following decision problem EMBED(k,d) in computational topology (where k \leq d are fixed positive integers): Given a finite simplicial complex K of dimension k, does there exist a (piecewise-linear) embedding of K into R^d?

The special case EMBED(1,2) is graph planarity, which is decidable in linear time, by the well-known algorithm of Hopcroft and Tarjan.

In higher dimensions, EMBED(2,3) and EMBED(3,3) are known to be decidable (as well as NP-hard), and recent results of Čadek et al., in combination with a classical theorem of Haefliger and Weber, imply that EMBED(k,d) can be solved in polynomial time for any fixed pair (k,d) of dimensions in the so-called \emph{metastable range} $d\geq (3(k+1))/2$.

Here, by contrast, we prove that EMBED(k,d) is algorithmically undecidable for almost all pairs of dimensions outside the metastable range, namely for $8\leq d<\floor{(3(k+1))/2}$. This almost completely resolves the decidability vs.\ undecidability of EMBED(k,d) in higher dimensions and establishes a sharp dichotomy between polynomial-time solvability and undecidability.

Our proof builds on work by Čadek et al., who showed how to encode an arbitrary system of Diophantine equations into a homotopy-theoretic extension problem. We turn their construction into an embeddability problem, using techniques from piecewise-linear (PL) topology due to Zeeman, Irwin, and others.

January 24

### A deformation invariant of 2D SQFTs

The elliptic genus is a powerful deformation invariant of 2D SQFTs: if it is nonzero, then it protects the SQFT from admitting a deformation to one with spontaneous supersymmetry breaking. I will describe a "secondary" invariant, defined in terms of mock modularity, that goes beyond the elliptic genus, protecting SQFTs with vanishing elliptic genus. The existence of this invariant supports the hypothesis that the space of minimally supersymmetric 2D SQFTs provides a geometric model for universal elliptic cohomology. Based on joint works with D. Gaiotto and E. Witten.