PIMS - SFU Discrete Mathematics Seminar: Peter Bradshaw

Abstract: Given a family G of graphs on a common vertex set X, we say that G is rainbow connected if for every vertex pair u, v ∈ X, there exists a path from u to v that uses at most one edge from each graph of G. We consider the case that G contains s graphs, each sampled randomly from G(n, p), with n = |X| and p = c log n / sn , where c > 1 is a constant. We show that there exists a threshold of at most three consecutive integer values such that when s is greater than or equal to this threshold, G is a.a.s. rainbow connected, and when s is below this threshold, G is a.a.s. not rainbow connected. Joint work with Bojan Mohar.