Vertex reachability in random graph

Question

Given $n$ vertices, one of which is $z$. Consider a uniform random tournament: Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $x$. Let $p_n$ be the probability that any vertex can be reached from $z$ via some directed path. Is it true that $p_n\rightarrow 1$ as $n\rightarrow\infty$?

I suspect this should follow from some known result in random graphs, but not sure which one.

Answer 1

The answer is yes.

$k=1$ is such a "constant", since, as is widely known, a uniform random tournament is asymptotically almost surely strongly connected, and therefore any vertex can be reached from any singleton $A$ you prescribe.

_{I do not see any point to allowing $A$ to have more than vertex. Or rather: if you have a problem which forces you to consider this, then you can be relieved: not only does there exist such a constant, but you can take $k$ to be any constant, essentially by (a slight modification of) the arguments in the reference I now give.}

For your convenience, I now reproduce from

John W. Moon: Topics on TOURNAMENTS in GRAPH THEORY. Dover Publications, Inc. 2015 reprint of the 1968 'Holt, Rinehart and Winston, Inc' version. accessed via a large search engine

the following two-and-a-half very relevant pages.

By combining the implications

($D$ is strong)$\qquad\vdash_{D\colon\mathsf{Tournaments}}\dashv_{D\colon\mathsf{Tournaments}}\qquad\qquad$($D$ is irreducible)

expressed by Theorem 2 in op. cit. with Theorem 1. in op. cit. you should¹ obtain:

• If $p_n$ is the probability in the OP, then for $k=1$ you have, for all $n\geq 2$,

$1 - \frac{n}{2^{n-2}} \left( 1 + \frac{n}{2^{n-1}}\right) < p_n < 1 - \frac{n}{2^{n-2}} \left( 1 - \frac{n}{2^{n-1}}\right)$

Roughly speaking, what you require holds almost surely, and with exponentially fast convergence, and with easily obtainable explicit convergence estimates.

Edit. An alternative answer to the question in the OP.

One should also point out that the above, while valuable because of the structural statement

irreducible$\quad\leftrightarrow_{\text{for.tournaments}}\quad$ strongly.connected,

is more complicated than necessary.

Another, in a sense, more 'probabilist' way (because of the use of Markov's inequality) to answer your question is the following, which will also show that a random tournament a.a.s. is 'very' strongly-connected, in the sense that

asymptotically almost surely each vertex of a random tournament a 2-king.

Intuitively, being a 2-king in a (finished) tournament means that you for any other participant, you either beat them, or you beat someone who beat them. (The latter of course does not imply you beat this other participant, and in a random tournament, half of the time you didn't.)

This can even be passed-off as some sort of a 'paradox', as follows. While standard digraph-theoretic meaning of 'king' is 'has distance $\leq 2$ from any vertex', for the purpose of the 'paradox' and also for the purpose of the application to random tournaments (where the distance-equal-to-1-possibility fails with the uninterestingly large probability $\frac12$), we may focus on the property 'has a directed path of length exactly two to any other vertex' only. We now define

'being a defeater's defeater of participant P' := 'having defeated at least once someone who defeated P'

and

'weak winner' := 'being a defeater's defeater of all the other participants'

Then, as the argument below will show, the following 'paradox' is true:

In a uniform random tournament, everyone is a weak winner.

How this relates to your question: not only can any vertex a.a.s. be reached from $z$, but even be reached via a path of length two.

Since this term is usual in digraph-theory, it would be remiss not to define the term '2-king'.

• For any digraph(=irreflexive binary relation) $D=(V,A)$ and any $v\in V$, let

_{$\mathrm{2king}_D(v)$ true $\quad:\Leftrightarrow\quad$ $\forall x\in V\hspace{5pt}$ $x=v$ $\vee$ $(v,x)\in A$ $\vee$ $\exists y\ $ $(v,y)\in A$ $\wedge$ $(y,x)\in A$}

However, in the argument below, and this is something I have not seen any text state clearly, the clause about there possibly being a length-one-path is irrelevant when discussion random tournaments. Its failure probability is too large anyway. Therefore, we will work with the following weaker predicate

• For any digraph(=irreflexive binary relation) $D=(V,A)$ and any $v\in V$, let

$\mathrm{weakwinner}_D(v)$ true $\quad:\Leftrightarrow\quad$ $\forall x\in V\hspace{5pt}$ $x=v$ $\vee$ $\exists y\ $ $(v,y)\in A$ $\wedge$ $(y,x)\in A$

We will now prove:

Lemma. For a random tournament $D=(n,A)$, asymptotically almost surely $\forall v\in n\colon \mathrm{weakwinner}_D(v)$ is true.

Proof. For each $(x,y)\in V\times V$ let $\mathcal{E}(x,y)$ denote the event that there does not exist any two-arc path from $x$ to $y$. If $x=y$, then the probability of $\mathcal{E}(x,y)$ is $1$ exactly since tournaments do not contain 2-cycles. If $x\neq y$, then by enumerating the relevant models, the probability of $\mathcal{E}(x,y)$ is $(\frac34)^{n-2}$. Since the event

$\mathcal{E}$ $:=$ $\neg$ ($\forall v\in V\colon \mathrm{weakwinner}_D(v)$)

is equal to

$\bigcup_{(x,y)\in V\times V}\mathcal{E}(x,y)$

it follows that by what Wikipedia calls Boole's inequality (and most people I know call 'union bound'), it follows that the probability of $\mathcal{E}$ is

$\leq (n-1)\cdot n\cdot(\frac34)^{n-2}$

which converges to $0$ as $n\to\infty$. This proves the lemma.

(Alternative, more-or-less equivalent argument: use linearity of expectation and Markov's inequality.)

_{1 This step is slightly non-rigorous: it should be easy to prove, though, that the event " $A=\{v_0\}$ is the root of a spanning out-tree of the tournament " is a.a.s. equiprobable with " the tournament is strongly connected ".}