Correlation of Paths Between Distinct Vertices in a Randomly Oriented Graph

Abstract: We prove that in a random tournament the events

s i g h t a r r o w a

and

t i g h t a r r o w b

are positively correlated, for distinct vertices

a, s, b, t i n K_{n} .

It is also proven that the correlation between the events

s i g h t a r r o w a

and

t i g h t a r r o w 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

). We conjecture it to be positive for all

p

and all

n

. An exact recursion for

P (s i g h t a r r o w a c a p t i g h t a r r o w b)

in

g n p

is given.

Recommendations

Cited In (6)

This page was built for publication: Correlation of Paths Between Distinct Vertices in a Randomly Oriented Graph