First critical probability for a problem on random orientations in $G(n,p)$.

Sven Erick Alm (Uppsala Universitet)
Svante Janson (Uppsala Universitet)
Svante Linusson (KTH- Royal Institute of Technology)


We study the random graph $G(n,p)$ with a random orientation. For three fixed vertices $s,a,b$ in $G(n,p)$ we study the correlation of the events $\{a\to s\}$ (there exists a directed path from $a$ to $s$) and $\{s\to b\}$. We prove that asymptotically the correlation is negative for small $p$, $p<\frac{C_1}n$, where $C_1\approx0.3617$, positive for $\frac{C_1}n<p<\frac2n$ and up to $p=p_2(n)$. Computer aided computations suggest that $p_2(n)=\frac{C_2}n$, with $C_2\approx7.5$. We conjecture that the correlationĀ  then stays negative for $p$ up to the previously known zero at $\frac12$; for larger $p$ it is positive.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-14

Publication Date: August 14, 2014

DOI: 10.1214/EJP.v19-2725


  • Alm, Sven Erick; Linusson, Svante. A counter-intuitive correlation in a random tournament. Combin. Probab. Comput. 20 (2011), no. 1, 1--9. MR2745674
  • Alm, Sven Erick; Janson, Svante; Linusson, Svante. Correlations for paths in random orientations of $G(n,p)$ and $G(n,m)$. Random Structures Algorithms 39 (2011), no. 4, 486--506. MR2846300
  • Grimmett, Geoffrey R. Infinite paths in randomly oriented lattices. Random Structures Algorithms 18 (2001), no. 3, 257--266. MR1824275
  • Janson, Svante; Luczak, Malwina J. Susceptibility in subcritical random graphs. J. Math. Phys. 49 (2008), no. 12, 125207, 23 pp. MR2484338
  • McDiarmid, Colin. General percolation and random graphs. Adv. in Appl. Probab. 13 (1981), no. 1, 40--60. MR0595886
  • Heinrich Weber, phLehrbuch der Algebra, Zweite Auflage, Erster Band. Friedrich Vieweg und Sohn, Braunschweig (1898).

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.