*Yale University
Department of Statistics Seminar
Monday, January 28, 2008
**4:15 pm, 24 Hillhouse Avenue, Rm 107

*Nick Reed
Yale University
Physics Department


"Geometry of random minimum spanning trees"

Given a connected finite graph with costs (real numbers) assigned to the edges,
the minimum spanning tree is defined to be an acyclic subgraph
(a tree) that is spanning (meets all the vertices) such that the sum
of the costs of the edges occupied by the tree is minimized. We consider
the random version in which the costs on the edges are independent
random variables, uniformly distributed between 0 and 1. The model
arises physically as the strong-disorder limit of a spin glass. Using Kruskal's
greedy algorithm to solve a random instance leads to a relation with bond
(Bernoulli) percolation on the same graph, which we exploit throughout. We
address the geometry of the random trees when the graph is a portion
of the hypercubic lattice in d dimensions. As a first step, we consider
instead the case in which the graph is the "Bethe lattice" (infinite Cayley tree,
of fixed degree at all vertices). This requires use of "wired" boundary conditions
to obtain a non-trivial minimum spanning forest. We show that the connected
component of the forest containing any given vertex has of order M**3
vertices within M steps of the given vertex. This is interpeted (heuristically)
as implying that in high dimensions (d>6) on the lattice in Euclidean space
the connected components contain R**6 vertices within Euclidean distance R.
Second, we address the fractal dimension of the path connecting any two vertices
on the MST in Euclidean space. (This has been addressed numerically in d=2
dimensions by several other authors.) We set up an expansion for the
related problem in which the Kruskal process is halted at the percolation
threshold, producing a minimum spanning forest. (It has been argued that
the use of this model produces the same result as the MST itself.) Taking
a heuristic continuum limit and using renormalization group methods, we
calculate this dimension to first order in 6-d for d<6 (for d>6, we argue that
it is 2, as for a Brownian random walk).

Work done in collaboration with Tom Jackson (Yale).
_______________________________________________