Monotone Paths in Random Hypergraphs

Matteo Novaga, Pietro Majer

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$.

Keywords


Random graphs; Extremal measures; Percolation

Full Text: PDF