We study the thresholds for the emergence of various properties in random subgraphs of (ℕ, <). 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.
@article{bwmeta1.element.bwnjournal-article-doi-10_4064-fm216-2-6,
author = {Alessandro Berarducci and Pietro Majer and Matteo Novaga},
title = {Infinite paths and cliques in random graphs},
journal = {Fundamenta Mathematicae},
volume = {219},
year = {2012},
pages = {163-191},
zbl = {1243.05216},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-fm216-2-6}
}
Alessandro Berarducci; Pietro Majer; Matteo Novaga. Infinite paths and cliques in random graphs. Fundamenta Mathematicae, Tome 219 (2012) pp. 163-191. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-fm216-2-6/