Covering 3-uniform hypergraphs by vertex-disjoint tight paths

被引:0
作者
Han, Jie [1 ]
机构
[1] Beijing Inst Technol, Sch Math & Stat, Ctr Appl Math, Beijing, Peoples R China
关键词
Hamilton cycle; tight path; MINIMUM CODEGREE THRESHOLD; LOOSE HAMILTON CYCLES; DIRAC-TYPE THEOREM; PERFECT MATCHINGS;
D O I
10.1002/jgt.22853
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For alpha > 0 and large integer n, let H be an n-vertex 3-uniform hypergraph such that every pair of vertices is in at least n / 3 + alpha ( n ) $n\unicode{x02215}3+\alpha (n)$ edges. We show that H $H$ contains two vertex-disjoint tight paths whose union covers the vertex set of H $H$. The quantity two here is best possible and the degree condition is asymptotically best possible. This result also has an interpretation as the deficiency problems, recently introduced by Nenadov, Sudakov, and Wagner: every such H $H$ can be made Hamiltonian by adding at most two vertices and all triples intersecting them.
引用
收藏
页码:782 / 802
页数:21
相关论文
共 26 条
  • [21] ANTI-RAMSEY NUMBER OF MATCHINGS IN 3-UNIFORM HYPERGRAPHS
    Guo, Mingyang
    Lu, Hongliang
    Peng, Xing
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (03) : 1970 - 1987
  • [22] Tiling 3-Uniform Hypergraphs With K43-2e
    Czygrinow, Andrzej
    DeBiasio, Louis
    Nagle, Brendan
    JOURNAL OF GRAPH THEORY, 2014, 75 (02) : 124 - 136
  • [23] Large Y3,2-tilings in 3-uniform hypergraphs
    Han, Jie
    Sun, Lin
    Wang, Guanghui
    EUROPEAN JOURNAL OF COMBINATORICS, 2024, 120
  • [24] Minimum degree condition of Berge Hamiltonicity in random 3-uniform hypergraphs
    Chen, Ailian
    Zhang, Liping
    FILOMAT, 2023, 37 (26) : 9039 - 9050
  • [25] Large sets of Hamilton cycle decompositions of complete bipartite 3-uniform hypergraphs
    Zhao, Hongtao
    JOURNAL OF COMBINATORIAL DESIGNS, 2018, 26 (12) : 581 - 594
  • [26] Large Sets of Wrapped K-K Hamilton Cycle Decompositions of Complete Bipartite 3-Uniform Hypergraphs
    Zhao, Hongtao
    Rodger, C. A.
    JOURNAL OF COMBINATORIAL DESIGNS, 2015, 23 (11) : 499 - 508