Can I read Finding Any Given 2‐Factor in Sparse Pseudorandom Graphs Efficiently on EtoBox?

Finding Any Given 2‐Factor in Sparse Pseudorandom Graphs Efficiently by Jie Han; Yoshiharu Kohayakawa; Patrick Morris; Yury Person is a Computer Science article available to read on EtoBox.

What is Finding Any Given 2‐Factor in Sparse Pseudorandom Graphs Efficiently about?

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

Who reads Finding Any Given 2‐Factor in Sparse Pseudorandom Graphs Efficiently?

Author

Jie Han; Yoshiharu Kohayakawa; Patrick Morris; Yury Person

Publisher

John Wiley and Sons; Wiley (John Wiley & Sons); John Wiley & Sons Inc.; Wiley (ISSN 0364-9024)

Published

2020

Language

EN

Field

Computer Science (Physical Sciences)