Uniform spanning tree

In mathematics, loop-erased random walk is a model for a random simple path with important applications in combinatorics and, in physics, quantum field theory. It is intimately connected to the uniform spanning tree, a model for a random tree. See also random walk for more general treatment of this topic.

Assume G is some graph and ${\displaystyle \gamma }$ is some path of length n on G. In other words, ${\displaystyle \gamma (1),\dots ,\gamma (n)}$ are vertices of G such that ${\displaystyle \gamma (i)}$ and ${\displaystyle \gamma (i+1)}$ are connected by an edge. Then the loop erasure of ${\displaystyle \gamma }$ is a new simple path created by erasing all the loops of ${\displaystyle \gamma }$ in chronological order. Formally, we define indices ${\displaystyle i_{j}}$ inductively using

...
Wikipedia