Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs

Hiệp Hàn, Jie Han*, Patrick Morris

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 (Formula presented.) -pseudo-random if for all (not necessarily disjoint) vertex subsets (Formula presented.) with (Formula presented.) we have (Formula presented.) For any linear k-uniform F, we provide a bound on (Formula presented.) in terms of (Formula presented.) and F, such that (under natural divisibility assumptions on n) any k-uniform (Formula presented.) -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, (Formula presented.) -pseudo-random k-graphs as above contain: (i) a perfect matching if (Formula presented.) and (ii) a loose Hamilton cycle if (Formula presented.). This extends the works of Lenz–Mubayi, and Lenz–Mubayi–Mycroft who studied the analogous problems in the dense setting.

Original languageEnglish
Pages (from-to)101-125
Number of pages25
JournalRandom Structures and Algorithms
Volume61
Issue number1
DOIs
Publication statusPublished - Aug 2022

Keywords

  • Hamilton cycle
  • hypergraph eigenvalue
  • perfect matching
  • pseudo-random hypergraph

Fingerprint

Dive into the research topics of 'Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs'. Together they form a unique fingerprint.

Cite this