Infinite paths and cliques in random graphs

Volume 216 / 2012

Alessandro Berarducci, Pietro Majer, Matteo Novaga Fundamenta Mathematicae 216 (2012), 163-191 MSC: Primary 05C80; Secondary 60C05, 06A07. DOI: 10.4064/fm216-2-6

Abstract

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.

Authors

  • Alessandro BerarducciDipartimento di Matematica
    Università di Pisa
    Largo B. Pontecorvo 5
    56127 Pisa, Italy
    e-mail
  • Pietro MajerDipartimento di Matematica
    Università di Pisa
    Largo B. Pontecorvo 5
    56127 Pisa, Italy
    e-mail
  • Matteo NovagaDipartimento di Matematica
    Università di Padova
    Via Trieste 63
    35121 Padova, Italy
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image