2019/02/16 by Han, Jie, Kohayakawa, Yoshiharu, Morris, Patrick +1
#05C38 #05C70 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1902.06164
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 φ\colon V(H)→ V(G) so that φ(u)φ(v)∈ E(G) for all uv∈ 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, i.e. Ω(pn). 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(p2n/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 (Bulletin of the London Mathematical Society, to appear) and on ours (arXiv:1806.01676), together with additional ideas and simplifications.