JEDNOSTKA NAUKOWA KATEGORII A+

Infinite paths and cliques in random graphs

Tom 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

Streszczenie

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.

Autorzy

  • 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

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek