  In this paper, we study the existence of perfect matchings and Hamiltonian
cycles in the preferential attachment model. In this model, vertices are added
to the graph one by one, and each time a new vertex is created it establishes a
connection with $m$ random vertices selected with probabilities proportional to
their current degrees. (Constant $m$ is the only parameter of the model.) We
prove that if $m \ge 1{,}260$, then asymptotically almost surely there exists a
perfect matching. Moreover, we show that there exists a Hamiltonian cycle
asymptotically almost surely, provided that $m \ge 29{,}500$. One difficulty in
the analysis comes from the fact that vertices establish connections only with
vertices that are "older" (i.e. are created earlier in the process). However,
the main obstacle arises from the fact that edges in the preferential
attachment model are not generated independently. In view of that, we also
consider a simpler setting---sometimes called uniform attachment---in which
vertices are added one by one and each vertex connects to $m$ older vertices
selected uniformly at random and independently of all other choices. We first
investigate the existence of perfect matchings and Hamiltonian cycles in the
uniform attachment model, and then extend the argument to the preferential
attachment version.
