Finding Periodic Apartments : A Computational Study of Hyperbolic Buildings

Show full item record

Title: Finding Periodic Apartments : A Computational Study of Hyperbolic Buildings
Author: Savela, Jarkko
Other contributor: Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta
University of Helsinki, Faculty of Science
Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten
Publisher: Helsingin yliopisto
Date: 2020
Language: eng
Thesis level: master's thesis
Discipline: Matematiikka
Abstract: 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.
Subject: sat
combinatorial generation
orderly algorithm
boolean satisfiability
hyperbolic buildings
geometric group theory

Files in this item

Total number of downloads: Loading...

Files Size Format View
savela_jarkko_tutkielma_2020.pdf 1.255Mb PDF View/Open

This item appears in the following Collection(s)

Show full item record