Infinite paths and cliques in random graphs

Alessandro Berarducci; Pietro Majer; Matteo Novaga

Infinite paths and cliques in random graphs

Alessandro Berarducci; Pietro Majer; Matteo Novaga

Fundamenta Mathematicae (2012)

Volume: 216, Issue: 2, page 163-191
ISSN: 0016-2736

Access Full Article

top

Access to full text

Full (PDF)

Abstract

top

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.

How to cite

top

MLA
BibTeX
RIS

Alessandro Berarducci, Pietro Majer, and Matteo Novaga. "Infinite paths and cliques in random graphs." Fundamenta Mathematicae 216.2 (2012): 163-191. <http://eudml.org/doc/282941>.

@article{AlessandroBerarducci2012,
abstract = {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.},
author = {Alessandro Berarducci, Pietro Majer, Matteo Novaga},
journal = {Fundamenta Mathematicae},
keywords = {random graphs; Ramsey theory; percolation threshold; probability},
language = {eng},
number = {2},
pages = {163-191},
title = {Infinite paths and cliques in random graphs},
url = {http://eudml.org/doc/282941},
volume = {216},
year = {2012},
}

TY - JOUR
AU - Alessandro Berarducci
AU - Pietro Majer
AU - Matteo Novaga
TI - Infinite paths and cliques in random graphs
JO - Fundamenta Mathematicae
PY - 2012
VL - 216
IS - 2
SP - 163
EP - 191
AB - 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.
LA - eng
KW - random graphs; Ramsey theory; percolation threshold; probability
UR - http://eudml.org/doc/282941
ER -

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Language to use for this widget.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Number of notes per page

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.