Monotone paths in random hypergraphs

2009/06/09 by Pietro Majer, Majer, Pietro, Matteo Novaga +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.0906.1689

openalex publication_date 2009/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We determine the probability thresholds for the existence of monotone paths, of finite and infinite length, in random oriented graphs with vertex set \mathbb N^[k], the set of all increasing k-tuples in \mathbb N. These graphs appear as line graph of uniform hypergraphs with vertex set \mathbb N.

Citations

• On a Problem of Formal Logic

Related

• A sharp threshold for random graphs with a monochromatic triangle in every edge coloring
• Random hypergraphs and algorithmics
• Longest paths in random hypergraphs
• A phase transition in Erdős-Barak random graphs
• Increasing paths in random temporal graphs