Browsing by Subject "boolean satisfiability"

Sort by: Order: Results:

Now showing items 1-1 of 1
  • Savela, Jarkko (Helsingin yliopisto, 2020)
    This thesis presents a computational study of a fundamental open conjecture in geometric group theory using an intricate combination of Boolean Satisfiability and orderly generation. In particular, we focus on Gromov’s subgroup conjecture (GSC), which states that “each one-ended hyperbolic group contains a subgroup isomorphic to the fundamental group of a closed surface of genus at least 2”. Several classes of groups have been shown to satisfy GSC, but the status of non-right-angled groups with regard to GSC is presently unknown, and may provide counterexamples to the conjecture. With this in mind Kangaslampi and Vdovina constructed 23 such groups utilizing the theory of hyperbolic buildings [International Journal of Algebra and Computation, vol. 20, no. 4, pp. 591–603, 2010], and ran an exhaustive computational analysis of surface subgroups of genus 2 arising from so-called periodic apartments [Experimental Mathematics, vol. 26, no. 1, pp. 54–61, 2017]. While they were able to rule out 5 of the 23 groups as potential counterexamples to GSC, they reported that their computational approach does not scale to genera higher than 2. We extend the work of Kangaslampi and Vdovina by developing two new approaches to analyzing the subgroups arising from periodic apartments in the 23 groups utilizing different combinations of SAT solving and orderly generation. We develop novel SAT encodings and a specialized orderly algorithm for the approaches, and perform an exhaustive analysis (over the 23 groups) of the genus 3 subgroups arising from periodic apartments. With the aid of massively parallel computation we also exhaust the case of genus 4. As a result we rule out 4 additional groups as counterexamples to GSC leaving 14 of the 23 groups for further inspection. In addition to this our approach provides an independent verification of the genus 2 results reported by Kangaslampi and Vdovina.