Large complete minors in random subgraphs

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=\frac{1+\epsilon }{k}$ with $\epsilon >0$. We show that with high probability $G_p$ contains a complete minor of order $\tilde{\Omega }(\sqrt{k})$, where the $\sim$ 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.

12 pages, small changes in exposition and a simplification of the proof of Lemma 5

References in corpus (2)

• Long cycles in random subgraphs of graphs with large minimum degree
• The threshold probability for long cycles

Cited by in corpus (1)

• Large independent sets in recursive Markov random graphs