On the complexity of sails. Appendix by Frederick Manners.

DOI10.2140/PJM.2012.258.1zbMATH Open1282.20044arXiv1102.1365OpenAlexW2082698914MaRDI QIDQ450504FDOQ450504

Authors: Lukas Brantner 

Publication date: 13 September 2012

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

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.

Full work available at URL: https://arxiv.org/abs/1102.1365

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

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)

Cited In (5)

• Stable commutator length in free products of cyclic groups
• Scl, sails, and surgery
• Integer hulls of linear polyhedra and scl in families
• 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)