Constructing presentations of subgroups of right-angled Artin groups

Let G be the right-angled Artin group associated to the flag complex Σ and let π:G → Z be its canonical height function. We construct an algorithm that, given n and for Σ, outputs a presentation for Γn= π-1(nZ) of optimal deficiency on a minimal generating set, provided Σ is triangle-free; the deficiency tends to infinity as n → ∞ if and only if the corresponding Bestvina-Brady kernel bigcap (Formula presented) is not finitely presented, and the algorithm detects whether this is the case. We explain why there cannot exist an algorithm that constructs finite presentations with these properties in the absence of the triangle-free hypothesis. We also prove, for general Σ, that the abelianized deficiency of Γn tends to infinity if and only if Σ is 1-acyclic, and discuss connections with the relation gap problem. © 2013 Springer Science+Business Media Dordrecht.