- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Returning walks on groups with tree-like Schreier graphs
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Returning walks on groups with tree-like Schreier graphs Aggarwal, Mudit
Abstract
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.
Item Metadata
Title |
Returning walks on groups with tree-like Schreier graphs
|
Creator | |
Supervisor | |
Publisher |
University of British Columbia
|
Date Issued |
2025
|
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.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2025-08-25
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0449866
|
URI | |
Degree (Theses) | |
Program (Theses) | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2025-11
|
Campus | |
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International