Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs

Abstract

Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)Factors and loose Hamilton cycles in sparse pseudo-random hypergraphsHiệp Hàn, Jie Han, and Patrick MorrisHiệp Hàn, Jie Han, and Patrick Morrispp.702 - 717Chapter DOI:https://doi.org/10.1137/1.9781611975994.43PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We investigate the emergence of spanning structures in sparse pseudo-random k-uniform hypergraphs, using the following comparatively weak notion of pseudorandomness. 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))-pseudo-random 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. Previous chapter Next chapter RelatedDetails Published:2020eISBN:978-1-61197-599-4 https://doi.org/10.1137/1.9781611975994Book Series Name:ProceedingsBook Code:PRDA20Book Pages:xxii + 3011

Locations

• Society for Industrial and Applied Mathematics eBooks - View
• arXiv (Cornell University) - View - PDF