Back to search

University of British Columbia

Returning walks on groups with tree-like Schreier graphs

Abstract

dc:description

We study closed walks on an infinite family of vertex-transitive graphs which arise as Schreier coset graphs of group presentations of the form G = 〈 a₁, a₂, . . . , aₖ | a₁ᴾ¹} =· · · = aₖᴾᴷ〉 . This is done by using bivariate generating functions to keep track of the length and the winding number of these walks. It can be observed that counting closed walks on them is equivalent to enumerating group words of a given length, equivalent to the identity. Particularly, the walks with winding number 0 are precisely the group words equivalent to the identity. This enumeration forms the cogrowth series of the group. We then apply the methods of analytic combinatorics by translating the problem of enumerating walks into functional equations for generating functions. Using complex analytic techniques like singularity analysis, asymptotic formulas for the number of closed walks of length n and winding number m can be derived. This is done by proving a local limit theorem in the case when all pᵢs are the same, which requires multiple steps, including pattern theorems, decomposition theorems, and variance bounds. This yields local limit theorems for parts of the graph, and then we analyse the nature and location of singularities to get the overarching local limit theorem. From this, we invoke Jungen's theorem to show that the cogrowth series is not algebraic, which is potentially surprising given that the group presentations are so compact and easy to deal with. Algebraicity of cogrowth series and its connections to group amenability are areas of active interest and research. This thesis makes progress towards the classification of algebraic cogrowth series by proving certain families cannot have algebraic cogrowth. Our work lies at some intersection of analytic and enumerative combinatorics, probability, and group theory. Tools from singularity analysis, transfer theorems, random walks (on groups and graphs), limit laws, and amenability of groups are used to produce precise results about the non-algebraicity of certain cogrowth series.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Mathematics
Grantor dc:publisher
University of British Columbia
Year dc:date
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Aggarwal, Mudit
Contributors dc:contributor
  • Rechnitzer, Andrew

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/92066

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Aggarwal, Mudit. Returning walks on groups with tree-like Schreier graphs. master's thesis, University of British Columbia, 2025. http://hdl.handle.net/2429/92066