Finding any given 2‐factor in sparse pseudorandom graphs efficiently. Issue 1 (5th May 2020) - Han, Jie; Kohayakawa, Yoshiharu; Morris, Patrick; Person, Yury
Abstract: 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.