Longest paths in random hypergraphs

DOI10.1137/20M1345712MaRDI QIDQ5163510zbMATH OpenOpenAlexFDO

Authors Oliver Cooley, Frederik Garbe, Eng Keat Hng, Mihyun Kang, Nicolás Sanhueza-Matamala, Julian Zalla

Publication date 4 November 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.14143

zbMATH Keywords

pathsphase transitionrandom hypergraphssearch algorithm

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Given integers $k,j$ with $1lejlek-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.

Recommendations

• Short proofs for long induced paths
• Largest components in random hypergraphs
• Monotone paths in random hypergraphs
• Tight Hamilton cycles in random hypergraphs
• Subcritical random hypergraphs, high-order components, and hypertrees

Cites work

• A Random Graph With a Subcritical Number of Edges
• A scaling limit for the length of the longest cycle in a sparse random graph
• A survey of hypergraph Ramsey problems
• An improved upper bound on the length of the longest cycle of a supercritical random graph
• Component structure in the evolution of random hypergraphs
• Cycles in a random graph near the critical point
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Hypergraph extensions of the Erdős-Gallai theorem
• Largest components in random hypergraphs
• Loose Hamilton cycles in random uniform hypergraphs
• Recent advances on Dirac-type problems for hypergraphs
• Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs
• The longest path in a random graph
• The phase transition in random graphs: a simple proof
• The size of the giant high-order component in random hypergraphs
• Tight cycles and regular slices in dense hypergraphs
• Tight Hamilton cycles in random uniform hypergraphs

Cited in

(6)

• Loose cores and cycles in random hypergraphs
• scientific article; zbMATH DE number 3915301 (Why is no real title available?)
• Monotone paths in random hypergraphs
• Long Paths in Random Apollonian Networks
• Short proofs for long induced paths
• Paths, cycles and sprinkling in random hypergraphs

This page was built for publication: Longest paths in random hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5163510)