Loose paths in random ordered hypergraphs

2025/04/16 by Dudek, Andrzej, Frieze, Alan, Pegden, Wesley
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2504.12196

Abstract

We consider the length of \em ordered loose paths in the random r-uniform hypergraph H=H^(r)(n, p). A ordered loose path is a sequence of edges E₁,E₂,…,E_ℓ where max\j∈ E_i\=min\j∈ E_i+1\ for 1≤ i<ℓ. We establish fairly tight bounds on the length of the longest ordered loose path in H that hold with high probability.

Related

• Longest paths in random hypergraphs
• Paths, cycles and sprinkling in random hypergraphs
• The Ramsey number of generalized loose paths in uniform Hypergrpahs
• Loose cores and cycles in random hypergraphs
• On-line size Ramsey number for monotone k-uniform ordered paths with\n uniform looseness