Upcoming Talks

Ist logo

GeomTop Seminar: short talk "On the Treewidth of Triangulated 3-Manifolds"

Date: Wednesday, May 30, 2018 13:00 - 13:30
Speaker: Kristof Huszar (IST Austria)
Location: Mondi Seminar Room 3, Central Building
Series: Mathematics and CS Seminar
Host: Herbert Edelsbrunner
Contact: WAGNER Hubert

Abstract:

On the Treewidth of Triangulated 3-Manifolds(Kristf Huszr, Jonathan Spreer and Uli Wagner) In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth. In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth. We derive these results from work of Agol and of Scharlemann and Thompson, by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 48(k+1) (resp. 4(3k+1)).
Qr image
Download ICS Download invitation
Back to eventlist