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

Datum objave: 19. 12. 2021
Seminar za diskretno matematiko
torek
21
december
Ura:
10.15
Lokacija:
Na daljavo.
ID: 985 4204 1829 – Geslo: 791896

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.