On the complexity of sails. Appendix by Frederick Manners.

DOI10.2140/PJM.2012.258.1MaRDI QIDQ450504zbMATH OpenOpenAlexFDO

Authors Lukas Brantner

Publication date 13 September 2012

Published in Pacific Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.1365, http://msp.org/pjm/2012/258-1/p01.xhtml

zbMATH Keywords

computational geometrycomplexity theorypolyhedraNP-complete problemsNP-hard problemsword lengthsbounded cohomologystable commutator lengthsCalegari algorithmgeneric behaviourP=NPsailsscl

Mathematics Subject Classification ID

Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Generators, relations, and presentations of groups (20F05) Geometric group theory (20F65) Topological methods in group theory (57M07) Commutator calculus (20F12)

Abstract: This paper analyses stable commutator length in groups Z^r * Z^s. We bound scl from above in terms of the reduced wordlength (sharply in the limit) and from below in terms of the answer to an associated subset-sum type problem. Combining both estimates, we prove that, as n tends to infinity, words of reduced length n generically have scl arbitrarily close to n/4 - 1. We then show that, unless P=NP, there is no polynomial time algorithm to compute scl of efficiently encoded words in F2. All these results are obtained by exploiting the fundamental connection between scl and the geometry of certain rational polyhedra. Their extremal rays have been classified concisely and completely. However, we prove that a similar classification for extremal points is impossible in a very strong sense.

Recommendations

• Scl, sails, and surgery
• Stable commutator length is rational in free groups
• Stable commutator length in free products of cyclic groups
• scl.
• Stable commutator length in right‐angled Artin and Coxeter groups

Cited in

(5)

• Stable commutator length in free products of cyclic groups
• Integer hulls of linear polyhedra and scl in families
• Scl, sails, and surgery
• Spectral algebra models of unstable \(v_n\)-periodic homotopy theory
• The \(\bmod\,2\) homology of free spectral Lie algebras

This page was built for publication: On the complexity of sails. Appendix by Frederick Manners.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q450504)