Let $G$ be an acyclic directed graph with $MN$ vertices arranged into $M$ generations of $N$ vertices each. We stipulate that edges may only go from generation $j$ to generation $j+1$, so there are $(M-1)N^2$ permissible edges. Each permissible edge is chosen independently with probability $p$, and the resulting subset of permissible edges is used to construct $G$.

The quantity of interest is the probability $P(p)$ that a randomly-chosen vertex $x$ in the first generation of $G$ is connected by a directed path to a random-chosen vertex $y$ in the $M$th generation of $G$. As $N$ becomes large for fixed $M$, one expects a phase transition in $P$ from near $0$ to near $1$ as $p$ crosses some threshold $p_0$.

Question: What is this threshold $p_0$ in terms of $M$ and $N$?

For example, when $M=3$ (first interesting case), it seems that the threshold is $p_0=N^{-\frac{1}{2}}$, and I would guess that $p_0=N^{-\frac{M-2}{M-1}}$ in general.

Is this correct, and how does one prove it? Or where can I find this problem analyzed? I have found many somewhat-relevant sources on percolation, but they mostly involve lattices or Erdös-Rényi graphs.


I have no final answer but this is my progress:

Here is an explicit formula for $P(p)$: $$P(p) = 1 - (1-p^{M-1})^{N^{M-2}}$$

Here $1 - p^{M-1}$ is the probability that a complete path from $v_1$ to $v_M$ is not completely connected and $N^{M-2}$ is the number of possible paths from $v_1$ to $v_M$. (Where $v_i$ is some node in generation $i$).

Inserting $M=3$ and $p_0 = N^{\frac{-1}{2}}$ gives you: $$P(p_0) = 1 - \left(\frac{N-1}{N}\right)^N.$$

Your general formula for $p_0$ will give you: $$P(p_0) = 1 - \left( \frac{K-1}{K} \right)^K$$ where $K := N^{M-2}$

Increasing $p_0$ above that threshold will decrease the subtractor, thus increasing $P(p_0)$, which follows the intuition. Decreasing $p_0$ will decrease the whole expression, thus making $P$ monotonically increasing in $p_0$.

I can't really see a clear transition here. Still curious if you can use that.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.