Correlation of Paths Between Distinct Vertices in a Randomly Oriented Graph - Leander, Madeleine; Linusson, Svante (MATHEMATICA SCANDINAVICA, 2015)
We prove that in a random tournament the events {s→ a} (meaning that there is a directed path from s to a) and {t→ b} are positively correlated, for distinct vertices a,s,b,t K_n. It is also proven that the correlation between the events {s→ a} and {t→ b} in the random graphs G(n,p) and G(n,m) with random orientation is positive for every fixed p>0 and sufficiently large n (with m=p n2floor). We conjecture it to be positive for all p and all n. An exact recursion for P({s→ a} {t→ b}) in G(n,p) is given.