- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Abelian girth and gapped sheaves
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Abelian girth and gapped sheaves Izsak, Alice
Abstract
The girth of a graph is the length of the shortest cycle in a graph, and the abelian girth of a graph is the girth of the graph's universal abelian covering graph. We denote the abelian girth of a graph G as Abl(G) and show that for d-regular graphs on n vertices with d constant and n growing we have Abl(G) ≤ 6 log_{d-1} n plus a vanishing term. This can be seen as a version of the Moore bound for abelian girth. We also prove Girth(G) ≤ Abl(G)/3, which implies that any multiplicative improvement to the abelian girth Moore bound would also improve the standard Moore bound. Sheaves on graphs and two of their homological invariants, the maximum excess and the first twisted Betti number, were used in the proof of the Hanna Neumann Conjecture from algebra and may be of use in proving several related unresolved conjectures. These conjectures can be proven if certain sheaves called ρ-kernels have vanishing maximum excess. Ungapped sheaves have maximum excess equal to the first twisted Betti number, and it is easy to compute the maximum excess of a given sheaf in the case that the sheaf is not gapped. For general sheaves though, there is no known way of computing the maximum excess in polynomial time. We give several conditions that gapped sheaves must satisfy. These conditions include that a gapped sheaf must have edge dimension at least as large as the abelian girth of the underlying graph. The ρ-kernels are subsheaves of constant sheaves. We prove that gapped subsheaves of constant sheaves exist, implying that finding maximum excess of some ρ-kernels may be computationally difficult.
Item Metadata
Title |
Abelian girth and gapped sheaves
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2015
|
Description |
The girth of a graph is the length of the shortest cycle in a graph, and the abelian girth of a graph is the girth of the graph's universal abelian covering graph. We denote the abelian girth of a graph G as Abl(G) and show that for d-regular graphs on n vertices with d constant and n growing we have Abl(G) ≤ 6 log_{d-1} n plus a vanishing term. This can be seen as a version of the Moore bound for abelian girth. We also prove Girth(G) ≤ Abl(G)/3, which implies that any multiplicative improvement to the abelian girth Moore bound would also improve the standard Moore bound. Sheaves on graphs and two of their homological invariants, the maximum excess and the first twisted Betti number, were used in the proof of the Hanna Neumann Conjecture from algebra and may be of use in proving several related unresolved conjectures. These conjectures can be proven if certain sheaves called ρ-kernels have vanishing maximum excess. Ungapped sheaves have maximum excess equal to the first twisted Betti number, and it is easy to compute the maximum excess of a given sheaf in the case that the sheaf is not gapped. For general sheaves though, there is no known way of computing the maximum excess in polynomial time. We give several conditions that gapped sheaves must satisfy. These conditions include that a gapped sheaf must have edge dimension at least as large as the abelian girth of the underlying graph. The ρ-kernels are subsheaves of constant sheaves. We prove that gapped subsheaves of constant sheaves exist, implying that finding maximum excess of some ρ-kernels may be computationally difficult.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2016-01-08
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivs 2.5 Canada
|
DOI |
10.14288/1.0223486
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2016-02
|
Campus | |
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivs 2.5 Canada