Treewidth & metric complexity for hyperbolic 3-manifolds - Joseph Maher
MAR 06, 2020 | 11:45 AM TO 12:45 PM
The Graduate Center
365 Fifth Avenue
March 06, 2020: 11:45 AM-12:45 PM
Data Science & Topology Seminar
Treewidth is an invariant of graphs which measures how close a graph is to being a tree. A number of algorithms that are exponential over all graphs are polynomial over graphs of bounded tree width. The treewidth of a 3-manifold is the minimal treewidth of the dual graph of any triangulation of the manifold. A number of 3-manifold invariants which are exponential in the number of tetrahedra are polynomial for manifolds of bounded treewidth, for example, the Turaev-Viro invariants. We show that for hyperbolic 3-manifolds, treewidth is linearly related to a metric complexity defined in terms of Morse functions to trees. In particular, this shows that there are 3-manifolds of arbitrarily large treewidth. This is joint work with Diane Hoffoss.