Independence number and disjoint theta graphs.
Induced complete -partite graphs in dense clique-less graphs.
Induced trees in triangle-free graphs.
Infinite paths and cliques in random graphs
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.