Finding any given 2-factor in sparse pseudorandom graphs efficiently

Given an $n$-vertex pseudorandom graph $G$ and an $n$-vertex graph $H$ with maximum degree at most two, we wish to find a copy of $H$ in $G$, i.e.\ an embedding $\phi \text{\hspace{0.17em}⁣}:V(H)\to V(G)$ so that $\phi (u)\phi (v)\in E(G)$ for all $uv\in E(H)$. Particular instances of this problem include finding a triangle-factor and finding a Hamilton cycle in $G$. Here, we provide a deterministic polynomial time algorithm that finds a given $H$ in any suitably pseudorandom graph $G$. The pseudorandom graphs we consider are $(p,\lambda )$-bijumbled graphs of minimum degree which is a constant proportion of the average degree, i.e.\ $\mathrm{\Omega }(pn)$. A $(p,\lambda )$-bijumbled graph is characterised through the discrepancy property: $\mid e(A,B)-p\mathrm{\mid }A\mathrm{\mid }\mathrm{\mid }B\mathrm{\mid }\mid <\lambda \sqrt{\mathrm{\mid }A\mathrm{\mid }\mathrm{\mid }B\mathrm{\mid }}$ for any two sets of vertices $A$ and $B$. Our condition $\lambda =O(p^{2}n\mathrm{/}\log n)$ on bijumbledness is within a log factor from being tight and provides a positive answer to a recent question of Nenadov. We combine novel variants of the absorption-reservoir method, a powerful tool from extremal graph theory and random graphs. Our approach builds on our previous work (\emph{European Journal of Combinatorics} $\mathbf{\text{82}}$ (2019), 102999), incorporating the work of Nenadov (\emph{Bulletin of the London Mathematical Society} $\mathbf{\text{51}}$ (3) (2019), pp.~421–430), together with additional ideas and simplifications.