The square of a Hamilton cycle in randomly perturbed graphs

Abstract

Abstract We investigate the appearance of the square of a Hamilton cycle in the model of randomly perturbed graphs, which is, for a given , the union of any ‐vertex graph with minimum degree and the binomial random graph . This is known when and we determine the exact perturbed threshold probability in all the remaining cases, that is, for each . We demonstrate that, as ranges over the interval , the threshold performs a countably infinite number of ‘jumps’. Our result has implications on the perturbed threshold for two‐universality, where we also fully address all open cases.

Locations

• arXiv (Cornell University) - View - PDF
• London School of Economics and Political Science Research Online (London School of Economics and Political Science) - View - PDF
• Random Structures and Algorithms - View