Uniform random spanning trees

We show that the geometry of minimum spanning trees (MST) on random graphs is universal. Due to this geometric universality, we are able to characterise the energy of MST using a scaling distribution ($P(\epsilon)$) found using uniform disorder. We show that the MST energy for other disorder distributions is simply related to $P(\epsilon)$. We discuss the relationship to invasion percolation (IP), to the directed polymer in a random media (DPRM) and the implications for the b...

Measuring the complexity of tree structures can be beneficial in areas that use tree data structures for storage, communication, and processing purposes. This complexity can then be used to compress tree data structures to their information-theoretic limit. Additionally, the lack of models for random generation of trees is very much felt in mathematical modeling of trees and graphs. In this paper, a number of existing tree generation models such as simply generated trees are ...

This extended abstract is dedicated to the analysis of the height of non-plane unlabelled rooted binary trees. The height of such a tree chosen uniformly among those of size $n$ is proved to have a limiting theta distribution, both in a central and local sense. Moderate as well as large deviations estimates are also derived. The proofs rely on the analysis (in the complex plane) of generating functions associated with trees of bounded height.

We prove that the free uniform spanning forest of any bounded degree proper plane graph is connected almost surely, answering a question of Benjamini, Lyons, Peres and Schramm. We provide a quantitative form of this result, calculating the critical exponents governing the geometry of the uniform spanning forests of transient proper plane graphs with bounded degrees and codegrees. We find that the same exponents hold universally over this entire class of graphs provided that...

We give an asymptotic expression for the expected number of spanning trees in a random graph with a given degree sequence $\boldsymbol{d}=(d_1,\ldots, d_n)$, provided that the number of edges is at least $n + \textstyle{\frac{1}{2}} d_{\max}^4$, where $d_{\max}$ is the maximum degree. A key part of our argument involves establishing a concentration result for a certain family of functions over random trees with given degrees, using Pr\"ufer codes.

We consider three probability measures on subsets of edges of a given finite graph $G$, namely those which govern, respectively, a uniform forest, a uniform spanning tree, and a uniform connected subgraph. A conjecture concerning the negative association of two edges is reviewed for a uniform forest, and a related conjecture is posed for a uniform connected subgraph. The former conjecture is verified numerically for all graphs $G$ having eight or fewer vertices, or having nin...

For any edge weight distribution, we consider the uniform spanning tree (UST) on finite graphs with i.i.d. random edge weights. We show that, for bounded degree expander graphs and finite boxes of ${\mathbb Z}^d$, the diameter of the UST is of order $n^{1/2+o(1)}$ with high probability, where $n$ is the number of vertices.

Let ${\mathbf T}_n$ be a uniformly random tree with vertex set $[n]=\{1,\ldots,n\}$, let $\Delta_{{\mathbf T}_n}$ be the largest vertex degree in ${\mathbf T}_n$, and let $\lambda_1({\mathbf T}_n),\ldots,\lambda_n({\mathbf T}_n)$ be the eigenvalues of its adjacency matrix, arranged in decreasing order. We prove that $|\lambda_1({\mathbf T}_n)-\sqrt{\Delta_{{\mathbf T}_n}}| \to 0$ in expectation as $n \to \infty$, and additionally prove probability tail bounds for $|\lambda_1(...

We describe a general approach of determining the distribution of spanning subgraphs in the random graph $\G(n,p)$. In particular, we determine the distribution of spanning subgraphs of certain given degree sequences, which is a generalisation of the $d$-factors, of spanning triangle-free subgraphs, of (directed) Hamilton cycles and of spanning subgraphs that are isomorphic to a collection of vertex disjoint (directed) triangles.

Let $\mathbb{G}^{D}$ be the set of graphs $G(V,\, E)$ with $\left|V\right|=n$, and the degree sequence equal to $D=(d_{1},\, d_{2},\,\dots,\, d_{n})$. In addition, for $\frac{1}{2}<a<1$, we define the set of graphs with an almost given degree sequence $D$ as follows, \[ \mathbb{G}_{a}^{D}:=\cup\,\mathbb{G}^{\bar{D}}, \] where the union is over all degree sequences $\bar{D}$ such that, for $1\leq i\leq n$, we have $\left|d_{i}-\bar{d}_{i}\right|<d_{i}^{a}$. Now, if we chose ...