Minimum Degree Condition of Berge Hamiltonicity in Random 3-Uniform Hypergraphs

Liping Zhang, Ailian Chen

Abstract


A graph $H$ has Hamiltonicity if it contains a cycle which cover 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 $\lceil{n\over2}\rceil$ has Hamiltonicity. In 2012, Lee and Sudakov proved that if $p\gg\frac{\log n}{n}$, then asympotically almost surely each $n$-vertex subgraph of random graph 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 hypergraph on $n$ vertices and every possible edge appears with probability $p$ randomly and independently. We prove that if $p\gg\frac{\log n} {n^{2}}$, then asympotically almost surely every $n$-vertex subgraph of $H^{3}(n,p)$ with minimum edge degree at least $(\frac{1}{4}+o(1)){n\choose 2}p$ has Berge Hamiltonicity. The value ${\log n\over n^2}$ and constant $1/4$ are best possible.


Refbacks

  • There are currently no refbacks.