We study the thresholds for the emergence of various properties in random subgraphs of (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.
Infinite paths and cliques in random graphs
BERARDUCCI, ALESSANDRO;MAJER, PIETRO;NOVAGA, MATTEO
2012-01-01
Abstract
We study the thresholds for the emergence of various properties in random subgraphs of (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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
