| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

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.

    1. #4 Splittability and duality on 3D grids


      Add remark

      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$


          Add remark

          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


              Add remark

              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?


                  Add remark

                  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?
                      A group worked on this problem during the workshop.

                    • #21 Splittability with non-constant weights


                      Add remark

                      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


                          Add remark

                          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?
                              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.

                            • #32 Improving bound from $1/N^2$ to $1/N$ on grid graphs


                              Add remark

                              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


                                  Add remark

                                  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?
                                      Micah Gold has answered the first question in the negative, constructing a family of partitions where random spanning trees on any merged pair of parts are exponentially unlikely to be splittable. As of April 2026, this work is not yet available online. The likelihood of such configurations is still an open question.

                                      Cite this as: AimPL: Mathematical foundations of sampling connected balanced graph partitions, available at http://aimpl.org/connectedbalanced.