Fragile minor-monotone parameters under random edge perturbation

Abstract

We conduct a quantitative analysis of how many random edges need to be added to a base graph $H$ in order to significantly increase natural minor-monotone graph parameters of the resulting graph $R$. Specifically, we show that if $R$ is obtained from a connected graph $H$ by adding only a few random edges, the tree-width, genus, and Hadwiger number of $R$ become very large, irrespective of the structure of $H$.

21 pages