×

Infinite paths and cliques in random graphs. (English) Zbl 1243.05216

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

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C55 Generalized Ramsey theory
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
60C05 Combinatorial probability
06A07 Combinatorics of partially ordered sets
PDFBibTeX XMLCite
Full Text: DOI arXiv