Infinite paths and cliques in random graphs
Volume 216 / 2012
Fundamenta Mathematicae 216 (2012), 163-191
MSC: Primary 05C80; Secondary 60C05, 06A07.
DOI: 10.4064/fm216-2-6
Abstract
We study the thresholds for the emergence of various properties in random subgraphs of $(\mathbb N, <)$. In particular, we give sharp sufficient conditions for the existence of (finite or infinite) cliques and paths in a random subgraph. No specific assumption on the probability is made. The main tools are a topological version of Ramsey theory, exchangeability theory and elementary ergodic theory.
