no. G6
Article de recherche - Combinatoire, Probabilités
Erdős–Rényi Poissonized
[Erdős–Rényi poissonisé]
Curien, Nicolas1
1Université Paris-Saclay
Comptes Rendus. Mathématique, Tome 362 (2024) no. G6, pp. 649-656

We introduce a variant of the Erdős–Rényi random graph where the number of vertices is random and follows a Poisson law. A very simple Markov property of the model entails that the Lukasiewicz exploration is made of independent Poisson increments. Using a vanilla Poisson counting process, this enables us to give very short proofs of classical results such as the phase transition for the giant component or the connectedness for the standard Erdős–Rényi model.

On introduit une variante du graphe d’Erdős–Rényi où le nombre de sommets est aléatoire et suit une loi de Poisson. Une propriété de Markov du graphe montre que le chemin de Lukasiewicz a des incréments indépendants. Cela permet de retrouver des résultats classiques comme la transition de phase pour l’existence de la composante géante en utilisant simplement des propriétés standards des processus de comptage de Poisson.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/crmath.578

Curien, Nicolas  1

1 Université Paris-Saclay
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits
@article{CRMATH_2024__362_G6_649_0,
     author = {Curien, Nicolas},
     title = {Erd\H{o}s{\textendash}R\'enyi {Poissonized}},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {649--656},
     year = {2024},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {362},
     number = {G6},
     doi = {10.5802/crmath.578},
     language = {en},
     url = {https://www.numdam.org/articles/10.5802/crmath.578/}
}
TY  - JOUR
AU  - Curien, Nicolas
TI  - Erdős–Rényi Poissonized
JO  - Comptes Rendus. Mathématique
PY  - 2024
SP  - 649
EP  - 656
VL  - 362
IS  - G6
PB  - Académie des sciences, Paris
UR  - https://www.numdam.org/articles/10.5802/crmath.578/
DO  - 10.5802/crmath.578
LA  - en
ID  - CRMATH_2024__362_G6_649_0
ER  - 
%0 Journal Article
%A Curien, Nicolas
%T Erdős–Rényi Poissonized
%J Comptes Rendus. Mathématique
%D 2024
%P 649-656
%V 362
%N G6
%I Académie des sciences, Paris
%U https://www.numdam.org/articles/10.5802/crmath.578/
%R 10.5802/crmath.578
%G en
%F CRMATH_2024__362_G6_649_0
Curien, Nicolas. Erdős–Rényi Poissonized. Comptes Rendus. Mathématique, Tome 362 (2024) no. G6, pp. 649-656. doi: 10.5802/crmath.578

[1] Aldous, D. Brownian excursions, critical random graphs and the multiplicative coalescent, Ann. Probab., Volume 25 (1997) no. 2, pp. 812-854 | DOI | Zbl | MR

[2] Bollobás, B.; Riordan, O. Asymptotic normality of the size of the giant component via a random walk, J. Comb. Theory, Ser. B, Volume 102 (2012), pp. 53-61 | DOI | Zbl | MR

[3] Erdős, P.; Rényi, A. On random graphs. I, Publ. Math. Debr., Volume 6 (1959), pp. 290-297 | Zbl | DOI | MR

[4] Erdős, P.; Rényi, A. On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci., Ser. A, Volume 5 (1960), pp. 17-60 | Zbl

[5] Pittel, B. On tree census and the giant component in sparse random graphs, Random Struct. Algorithms, Volume 1 (1990) no. 3, pp. 311-342 | DOI | Zbl | MR

Cité par Sources :