跳到主要导航 跳到搜索 跳到主要内容

Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs

  • Hiêp Hàn
  • , Jie Han
  • , Patrick Morris
  • Universidad de Santiago de Chile
  • University of Rhode Island
  • Free University of Berlin
  • Berlin Mathematical School

科研成果: 书/报告/会议事项章节会议稿件同行评审

摘要

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.

源语言英语
主期刊名31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
编辑Shuchi Chawla
出版商Association for Computing Machinery
702-717
页数16
ISBN(电子版)9781611975994
出版状态已出版 - 2020
已对外发布
活动31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, 美国
期限: 5 1月 20208 1月 2020

丛书

姓名Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
2020-January

会议

会议31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
国家/地区美国
Salt Lake City
时期5/01/208/01/20

学术指纹

探究 'Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs' 的科研主题。它们共同构成独一无二的学术指纹。

引用此