1. Markov Chains
These questions concern Markov chains for sampling trees and graph partitions. Key questions include ergodicity, mixing times, and methods to sample from specific distributions, e.g., using the Metropolis-Hastings algorithm.-
#1 ReCom ergodicity
It is known that 3-district ReCom is ergodic on a triangular subset of the triangular lattice with $\pm 1$ balance constraints, restricting to simply connected districts [Cannon, 2023]. A forthcoming work proves the same statement for a rectangular subset of the grid lattice. Below is an alternative proof approach, which might be more easily extended.Problem 1.1.
[Hugo Akitaya] -
(a) Given a map, take the two districts with the largest shared perimeter, then redraw to minimize boundary. Does this process eventually terminate in a simple, Voronoi-like partition (for instance, possibly, the partition minimizing cut edges)? This would imply ergodicity. Or does it get stuck?
(b) Does this policy at least eventually give you a district that is $x$-monotone (AKA "vertically convex," no gaps in any vertical slice)? If so, a theorem from the forthcoming paper says that a constant number of steps will suffice to get you to a simple canonical partition, like the Italian flag. This would also prove ergodicity.
(c) How do you efficiently compute the shortest boundary at each step in this process? This might be solved by a paper called. There is a paper that solves this in $O(n^5)$ time without the requirement that districts are connected [Papadimitriou and Sideri, 1996]. -
#7 MST ReCom
Problem 1.2.
[Jamie Tucker-Foltz, Wesley Pegden, Jonathan Mattingly] Running ReCom with random minimal spanning trees (i.e., drawing trees using Kruskal’s algorithm with random weights):
(a) Can we modify the algorithm so that we get a nice (approximate) description of the distribution we are sampling from?
(b) Can we at least calculate forward and backward probabilities so we can use Metropolis-Hastings? -
#9 Other (Metropolized) chains for small perimeter
Problem 1.3.
[Jonathan Mattingly] Can we find other Metropolis-Hasting schemes besides UST RevReCom to sample partitions with small perimeters, for instance under the isoparametric ratio or Polsby-Popper score? Is the cycle walk a good candidate? One can at least calculate the forward and backward probabilities for that. -
#19 ReCom rapid mixing on restricted graph families
A group worked on this question during the workshop. It was able to prove rapid mixing on complete graphs, as well as asymptotically tight upper and lower bounds on the diameter of the state space. This group also led to a new open question about a different Markov chain, #34 below.Problem 1.4.
[Eyob Tsegaye] Can we prove ReCom mixes rapidly on some families of graphs? Triangular/square lattice? Complete graphs? Dense random graphs? -
#20 Cycle walk rapid mixing on restricted graph families
The cycle walk is a "lifted" alternative of ReCom where we keep track of the tree in each part. A step is allowed to recombine a pair of partitions by adding two edges between two adjacent parts and then removing two edges.Problem 1.5.
[Jonathan Mattingly] Can we prove the cycle walk mixes rapidly on some families of graphs? -
#34 Cycle walk variant on splittable trees
A group worked on this question during the workshop, finding a characterization of the kinds of moves that this walk can induce on partitions. as well as counterexamples showing that this walk is logically incomparable to ReCom. There can be isolated states on arbitrary graphs even for $k = 2$.Problem 1.6.
[Gregory Herschlag] Suppose we run the up-down walk but restrict to trees that are k-splittable. Is this Markov chain ergodic, and if so, does it mix rapidly?
Cite this as: AimPL: Mathematical foundations of sampling connected balanced graph partitions, available at http://aimpl.org/connectedbalanced.