We consider the probability that a spanning tree chosen uniformly at random from a graph can be partitioned into a fixed number $k$ of trees of equal size by removing $k-1$ edges. In that case, the spanning tree is called {\em splittable}. Splittable spanning trees are useful in algorithms for sampling {\em balanced forests}, forests whose components are of equal size, and for sampling partitions of a graph into components of equal size, with applications in redistricting, network algorithms, and image decomposition. Cannon et al.~recently showed that spanning trees on grid and grid-like graphs on $n$ vertices are splittable into $k$ equal sized components with probability at least $n^{-2k}$, leading to the first rigorous sampling algorithm for balanced forests in any class of graphs. Focusing on the complementary case of dense random graphs, we show that random spanning trees have inverse polynomial probability of being splittable; specifically, a random spanning tree is splittable with probability at least $n^{(-k/2)}$ for both the $G(n,p)$ and $G(n,m)$ models when $p = Ω(1/\log n)$, giving the first dense class of graphs where partitions of equal size can be sampled efficiently. In addition, we present an infinite family of graphs with properties that have been conjectured to ensure splittability (i.e., Hamiltonian subgraphs of the triangular lattice) and prove that random spanning trees are not splittable with more than exponentially small probability. As a consequence, we show that a family of widely-used Markov chain algorithms for sampling equal-size partitions will fail on this family of graphs if their state spaces are restricted to equal-size partitions. Moreover, we show these algorithms will be inefficient if their state spaces are generalized to include any unbalanced partitions, suggesting barriers for sampling balanced partitions in sparse graphs.

翻译：我们考虑从图中均匀随机选取的生成树，通过移除$k-1$条边后能否被划分为$k$棵大小相等的树。若满足此条件，该生成树称为{\\em 可分割的}。可分割生成树在采样{\\em 平衡森林}（即各连通分量大小相等的森林）以及将图划分为等尺寸分区的算法中具有重要应用，其用途涵盖选区重划、网络算法和图像分解等领域。Cannon等人近期证明，在$n$个顶点的网格及类网格图中，生成树能以至少$n^{-2k}$的概率被分割为$k$个等尺寸分量，这为任意图类中平衡森林的严格采样算法提供了首个理论依据。针对稠密随机图的互补情形，我们证明随机生成树具有逆多项式量级的可分割概率；具体而言，在$p = Ω(1/\\log n)$条件下，$G(n,p)$与$G(n,m)$模型中的随机生成树至少以$n^{(-k/2)}$的概率可分割，这首次给出了能够高效采样等尺寸划分的稠密图类。此外，我们提出一个具有推测可分割性性质的无限图族（如三角晶格的哈密顿子图），并证明随机生成树在该图族中以超指数小概率可分割。由此表明，若将状态空间限制为等尺寸划分，一系列广泛使用的马尔可夫链等尺寸划分采样算法将在此图族中失效。进一步，我们证明即使将状态空间扩展至包含非平衡划分，这些算法仍将低效，这揭示了稀疏图中平衡划分采样的理论障碍。