Date of Submission
Open Access Senior Thesis
Best Senior Thesis in Mathematics
Bachelor of Arts
2023 Angie Wang
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.
Wang, Angie, "Counting Spanning Trees on Triangular Lattices" (2023). CMC Senior Theses. 3364.