PIMS - SFU Discrete Mathematics Seminar: Peter Bradshaw

  • Date: 11/16/2021
  • Time: 14:30
Peter Bradshaw (SFU)

Simon Fraser University


A Rainbow Connectivity Threshold for Random Graph Families


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.

Other Information: 

This is an in-person presentation located at SFU, room K9509. There is a limit of 15 people for room attendance. There is an online option to join over Zoom. (ID: 668 0051 2140, password: Graph)


Visit SFU Department of Mathematics for information and scroll down to see calendar listing.