Research Group
| Seminar | WSU Colloquium
| Department Home

Washington State
University

Combinatorics, Linear Algebra and Number Theory Seminar

Department of Mathematics and Statistics

WEBS 11

January 30, Monday, 4:10 - 5:00 PM

Daryl DeFord

Department of Mathematics and Statistics

Washington State University

Combinatorics, Linear Algebra and Number Theory Seminar

Department of Mathematics and Statistics

WEBS 11

January 30, Monday, 4:10 - 5:00 PM

Daryl DeFord

Department of Mathematics and Statistics

Washington State University

Title: Complexity bounds for sampling connected
graph partitions

Abstract: Applications to political redistricting have motivated interest in the problem of sampling partitions of planar graphs, where the induced subgraphs are constrained to be connected and to contain approximately equal numbers of nodes. While the abstract formulation of this problem is similar to well-studied examples of spin glasses from statistical physics, the imposition of a global constraint means that care must be taken when adopting methods from that setting. In this talk we will use the perspective of self-avoiding walks to explore these connections and analyze phase transitions, asymptotic behavior, and mixing times of the resulting systems. This will allow us to give formal statements about the complexity of this problem and to motivate current work on Markov-based approaches. We will also introduce several related open combinatorial problems and questions combining random graph theory and empirical geographic data.

Abstract: Applications to political redistricting have motivated interest in the problem of sampling partitions of planar graphs, where the induced subgraphs are constrained to be connected and to contain approximately equal numbers of nodes. While the abstract formulation of this problem is similar to well-studied examples of spin glasses from statistical physics, the imposition of a global constraint means that care must be taken when adopting methods from that setting. In this talk we will use the perspective of self-avoiding walks to explore these connections and analyze phase transitions, asymptotic behavior, and mixing times of the resulting systems. This will allow us to give formal statements about the complexity of this problem and to motivate current work on Markov-based approaches. We will also introduce several related open combinatorial problems and questions combining random graph theory and empirical geographic data.