Minors, connectivity, and diameter in randomly perturbed sparse graphs

Extremal properties of sparse graphs, randomly perturbed by the binomial random graph are considered. It is known that every n-vertex graph G contains a complete minor of order Ω(n/α(G)). We prove that adding ξn random edges, where ξ>0 is arbitrarily small yet fixed, to an n-vertex graph G satisfying α(G)≤ζ(ξ)n asymptotically almost surely results in a graph containing a complete minor of order Ω̃n/α(G); this result is tight up to the implicit logarithmic terms. For complete topological minors, we prove that there exists a constant C>0 such that adding Cn random edges to a graph G satisfying δ(G)=ω(1), asymptotically almost surely results in a graph containing a complete topological minor of order Ω̃(min{δ(G),n}); this result is tight up to the implicit logarithmic terms. Finally, extending results of Bohman, Frieze, Krivelevich, and Martin for the dense case, we analyse the asymptotic behaviour of the vertex-connectivity and the diameter of randomly perturbed sparse graphs.