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 $varphicolon V(H)to V(G)$ so that $varphi(u)varphi(v)in E(G)$ for all $uvin 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. $Omega(pn)$. A $(p,lambda)$-bijumbled graph is characterised through the discrepancy property: $left|e(A,B)-p|A||B|right |<lambdasqrt{|A||B|}$ for any two sets of vertices $A$ and $B$. Our condition $lambda=O(p^2n/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 is based on that of Nenadov (emph{Bulletin of the London Mathematical Society}, to appear) and on ours (arXiv:1806.01676), together with additional ideas and simplifications.
Download