Bojan Mohar: Mavrična povezanost družin slučajnih grafov (Rainbow connectivity of families of random graphs)

Predavatelj:
**Bojan Mohar ** (SFU in IMFM)

Naslov:
Mavrična povezanost družin slučajnih grafov
(Rainbow connectivity of families of random graphs)

Povzetek:
Given a family G that contains s graphs on a common vertex set X, we say that G is rainbow connected if for every vertex pair u,v in X, there exists a path from u to v that uses at most one edge from each graph in 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 when s is sufficiently large, G is a.a.s. rainbow connected, and when s is sufficiently small, G is a.a.s. not rainbow connected. We also calculate a threshold of s for the rainbow connectivity of G, and we show that this threshold is concentrated on at most three values.

This is joint work with Peter Bradshaw.