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

Abstract: 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 o s

and

s o b

. We prove that asymptotically the correlation is negative for small

p

,

p < f r a c C_{1} n

, where

C_{1} a p p r o x 0.3617

, positive for

f r a c C_{1} n < p < f r a c 2 n

and up to

p = p_{2} (n)

. Computer aided computations suggest that

p_{2} (n) = f r a c C_{2} n

, with

C_{2} a p p r o x 7.5

. We conjecture that the correlation then stays negative for

p

up to the previously known zero at

f r a c 12

; for larger

p

it is positive.

Recommendations

Cited In (4)

This page was built for publication: First critical probability for a problem on random orientations in \(G(n,p)\).