Results on spanning trees and the free uniform spanning forest, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• The formula of Cauchy and Binet — Lemma 2.1. The determinant of the product of a matrix with r rows and n columns and a matrix with n rows and r columns is the sum, over the sets of r indices, of the products of the corresponding minors.
• The weighted matrix-tree theorem — Theorem 3.1. For a finite connected graph with positive edge weights, the determinant of the reduced weighted Laplacian is the sum over the spanning trees of the products of the weights of their edges.
• Inclusion probabilities and covariances of a weighted spanning tree — Proposition 4.2. For the random spanning tree with probability proportional to the product of the edge weights, the probability of an edge e is c_e a_e^T L^-1 a_e, and the covariance of the indicators of two different edges is -c_e c_f (a_e^T L^-1 a_f)^2, which is not positive.
• The response identity for weighted spanning trees — Theorem 5.1. The absolute values of the derivatives of the inclusion probability of an edge with respect to the logarithms of the weights of all edges add up to 2 p_e (1 - p_e), which is at most 1/2.
• Lipschitz dependence on the logarithms of the weights — Corollary 5.2. If the logarithms of the weights are changed by at most epsilon, every inclusion probability of an edge in the weighted random spanning tree changes by at most epsilon/2.
• The determinant identity det(I + UV) = det(I + VU) — Lemma 1.1. For a matrix U with r rows and k columns and a matrix V with k rows and r columns, det(I_r + UV) = det(I_k + VU).
• Inclusion probabilities of the uniform spanning tree as determinants — Theorem 1.2. For the uniform spanning tree T of a finite connected graph H and every set F of edges, P(F is contained in T) is the determinant of the entries with indices in F of the matrix K_H = A^T (A A^T)^-1 A, where A is the reduced incidence matrix.
• The matrix of the uniform spanning tree is a projection — Proposition 2.1. K_H is the orthogonal projection onto the orthogonal complement of the space of circulations of H; it does not depend on the vertex that is left out.
• Circulations are spanned by cycle flows — Lemma 2.2. The space of circulations of a finite connected graph is spanned by the cycle flows.
• Convergence of the projections along an exhaustion — Proposition 3.1. For an exhaustion of an infinite connected graph with finite degrees by finite connected subgraphs, the projections onto the spaces of circulations converge strongly to the projection onto the closed span of the cycle flows, and the matrices K_n converge entry by entry to K = I - P_C.
• The free uniform spanning forest — Theorem 4.1. For an infinite connected graph with finite degrees there is exactly one probability measure on the sets of edges with P(F contained) = det K_F for all finite F; the laws of the uniform spanning trees of every exhaustion converge to it on cylinders; it has no cycles almost surely, and it is carried along by isomorphisms of graphs.
• A tilt is the conditional law given Gaussian observations — Proposition 2.1. For a law on {0,1}^I, a finite set S and t > 0, let Y_f = t X_f + sqrt(t) N_f for f in S with independent standard normal N_f independent of X. Then Y has the density Z_S(t, y) times the product of normal densities, and the tilted probability b_{i,S}(t, Y) is the conditional probability of X_i = 1 given Y.
• The response bound for tilts of the free uniform spanning forest — Lemma 3.1. For the free uniform spanning forest of an infinite connected graph with finite degrees, every edge e, every finite set S of edges and t >= 0, the tilted probability of e changes by at most half the largest change of the numbers y_f, f in S.
• The neighbourhoods of an edge form an exhaustion — Lemma 4.1. For an edge e = {u, v}, the subgraphs spanned by the vertices at distance at most n from u or v are finite, connected, increasing, and contain every edge for large n.
• The drift of the free uniform spanning forest — Proposition 4.3. The drift b_e(t, y), the upper limit of the tilted probabilities of e along the neighbourhoods of e, is a Borel function with values in [0, 1]; it changes by at most half the supremum of |y_f - y'_f| when this supremum is finite; and it respects isomorphisms of graphs.
• The integral equation of a drift has exactly one solution — Theorem 2.1. Let b = (b_i) be Borel functions on [0, infinity) x R^I with values in [0, 1] such that sup_i |b_i(t, y) - b_i(t, y')| <= L sup_j |y_j - y'_j| whenever the right side is finite. Then for every family w of continuous paths there is exactly one family Z of continuous paths with Z_i(t) = w_i(t) + integral from 0 to t of b_i(s, Z(s)) ds for all i and t.
• Causality and relabelling of the solution map — Proposition 3.1. The solution on [0, T] depends only on the paths w on [0, T]; a bijection of the index sets that carries one drift to another carries the solution map to the solution map.
• Integrals with a parameter are measurable — Lemma 4.1. For a measurable function g on [0, t] x Omega with values in [0, 1], where Omega is any measurable space, the integral of g(s, omega) ds over [0, t] is a measurable function of omega.
• The solution map is measurable — Theorem 4.3. For a drift with a constant L, the solution map on families of continuous paths is measurable for the sigma-algebra generated by the evaluations.

Reading order

Four lessons so far, with complete proofs: weighted spanning trees of finite graphs; the free uniform spanning forest of an infinite graph as the limit of uniform spanning trees; the tilts of the forest and its drift; the integral equation of the drift. The theorem on factors of independent labels needs Brownian motion and is not yet in the course.