We show that deciding if a right-angled Artin group is free-by-free is an NP-complete problem. The work is based on an earlier result by Susan Hermiller and the speaker stating that the right-angled Artin group AΓ defined by the graph Γ is free-by-free if and only if Γ is 2-breakable (a graph Γ is 2-breakable if there exists an independent set D of vertices in Γ such that every cycle in Γ contains as least two vertices from D). We reduce the 3SAT Problem to the problem of deciding if a given graph is 2-breakable (in fact, k-breakable, for any fixed k ≥ 1). Once it is shown that the problem is NP-complete, it is not difficult to show that it stays NP-complete even if we restrict it to right-angled Artin groups defined by planar graphs. Note that the more special problem of deciding if a right-angled Artin group is free-by-infinite-cyclic has a very simple answer. Namely, it follows easily from known results that the following three statements are equivalent. (1) AΓ is free-by-infinite-cyclic. (2) Γ is a forest. (3) AΓ embeds in the right angled group defined by the path of length 3. (Joint work with David Carroll and Benjamin Francisco.)
This video is part of the New York Group Theory Cooperative‘s group theory seminar series.
