Finding any given 2-factor in sparse pseudorandom graphs efficiently

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Given an (Formula presented.) -vertex pseudorandom graph (Formula presented.) and an (Formula presented.) -vertex graph (Formula presented.) with maximum degree at most two, we wish to find a copy of (Formula presented.) in (Formula presented.), that is, an embedding (Formula presented.) so that (Formula presented.) for all (Formula presented.). Particular instances of this problem include finding a triangle-factor and finding a Hamilton cycle in (Formula presented.). Here, we provide a deterministic polynomial time algorithm that finds a given (Formula presented.) in any suitably pseudorandom graph (Formula presented.). The pseudorandom graphs we consider are (Formula presented.) -bijumbled graphs of minimum degree which is a constant proportion of the average degree, that is, (Formula presented.). A (Formula presented.) -bijumbled graph is characterised through the discrepancy property: (Formula presented.) for any two sets of vertices (Formula presented.) and (Formula presented.). Our condition (Formula presented.) 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.

Original languageEnglish
Pages (from-to)87-108
Number of pages22
JournalJournal of Graph Theory
Volume96
Issue number1
DOIs
Publication statusPublished - Jan 2021
Externally publishedYes

Keywords

  • 2-factors
  • absorbing meth
  • expander graphs

Fingerprint

Dive into the research topics of 'Finding any given 2-factor in sparse pseudorandom graphs efficiently'. Together they form a unique fingerprint.

Cite this