Erdős–Rényi Poissonized

Nicolas Curien

doi:10.5802/crmath.578

Article de recherche - Combinatoire, Probabilités

Erdős–Rényi Poissonized
[Erdős–Rényi poissonisé]

Nicolas Curien ¹

¹ Université Paris-Saclay

Comptes Rendus. Mathématique, Volume 362 (2024), pp. 649-656.

Résumé
Abstract

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.

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.

Reçu le : 2022-11-27
Révisé le : 2023-08-25
Accepté le : 2023-10-10
Publié le : 2024-07-09

DOI : 10.5802/crmath.578

Affiliations des auteurs :

Nicolas Curien ¹

¹ Université Paris-Saclay

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@article{CRMATH_2024__362_G6_649_0,
     author = {Nicolas Curien},
     title = {Erd\H{o}s{\textendash}R\'enyi {Poissonized}},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {649--656},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {362},
     year = {2024},
     doi = {10.5802/crmath.578},
     language = {en},
}

TY  - JOUR
AU  - Nicolas Curien
TI  - Erdős–Rényi Poissonized
JO  - Comptes Rendus. Mathématique
PY  - 2024
SP  - 649
EP  - 656
VL  - 362
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.578
LA  - en
ID  - CRMATH_2024__362_G6_649_0
ER  -

%0 Journal Article
%A Nicolas Curien
%T Erdős–Rényi Poissonized
%J Comptes Rendus. Mathématique
%D 2024
%P 649-656
%V 362
%I Académie des sciences, Paris
%R 10.5802/crmath.578
%G en
%F CRMATH_2024__362_G6_649_0

Nicolas Curien. Erdős–Rényi Poissonized. Comptes Rendus. Mathématique, Volume 362 (2024), pp. 649-656. doi : 10.5802/crmath.578. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.578/

Bibliographie
Cité par

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

[2] B. Bollobás; O. Riordan 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

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

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

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

Cité par Sources :

Commentaires - Politique