Speaker
Svante Linusson
(KTH Stockholm)
Description
Consider a graph G and orient the edges independently with
equal probabilities for the two directions. Let a; s; b be three
distinct vertices and consider the events {s to a}, that there is
a directed path from s to a, and {s to b}. It feels intuitively
clear that these events are positively correlated, which also can
be proven to be true for any graph. In fact, it is true also if we
first condition that there is no directed path from s to t for any
other vertex t in G, which is perhaps less clear intuitively. If we
instead consider the paths {a to s} and {s to b} one
might first guess that these should be negatively correlated,
but this does not hold in general. I will present results for some
special classes of graphs and for random graphs G(n; p) and
G(n;m). This is joint work with Sven Erick Alm and Svante
Janson.