Infinite paths and cliques in random graphs

• Autorzy: Alessandro Berarducci , Pietro Majer , Matteo Novaga
• Języki publikacji: EN

Abstrakty

EN

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.

Kategorie tematyczne

• 05C80: Random graphs
• 60C05: Combinatorial probability
• 06A07: Combinatorics of partially ordered sets

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Fundamenta Mathematicae
• Rocznik: 2012
• Tom: 216
• Numer: 2
• Strony: 163-191

Daty

wydano

2012

Twórcy

autor

Alessandro Berarducci

• Dipartimento di Matematica, Università di Pisa, Largo B. Pontecorvo 5, 56127 Pisa, Italy

autor

Pietro Majer

• Dipartimento di Matematica, Università di Pisa, Largo B. Pontecorvo 5, 56127 Pisa, Italy

autor

Matteo Novaga

• Dipartimento di Matematica, Università di Padova, Via Trieste 63, 35121 Padova, Italy

Identyfikatory

DOI

10.4064/fm216-2-6