# Phase transition threshold for acyclic directed graph

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.

## 1 Answer

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.