Presented by: 
Jonathan Spreer, UQ
Date: 
Tue 9 Aug, 3:00 pm - 4:00 pm
Venue: 
67-442
Tightness is a generalisation of the notion of convexity: a space is tight if and only if it is "as convex as possible", given its topological constraints. For a simplicial complex, deciding tightness has a straightforward exponential time algorithm, but efficient methods to decide tightness are only known in the trivial setting of triangulated surfaces.
In this talk I present a new polynomial time procedure to decide tightness for triangulations of 3-manifolds -- a problem which previously was thought to be hard. Moreover, I describe an algorithm to decide tightness in the case of 4-dimensional combinatorial manifolds which is fixed parameter tractable in the treewidth of the 1-skeletons of their vertex links, and I discuss why similar shortcuts are unlikely to exist in higher dimensions.