| Full text | |
| Author(s): |
Han, Jie
;
Kohayakawa, Yoshiharu
;
Morris, Patrick
;
Person, Yury
Total Authors: 4
|
| Document type: | Journal article |
| Source: | JOURNAL OF GRAPH THEORY; v. 96, n. 1, p. 22-pg., 2020-05-05. |
| 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 phi:V(H)-> V(G) so that phi(u)phi(v)is an element of E(G) for all uv is an element of 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,lambda)-bijumbled graphs of minimum degree which is a constant proportion of the average degree, that is, omega(pn). A (p,lambda)-bijumbled graph is characterised through the discrepancy property: |e(A,B)-p|A||B||<lambda|A||B| for any two sets of vertices A and B. Our condition lambda=O(p2n/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 builds on our previous work, incorporating the work of Nenadov, together with additional ideas and simplifications. (AU) | |
| FAPESP's process: | 14/18641-5 - Hamilton cycles and tiling problems in hypergraphs |
| Grantee: | Jie Han |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |