Geodesic
Infinite paths and cliques in random graphs
Alessandro Berarducci1 ; Pietro Majer1 ; Matteo Novaga2
1 Dipartimento di Matematica Università di Pisa Largo B. Pontecorvo 5 56127 Pisa, Italy
2 Dipartimento di Matematica Università di Padova Via Trieste 63 35121 Padova, Italy
Fundamenta Mathematicae, Tome 216 (2012) no. 2, pp. 163-191

Voir la notice de l'article provenant de la source Institute of Mathematics Polish Academy of Sciences

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.
DOI : 10.4064/fm216-2-6
Keywords: study thresholds emergence various properties random subgraphs mathbb particular sharp sufficient conditions existence finite infinite cliques paths random subgraph specific assumption probability made main tools topological version ramsey theory exchangeability theory elementary ergodic theory

Alessandro Berarducci 1 ; Pietro Majer 1 ; Matteo Novaga 2

1 Dipartimento di Matematica Università di Pisa Largo B. Pontecorvo 5 56127 Pisa, Italy
2 Dipartimento di Matematica Università di Padova Via Trieste 63 35121 Padova, Italy 
@article{10_4064_fm216_2_6,
     author = {Alessandro Berarducci and Pietro Majer and Matteo Novaga},
     title = {Infinite paths and cliques in random graphs},
     journal = {Fundamenta Mathematicae},
     pages = {163--191},
     publisher = {mathdoc},
     volume = {216},
     number = {2},
     year = {2012},
     doi = {10.4064/fm216-2-6},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4064/fm216-2-6/}
}
TY  - JOUR
AU  - Alessandro Berarducci
AU  - Pietro Majer
AU  - Matteo Novaga
TI  - Infinite paths and cliques in random graphs
JO  - Fundamenta Mathematicae
PY  - 2012
SP  - 163
EP  - 191
VL  - 216
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4064/fm216-2-6/
DO  - 10.4064/fm216-2-6
LA  - en
ID  - 10_4064_fm216_2_6
ER  - 
%0 Journal Article
%A Alessandro Berarducci
%A Pietro Majer
%A Matteo Novaga
%T Infinite paths and cliques in random graphs
%J Fundamenta Mathematicae
%D 2012
%P 163-191
%V 216
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4064/fm216-2-6/
%R 10.4064/fm216-2-6
%G en
%F 10_4064_fm216_2_6
Alessandro Berarducci; Pietro Majer; Matteo Novaga. Infinite paths and cliques in random graphs. Fundamenta Mathematicae, Tome 216 (2012) no. 2, pp. 163-191. doi: 10.4064/fm216-2-6

Cité par Sources :