The complexity of pinning loops in the sphere

Meeting Details

For more information about this meeting, contact Rachel Weaver, Dmitri Burago, Anton Petrunin, Joshua Paik.

Speaker: Christopher-Lloyd Simon via ZOOM https://psu.zoom.us/j/92989012308, PSU

Abstract: In a punctured sphere $S-P$, consider homotopy class of loops $C$. Some of its generic representatives $c$ are simpler than others: a result of Neumann-Coto says that $c$ is isotopic to a shortest geodesic for a complete Riemannian metric on $S-P$ if and only if it is taut (realizes the minimal number of double-points in its homotopy class $C$). We investigate the inverse problem: given a generic isotopy class $c$ in the sphere $S$, where should we place the "pins" $P$ to ensure that it is taut, and how many do we need? We show that it is NP-complete to bound this "pinning number". On the one hand, we provide two separate polynomial algorithms to check if a given set of points is pinning. The first relies on combinatorial group theory, adapting a method of Birman--Series for computing intersection numbers of curves in surfaces. The second relies on geometric topology, improving a characterisation of taut loops by Hass--Scott to convert the pinning number problem into a Boolean formula. On the other hand, we reduce the planar vertex cover problem for graphs to the pinning problem for loops in the sphere. This is based on joint work with Ben Stucky.

---

Room Reservation Information

Room Number: 114 McAllister

Date: 10/30/2024

Time: 12:10pm - 1:30pm