Kirby Problem 2.10

Definitions and mathematical statement

Let $S$ be a finite-type oriented surface of complexity $3g-3+p\geq1$, where $g$ is its genus and $p$ its number of punctures. Its curve graph $\mathcal C(S)$ has one vertex for each isotopy class of essential nonperipheral simple closed curve, and, at complexity at least two, an edge for disjoint representatives. Every edge has length one; $d_{\mathcal C}$ is shortest-path distance. The customary minimal-intersection adjacency is used for the once-punctured torus and four-punctured sphere.

(a) Find an efficient algorithm computing the exact distance between two input curves. For a uniform complexity question, encode $S$ by a triangulation and curves by normal coordinates in binary; running time should be controlled in the total input length, including surface complexity, rather than only for one fixed surface. Ask the analogous question for the arc graph on a surface with boundary: vertices are isotopy classes of essential properly embedded arcs, with endpoints allowed to move along boundary components, and edges mean representatives with disjoint interiors.

(b) Find algorithms computing distances between effectively described quasiconvex subsets $A,B\subseteq\mathcal C(S)$, where $d(A,B)=\min\{d(a,b):a\in A,b\in B\}$. A subset is quasiconvex if geodesics between its vertices stay within some bounded distance of it. A principal case is the disk set of a handlebody: boundary curves bounding properly embedded disks. For a Heegaard splitting $H_1\cup_S H_2$, compute the distance between its two disk sets from finite handlebody and gluing data. These infinite sets require specified effective descriptions; arbitrary unencoded subsets are not algorithmic inputs.

Short English statement

Compute exact distances in curve graphs efficiently, and develop algorithms for distances between naturally specified infinite subsets, especially the disk sets of Heegaard splittings.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 2758 (KP-2.10), Kirby's Problems in Low-Dimensional Topology. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 K3: A New Problem List in Low-Dimensional Topology, Problem 2.10. Expanded formulation of the supplied catalogue statement. https://math.berkeley.edu/sites/default/files/surv-295-ruberman-watermarked-author-pdf.pdf.