Matstat seminarium fredagen  9 februari, 2001

Long Paths in the Dynamical Graphs

Tatyana Turova, Lund

Abstract:

We study a Markov process whose states are finite directed multi-graphs.
The number of the vertices is described by a supercritical branching
process, and the edges follow a certain mean-field dynamics determined
by the rates of appending and deleting. We find the sufficient conditions
under which the probability of the giant component in the graph tends to
one. A lower bound for the length of this component is also provided.