Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Given any finite graph G, define the bunkbed graph as G x K_2, where K_2 consists of two vertices {0,1} connected by an edge. In edge percolation every edge in G x K_2 is present with probability p. An old conjecture (dating at least to Kasteleyn 1985) states that for all G and p the probability that (u,0) is in the same component as (v,0) is greater than the probability that (u,0) is in the same component as (v,1) for every pair of vertices u,v in G. I will discuss what is known about this conjecture.

I will then turn to a related problem with random orientation, where we for a fixed graph G orient the edges independently with equal probabilities for the two directions. Let a,s,b be three distinct vertices of G and consider the events {s -> a}, that there is a directed path from s to a, and {s -> b}. It feels intuitively clear that these events are positively correlated, which also can be proven to be true for any graph.

If we instead consider the paths {a -> s} and {s -> 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). The second part is joint work with Sven Erick Alm and Svante Janson.

This is a joint Discrete Math/Probability seminar.