2. Tree Splittability
These questions concern the probability that a random spanning tree is $k$-spittable, meaning that the removal of $(k - 1)$ edges disconnects the tree into $k$ subtrees with (approximately) equal numbers of vertices, or population weight.-
#4 Splittability and duality on 3D grids
Problem 2.1.
[Wesley Pegden] Can we extend the polynomial splittability bound to 3D grids? Specifically, can we get a $\frac{1}{\text{poly}(n)}$ lower bound on splittability into $k = 2$ components of exactly the same numbers of vertices in an $n \times n \times n$ grid graph? What’s the analog for generating the dual of a spanning tree with Wilson’s algorithm? Perhaps there is a different route altogether. -
#5 Combinatorics of splittability on $K_n$
Problem 2.2.
[Dana Randall] There is also a $\frac{1}{\text{poly}(n)}$ lower bound for the probability that a uniformly random spanning tree of an $n$-vertex complete graph is $k$-splittable. If you plot 2-splittability probability as a function of $k$, it’s not unimodal. If it was, then we could prove that we can generalize beyond complete graphs. In more detail, let $a_j$ be the probability that a random spanning tree of $K_n$ is splittable into pieces of size $j$ and $n - j$. This is not unimodal. Can we find a sequence related sequence $b_j$ that is unimodal, or at least that we can come up with a combinatorial argument for computing them, e.g., by establishing injections/bijections relating $b_j$ and $b_{j - 1}$. -
#6 Component sizes on the infinite grid
Problem 2.3.
[Kris Tapp] Consider UST on the infinite grid lattice. If you remove any edge, with probability 1 you get a finite and an infinite component. What does the distribution over finite component sizes look like? -
#11 What makes a tree or graph splittable?
A group worked on this problem during the workshop.Problem 2.4.
[Ann Clifton, Jeanne Clelland, Daryl DeFord] Star graphs are not splittable, paths are. What other structures of trees make it splittable or not splittable? What determines whether a graph is splittable or not splittable? Is there a metric on a tree or a graph that quantifies this? -
#21 Splittability with non-constant weights
Problem 2.5.
[Gabe Schoenbach] Are trees still splittable with polynomial probability when node populations differ by more than a constant amount asymptotically? -
#23 MST vs UST splittability
A group worked on this problem during this workshop and was able to refute (a): there is a graph with 6 vertices where MST trees are more likely to be splittable.Problem 2.6.
[Kris Tapp, Jamie Tucker-Foltz] For a given family of graphs (like grids, complete graphs), what is the assymptotic probability a uniformly random spanning tree versus a random minimal spanning tree is 2-splittable?
(a) Is it true that on any graph a random MST is weakly less likely to be 2-splittable? -
#32 Improving bound from $1/N^2$ to $1/N$ on grid graphs
Problem 2.7.
[org.aimpl.user:jtuckerfoltz@gmail.com] In a uniformly random spanning tree of a grid graph with $N$ vertices, we know the probability of having an exactly balanced split edge is at least $\frac{1}{N^2}$. Can we improve this to $\frac{1}{N}$? Empirically, this seems like the right answer. It would suffice to extend the $\frac{1}{N^2}$ lower bound to a neighborhood of other edges around the central edge. -
#33 ReCom transition function complexity
Problem 2.8.
[org.aimpl.user:jtuckerfoltz@gmail.com] Does the ReCom transition function run in polynomial time? Or can it get stuck in configurations where it is very unlikely a random tree will be splittable? Can we at least show that such configurations are exponentially unlikely?
Cite this as: AimPL: Mathematical foundations of sampling connected balanced graph partitions, available at http://aimpl.org/connectedbalanced.