Finding any given 2-factor in sparse pseudorandom graphs efficiently

MaRDI QIDQ6314156zbMATH OpenFDO

Authors Jie Han, Yoshiharu Kohayakawa, Patrick Morris, Yury Person

Publication date 16 February 2019

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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$, i.e. an embedding $varphicolonV(H)oV(G)$ so that $varphi(u)varphi(v)inE(G)$ for all $uvinE(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|ight|<lambdasqrt|A||B|$ for any two sets of vertices $A$ and $B$. Our condition $lambda=O(p^{2}n/logn)$ 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.

This page was built for publication: Finding any given 2-factor in sparse pseudorandom graphs efficiently

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6314156)