Finding any given 2‐factor in sparse pseudorandom graphs efficiently. Issue 1 (5th May 2020)

• Record Type: Journal Article
• Authors: Han, Jie; Kohayakawa, Yoshiharu; Morris, Patrick; Person, Yury
• Is Part Of: Journal of graph theory. Volume 96:Issue 1(2021)
• Page Start: 87
• Page End: 108
• Publication Date: 2020-05-05
• Subjects: 2‐factors -- absorbing meth -- expander graphs; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22576
• Languages: English
• ISSNs: 0364-9024

Abstract

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.