Graduation Year
2023
Date of Submission
4-2023
Document Type
Open Access Senior Thesis
Award
Best Senior Thesis in Mathematics
Degree Name
Bachelor of Arts
Department
Mathematical Sciences
Reader 1
Sarah Cannon
Rights Information
2023 Angie Wang
Abstract
This thesis focuses on finding spanning tree counts for triangular lattices and other planar graphs comprised of triangular faces. This topic has applications in redistricting: many proposed algorithmic methods for detecting gerrymandering involve spanning trees, and graphs representing states/regions are often triangulated. First, we present and prove Kirchhoff’s Matrix Tree Theorem, a well known formula for computing the number of spanning trees of a multigraph. Then, we use combinatorial methods to find spanning tree counts for chains of triangles and 3 × n triangular lattices (some limiting formulas exist, but they rely on higher level mathematics). For a chain of t triangles, we find and prove an unexpected result: the number of spanning trees is equal to the 2(t + 1)th Fibonacci number. For 3 × n triangular lattices, we provide lower and upper bounds for the spanning tree count by decomposing the larger lattice into smaller subgraphs and analyzing those subgraphs.
Recommended Citation
Wang, Angie, "Counting Spanning Trees on Triangular Lattices" (2023). CMC Senior Theses. 3364.
https://scholarship.claremont.edu/cmc_theses/3364
Data Repository Link
https://github.com/angiewang23/Senior-Thesis-Code
