Perfect matchings and Hamilton cycles in uniform attachment graphs

Abstract

We study Hamilton cycles and perfect matchings in a uniform attachment graph. In this random graph, vertices are added sequentially, and when a vertex $t$ is created, it makes $k$ independent and uniform choices from $\{1,\dots ,t-1\}$ and attaches itself to these vertices. Improving the results of Frieze, Pérez-Giménez, Prałat and Reiniger (2019), we show that, with probability approaching 1 as $n$ tends to infinity, a uniform attachment graph on $n$ vertices has a perfect matching for $k\ge 5$ and a Hamilton cycle for $k\ge 13$. One of the ingredients in our proofs is the identification of a subset of vertices that is least likely to expand, which provides us with better expansion rates than the existing ones.

16 pages