Large Complete Minors in Random Subgraphs

Activity: Talk or presentationTalk at conference or symposiumScience to science


Let G be a graph of minimum degree at least k and let Gp be the random subgraph of G obtained by keeping each edge independently with probability p. We are interested in the size of the largest complete minor that Gp contains when p=1+εk with ε>0. We show that with high probability Gp contains a complete minor of order Ω~(k−−√), where the ∼ hides a polylogarithmic factor. Furthermore, in the case where the order of G is also bounded above by a constant multiple of k, we show that this polylogarithmic term can be removed, giving a tight bound.
Period8 Jul 2021
Event title28th British Combinatorial Conference
Event typeConference
LocationVirtuell, United KingdomShow on map
Degree of RecognitionNational