Minimum degree condition of Berge Hamiltonicity in random 3-uniform hypergraphs

被引:0
作者
Chen, Ailian [1 ]
Zhang, Liping [1 ]
机构
[1] Fuzhou Univ, Sch Math & Stat, Fuzhou 350108, Fujian, Peoples R China
基金
中国国家自然科学基金;
关键词
Dirac's theorem; Random hypergraph; Berge cycle; Hamilton cycle;
D O I
10.2298/FIL2326039C
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A graph H has Hamiltonicity if it contains a cycle which covers each vertex of H. In graph theory, Hamiltonicity is a classical and worth studying problem. In 1952, Dirac proved that any n-vertex graph H with minimum degree at least inverted right perpendicular n/2 inverted left perpendicular has Hamiltonicity. In 2012, Lee and Sudakov proved that if p >> log n/n, then asympotically almost surely each n-vertex subgraph of random graph G(n, p) with minimum degree at least (1/2 + o(1))np has Hamiltonicity. In this paper, we exend Dirac's theorem to random 3-uniform hypergraphs. The random 3-uniform hypergraph model H-3(n, p) consists of all 3-uniform hypergraphs on n vertices and every possible edge appears with probability p randomly and independently. We prove that if p >> log n/n(2), then asympotically almost surely every n-vertex subgraph of H-3(n, p) with minimum degree at least (1/4 + o(1))(n/2) p has Berge Hamiltonicity. The value log n/n(2) and constant 1/4 both are best possible.
引用
收藏
页码:9039 / 9050
页数:12
相关论文
共 17 条
[1]  
Alon N., 2016, Wiley Series in Discrete Mathematics and Optimization
[2]   Hamiltonian Berge cycles in random hypergraphs [J].
Bal, Deepak ;
Berkowitz, Ross ;
Devlin, Pat ;
Schacht, Mathias .
COMBINATORICS PROBABILITY & COMPUTING, 2021, 30 (02) :228-238
[3]   Rainbow Matchings and Hamilton Cycles in Random Graphs [J].
Bal, Deepak ;
Frieze, Alan .
RANDOM STRUCTURES & ALGORITHMS, 2016, 48 (03) :503-523
[4]  
Berge C., 1976, GRAPHS HYPERGRAPH, V2rd
[5]  
Bermond J.-C., 1978, Problemes combinatoires et theorie des graphes, V260, P39
[6]   Some New Sufficient Conditions for 2p-Hamilton-Biconnectedness of Graphs [J].
Chen, Ming-Zhu ;
Zhang, Xiao-Dong .
FILOMAT, 2019, 33 (03) :993-1011
[7]   A Dirac-type theorem for Berge cycles in random hypergraphs [J].
Clemens, Dennis ;
Ehrenmueller, Julia ;
Person, Yury .
ELECTRONIC JOURNAL OF COMBINATORICS, 2020, 27 (03) :1-23
[8]  
Dirac G.A., 1952, P LONDON MATH SOC 3, Vs3-2, P69, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]
[9]   Extensions of Results on Rainbow Hamilton Cycles in Uniform Hypergraphs [J].
Dudek, Andrzej ;
Ferrara, Michael .
GRAPHS AND COMBINATORICS, 2015, 31 (03) :577-583
[10]  
Dudek A, 2012, ELECTRON J COMB, V19