Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs

Publication date 16 September 2020

Abstract: For positive integers

r > e l l

, an

r

-uniform hypergraph is called an

e l l

-cycle if there exists a cyclic ordering of its vertices such that each of its edges consists of

r

consecutive vertices, and such that every pair of consecutive edges (in the natural ordering of the edges) intersect in precisely

e l l

vertices. Such cycles are said to be linear when

e l l = 1

, and nonlinear when

e l l > 1

. We determine the sharp threshold for nonlinear Hamiltonian cycles and show that for all

r > e l l > 1

, the threshold

p_{r, e l l}^{*} (n)

for the appearance of a Hamiltonian

e l l

-cycle in the random

r

-uniform hypergraph on

n

vertices is sharp and is

p_{r, e l l}^{*} (n) = l a m b d a (r, e l l) (f r a c m a t h r m e n)^{r - e l l}

for an explicitly specified function

l a m b d a

. This resolves several questions raised by Dudek and Frieze in 2011.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs