Large complete minors in random subgraphs. (3rd July 2021)

• Record Type: Journal Article
• Authors: Erde, Joshua; Kang, Mihyun; Krivelevich, Michael
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 4(2021)
• Page Start: 619
• Page End: 630
• Publication Date: 2021-07-03
• Subjects: 05C80 -- 05C83; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000607
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: Let G be a graph of minimum degree at least k and let G p 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 G p contains when p = (1 + ε )/ k with ε > 0. We show that with high probability G p contains a complete minor of order $\tilde{\Omega}(\sqrt{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.