Graduation Year

2025

Date of Submission

4-2025

Document Type

Campus Only Senior Thesis

Degree Name

Bachelor of Arts

Department

Mathematical Sciences

Reader 1

Dr. Sarah Cannon

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Abstract

This thesis investigates balanced partitions of spanning trees in triangular lattice graphs, extending previous work on grid graphs. The study of spanning tree partitions has applications in randomized algorithms and graph-based sampling techniques. First, we review foundational results on spanning trees in grid graphs, including probability bounds for obtaining balanced partitions when dividing a graph into two components. Then, we extend these methods to triangular lattices. Specifically, for a hexagonal region of a triangular lattice graph with a partition, we seek to establish a minimum probability that a randomly selected spanning tree can be divided into two balanced components. By adapting spanning tree distribution techniques, using a careful study of random walks, and employing combinatorial probability bounds, we provide theoretical guarantees for balanced partitions in triangular lattices. These results contribute to both theoretical graph analysis and practical applications in randomized algorithms and partition-based sampling methods. This research holds potential applications in redistricting electoral districts in the United States, equipping statisticians and political scientists with a framework for evaluating electoral boundary fairness.

Download

This thesis is restricted to the Claremont Colleges current faculty, students, and staff.

Share

COinS