Dgdrxrt

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^-frac12$, and I would guess that $p_0=N^-fracM-2M-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-12$ gives you:
$$P(p_0) = 1 - left(fracN-1Nright)^N.$$

Your general formula for $p_0$ will give you:
$$P(p_0) = 1 - left( fracK-1K 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.