Finding Periodic Apartments : A Computational Study of Hyperbolic Buildings

Visa fullständig post

Titel: Finding Periodic Apartments : A Computational Study of Hyperbolic Buildings
Författare: Savela, Jarkko
Medarbetare: Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten
Utgivare: Helsingin yliopisto
Datum: 2020
Språk: eng
Permanenta länken (URI):
Nivå: pro gradu-avhandlingar
Ämne: Matematiikka
Abstrakt: 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

Filer under denna titel

Totalt antal nerladdningar: Laddar...

Filer Storlek Format Granska
savela_jarkko_tutkielma_2020.pdf 1.255Mb PDF Granska/Öppna

Detta dokument registreras i samling:

Visa fullständig post