Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs. Issue 1 (14th October 2021)

• Record Type: Journal Article
• Authors: Hàn, Hiệp; Han, Jie; Morris, Patrick
• Is Part Of: Random structures & algorithms. Volume 61:Issue 1(2022)
• Page Start: 101
• Page End: 125
• Publication Date: 2021-10-14
• Subjects: Hamilton cycle -- hypergraph eigenvalue -- perfect matching -- pseudo‐random hypergraph; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21052
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We investigate the emergence of subgraphs 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) vertex subsets A 1, …, A k ⊆ V ( H ) with | A 1 | ⋯ | A k | ≥ α n k we have e ( A 1, …, A k ) = ( 1 ± ε ) p | A 1 | ⋯ | A k | . 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 k ‐uniform ( p, α, o ( 1 ) ) ‐pseudo‐random n ‐vertex hypergraph H with a mild minimum vertex 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, along the way, we also derive conditions which guarantee the appearance of any fixed sized subgraph. All results imply corresponding bounds for stronger notions of hypergraph pseudo‐randomness such as jumbledness or large spectral gap. As a consequence, ( p, α, o ( 1 ) ) ‐pseudo‐random k ‐graphs as above contain: (i) a perfect matching if α = o ( p k ) and (ii) a loose Hamilton cycle if α = o ( p k − 1 ) . This extends the works of Lenz–Mubayi, and Lenz–Mubayi–Mycroft who studied the analogous problems in the dense setting.