Properties of a specific type of random network

Question

Suppose I have a directed network constructed in the following way: There are $n$ vertices. Each vertex has $e$ out-edges, which point to other vertices chosen uniformly at random. (If it matters, I'm generally working with smaller $e$.)

First question, does this type of graph have a name? Keywords for searching would be helpful.

Specific questions:

1. Suppose I choose a subset $T$ of vertices of size $s$. What is the probability that there is a path from every node outside of $T$ to at least one node in $T$?

2. Suppose two non-overlapping subsets of vertices both of size $s$. What is the probability that a single node has a path to one but not the other?

It's easy enough to solve numerically, which I can do on my own. But I was wondering if this was already studied and could be determined exactly.

Thanks for your help!

Answer 1

The case $k=1$ is very special: we are looking at a random function $f : \{1, 2, \dots, n\} \to \{1,2,\dots,n\}$, and lots of the dynamics change. It's much likelier that there will be multiple large components.

For $k\ge 2$, and asymptotically as $n \to \infty$, the first probability already goes to $0$ for some $s = O(\log n)$. I've given some bounds that go to $0$ below, not very quickly. We can get better bounds of the form $\frac1{n^C}$ for any constant $C$ by doing things more carefully, and varying the constant in $O(\log n)$. So certainly when $s$ is a constant fraction of $n$, the probability goes to $0$.

This tells us that actually, every vertex reaches almost all others, so for your second question, the probability is essentially the same as the probability a vertex $v$ cannot reach a set of size $s$. There's more to be said on what the probability is for a very small $s$; I can expand on that if you're interested.

---

I'll begin with a slightly different question: if there are no edges from a set $S$ to $V-S$, how large can $S$ be? Clearly, $|S| \ge k+1$, since each vertex in $S$ has edges to at least $k$ more.

When $|S|=r$, there are $\binom nr \le (\frac{ne}{r})^r$ ways to choose $S$. For a vertex $v \in S$, the first edge we choose out of $v$ has a $\frac{r-1}{n-1} < \frac rn$ chance of landing in $S$; after that, the probability decreases (because we can't pick the same edge twice) so this is an upper bound for all edges. So the probability is at most $(\frac rn)^{kr}$ that all edges out of vertices in $S$ go back to $S$. The expected number of such sets of size $r$ is at most $(\frac{ne}{r})^r (\frac rn)^{kr} = (e(\frac rn)^{k-1})^r$.

Let's look at this for various ranges of $r$:

• For $r = o(n)$, say for concreteness $r \le \sqrt n$, we get $e(\frac rn)^{k-1} < \frac{e}{\sqrt n}$. The sum over all such $r$ is bounded by $\sum_{r=1}^\infty (\frac{e}{\sqrt n})^r = \frac{e/\sqrt n}{1 - e/\sqrt n} = (1+o(1))\frac e{\sqrt n}$, which goes to $0$ as $n \to \infty$. We could actually give sharper bounds, since the dominant terms are the first few, and $\frac rn$ is much smaller for those. Not to mention that we've just used $k \ge 2$ here instead of the actual value of $k$.
• For $\sqrt n < r < 0.1n$, say, we get $(e(\frac rn)^{k-1})^r < (0.1e)^r < (0.1e)^{\sqrt n}$, so the sum over all such $r$ is at most $0.1n (0.1e)^{\sqrt n}$, which also goes to $0$ as $n \to \infty$. Actually, the constant $0.1$ can be anything less than $e^{-1/(k-1)}$.

So now suppose we're looking at a set $T$ of $s$ vertices in your problem. We know all vertices outside $T$ expand to reach at least $0.1n$ vertices with high probability. The probability such a vertex has no path to $T$ is less than $(1 - \frac sn)^{0.1kn}$. Using the inequality $1+x \le e^x$, this is at most $e^{-0.1ks}$. Just taking $s = 10 \log n$, we already get a bound of $\frac1{n^2}$ for all $k\ge2$, which still is less than $\frac1n$ (and therefore going to $0$) if we take the very weak union bound over all vertices $v$ outside $T$.

On the other hand, for very small $s$, there's a good chance that there are no edges to $T$, which is the easiest way for the event we want to happen. Specifically, that probability is $(1+o(1))(1 - \frac sn)^{kn} \sim e^{-ks}$. That's not the whole story: the set not reachable from anywhere else could be a bit bigger than $T$. But it says something about the size of the set we're looking at, if we want the probability to be non-negligible.