A random triadic process

Abstract

Given a random 3-uniform hypergraph $H=H(n,p)$ on $n$ vertices where each triple independently appears with probability $p$, consider the following graph process. We start with the star $G_0$ on the same vertex set, containing all the edges incident to some vertex $v_0$, and repeatedly add an edge $xy$ if there is a vertex $z$ such that $xz$ and $zy$ are already in the graph and $xzy \in H$. We say that the process propagates if it reaches the complete graph before it terminates. In this paper we prove that the threshold probability for propagation is $p=\frac{1}{2\sqrt{n}}$. We conclude that $p=\frac{1}{2\sqrt{n}}$ is an upper bound for the threshold probability that a random 2-dimensional simplicial complex is simply connected.

20 pages; some minor corrections