TY - GEN
T1 - Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs
AU - Hàn, Hiêp
AU - Han, Jie
AU - Morris, Patrick
N1 - Publisher Copyright:
Copyright © 2020 by SIAM
PY - 2020
Y1 - 2020
N2 - We investigate the emergence of spanning structures in sparse pseudo-random k-uniform hypergraphs, using the following comparatively weak notion of pseudo-randomness. A k-uniform hypergraph H on n vertices is called (p, α, ε)-pseudo-random if for all not necessarily disjoint sets A1, . . ., Ak ⊂ V (H) with ∣A1∣∙∙∙∣Ak∣ > αnk we have e(A1, . . ., Ak) = (1 ± ε)p∣A1∣∙∙∙∣Ak∣. For any linear k-uniform F we provide a bound on α = α(n) in terms of p = p(n) and F, such that (under natural divisibility assumptions on n) any (p, α, o(1))-pseudorandom n-vertex H with a mild minimum degree condition contains an F-factor. The approach also enables us to establish the existence of loose Hamilton cycles in sufficiently pseudo-random hypergraphs and all results imply corresponding bounds for stronger notions of hypergraph pseudo-randomness such as jumbledness or large spectral gap. As a consequence of our results, perfect matchings appear at α = o(pk) while loose Hamilton cycles appear at α = o(pk−1). This extends the works of Lenz-Mubayi, and Lenz-Mubayi-Mycroft who studied the analogous problems in the dense setting.
AB - We investigate the emergence of spanning structures in sparse pseudo-random k-uniform hypergraphs, using the following comparatively weak notion of pseudo-randomness. A k-uniform hypergraph H on n vertices is called (p, α, ε)-pseudo-random if for all not necessarily disjoint sets A1, . . ., Ak ⊂ V (H) with ∣A1∣∙∙∙∣Ak∣ > αnk we have e(A1, . . ., Ak) = (1 ± ε)p∣A1∣∙∙∙∣Ak∣. For any linear k-uniform F we provide a bound on α = α(n) in terms of p = p(n) and F, such that (under natural divisibility assumptions on n) any (p, α, o(1))-pseudorandom n-vertex H with a mild minimum degree condition contains an F-factor. The approach also enables us to establish the existence of loose Hamilton cycles in sufficiently pseudo-random hypergraphs and all results imply corresponding bounds for stronger notions of hypergraph pseudo-randomness such as jumbledness or large spectral gap. As a consequence of our results, perfect matchings appear at α = o(pk) while loose Hamilton cycles appear at α = o(pk−1). This extends the works of Lenz-Mubayi, and Lenz-Mubayi-Mycroft who studied the analogous problems in the dense setting.
UR - http://www.scopus.com/inward/record.url?scp=85084077441&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85084077441
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 702
EP - 717
BT - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
A2 - Chawla, Shuchi
PB - Association for Computing Machinery
T2 - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
Y2 - 5 January 2020 through 8 January 2020
ER -