Treewidth & metric complexity for hyperbolic 3-manifolds - Joseph Maher

MAR 06, 2020 | 11:45 AM TO 12:45 PM

Details

WHERE:

The Graduate Center
365 Fifth Avenue

ROOM:

4419

WHEN:

March 06, 2020: 11:45 AM-12:45 PM

ADMISSION:

Free

SPONSOR:

Data Science & Topology Seminar

Description

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.