PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

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