Paths, cycles and sprinkling in random hypergraphs

Abstract

We prove a lower bound on the length of the longest $j$-tight cycle in a $k$-uniform binomial random hypergraph for any $2\le j\le k-1$. We first prove the existence of a $j$-tight path of the required length. The standard "sprinkling" argument is not enough to show that this path can be closed to a $j$-tight cycle -- we therefore show that the path has many extensions, which is sufficient to allow the sprinkling to close the cycle.

References in corpus (1)

• Note on induced paths in sparse random graphs