Longest paths in random hypergraphs
Authors:
- Oliver CooleyOCOliver Cooley
- Frederik GarbeFGFrederik Garbe
- Eng Keat HngEHEng Keat Hng
- Mihyun KangMKMihyun Kang
- Nicolás Sanhueza-MatamalaNSNicolás Sanhueza-Matamala
- Julian ZallaJZJulian Zalla
Preprint
Abstract
Given integers $k,j$ with $1\le j \le k-1$, we consider the length of the longest $j$-tight path in the binomial random $k$-uniform hypergraph $H^k(n,p)$. We show that this length undergoes a phase transition from logarithmic length to linear and determine the critical threshold, as well as proving upper and lower bounds on the length in the subcritical and supercritical ranges. In particular, for the supercritical case we introduce the `Pathfinder' algorithm, a depth-first search algorithm which discovers $j$-tight paths in a $k$-uniform hypergraph. We prove that, in the supercritical case, with high probability this algorithm will find a long $j$-tight path.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- A scaling limit for the length of the longest cycle in a sparse random graphJournal of Combinatorial Theory, Series B, 2021
- A Survey of Hypergraph Ramsey Problems2020
- Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphsRandom Structures & Algorithms, 2020
- The size of the giant high‐order component in random hypergraphsRandom Structures & Algorithms, 2018
- Tight cycles and regular slices in dense hypergraphsJournal of Combinatorial Theory, Series A, 2017
- The phase transition in random graphs: A simple proofRandom Structures & Algorithms, 2012
- Tight Hamilton cycles in random uniform hypergraphsRandom Structures & Algorithms, 2012
- Cycles in a random graph near the critical pointRandom Structures & Algorithms, 1991
- Component structure in the evolution of random hypergraphsCombinatorica, 1985
- The longest path in a random graphCombinatorica, 1981