CORRELATIONS FOR PATHS IN RANDOM ORIENTATIONS OF G(n, p) AND G(n,m)

Abstract. We study random graphs, both G(n, p) and G(n,m), with random orien-tations on the edges. For three fixed distinct vertices s, a, b we study the correlation, in the combined probability space, of the events {a → s} and {s → b}. For G(n, p), we prove that there is a pc = 1/2 such that for a fixed p < pc the correlation is negative for large enough n and for p> pc the correlation is positive for large enough n. We conjecture that for a fixed n ≥ 27 the correlation changes sign three times for three critical values of p. For G(n,m) it is similarly proved that, with p = m/