The Random Tree Process

Introduction

The random tree process is a process that produces random trees from random permutations.

Let us first label all edges of a complete graph on n vertices by numbers 1 through n choose 2 in a random fashion so that every labeling has the same probability (this labeling is the random permutation).

Using this permutation, we start building a tree on n vertices: Initially, we have n vertices and no edges. In the k-th step we try to add the k-th edge and see if the the resulting graph contains a cycle. If it does, we skip the edge, else we add it to the graph and repeat for k+1. During this process the graph will remain a forest. After at most n choose 2 steps we will obtain a tree (a connected forest).

An example random tree process

First three steps

The dashed lines represent edges that were considered but skipped.

Last three steps

Note that although we have not considered all the edges yet we do not need to continue: The graph is already a tree and all the other edges will be rejected.

Probability for a star

The distribution of the random trees produced is not uniform: A (labeled) star has the highest probability while a (labeled) path has the lowest probability.

It is known that the probability of obtaining a labeled star on n vertices is 2^{n-1}(n-1)!/(2n-2)!.

A star on 14 vertices
A star on 14 vertices

Our goal

The aim of our project is to find an asymptotic for the probability of obtaining a labeled path. Estimating the probability of the least probable tree would provide us with an insight on how much does the distribution of the random tree process differ from the uniform distribution.

References

S. Gerke, D. Schlatter, A. Steger, A. Taraz: The Random Planar Graph Process.

D. Aldous: A Random Tree Model Associated with Random Graphs, Random Structures Algorithms 1, 386-402, 1990.