Minimum degree condition of Berge Hamiltonicity in random 3-uniform hypergraphs
Filomat, Tome 37 (2023) no. 26, p. 9039
Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts
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 ⌈ n 2 ⌉ 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.
Classification :
05C65, 05C80, 05C45, 05C07
Keywords: Dirac’s theorem, Random hypergraph, Berge cycle, Hamilton cycle
Keywords: Dirac’s theorem, Random hypergraph, Berge cycle, Hamilton cycle
Ailian Chen; Liping Zhang. Minimum degree condition of Berge Hamiltonicity in random 3-uniform hypergraphs. Filomat, Tome 37 (2023) no. 26, p. 9039 . doi: 10.2298/FIL2326039C
@article{10_2298_FIL2326039C,
author = {Ailian Chen and Liping Zhang},
title = {Minimum degree condition of {Berge} {Hamiltonicity} in random 3-uniform hypergraphs},
journal = {Filomat},
pages = {9039 },
year = {2023},
volume = {37},
number = {26},
doi = {10.2298/FIL2326039C},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.2298/FIL2326039C/}
}
TY - JOUR AU - Ailian Chen AU - Liping Zhang TI - Minimum degree condition of Berge Hamiltonicity in random 3-uniform hypergraphs JO - Filomat PY - 2023 SP - 9039 VL - 37 IS - 26 UR - http://geodesic.mathdoc.fr/articles/10.2298/FIL2326039C/ DO - 10.2298/FIL2326039C LA - en ID - 10_2298_FIL2326039C ER -
Cité par Sources :