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 , that is, an embedding φ : V ( H ) → V ( G )so that φ ( u ) φ ( v ) ∈ E ( G ) for all u v ∈ 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 , λ ) ‐bijumbled graphs of minimum degree which is a constant proportion of the average degree, that is, Ω ( p n ) . A ( p , λ ) ‐bijumbled graph is characterised through the discrepancy property:| e ( A , B ) − p | A | | B | | < λ| A | | B |for any two sets of vertices A and B . Our condition λ = O ( p 2 n / 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, incorporating the work of Nenadov, together with additional ideas and simplifications.