Seminar

In graph theory, as well as three-manifold topology, a wide range of parameters exist to decide how "simple", or "thin", a given graph or three-manifold is. These width-type parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for three-manifolds, play an important role when studying algorithmic problems in the field: There exist several topological problems -- some of them known to be computationally hard in general -- which become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded tree width.

In view of such algorithmic results, the question of whether there exists an explicit link between combinatorial concepts such as treewidth (applicable to a single input triangulation of a given three-manifold M) and results in three-manifold topology (applicable to all possible triangulations of M) has repeatedly been asked by researchers working in the computational branch of three-manifold topology.

In this talk I will present such a link, stating that there exist families of three-manifolds not admitting triangulations of bounded treewidth.