Monotone paths in random hypergraphs

MaRDI QIDQ426858zbMATH OpenFDO

Authors Pietro Majer, M. Novaga

Publication date 12 June 2012

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0906.1689, http://www.emis.de/journals/EJC/ojs/index.php/eljc/article/view/v19i2p3

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

extremal measurespercolationrandom graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80)

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 $mathbbN$. These graphs appear as line graph of uniform hypergraphs with vertex set $mathbbN$.

Review text

Summary: 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\).

Recommendations

• Infinite paths and cliques in random graphs
• Longest paths in random hypergraphs
• The multiple-orientability thresholds for random hypergraphs

Cited in

(3)

• The median of the number of simple paths on three vertices in the random graph
• Infinite paths and cliques in random graphs
• Longest paths in random hypergraphs

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

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