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.