Erdős–Rényi Poissonized

Nicolas Curien

doi:10.5802/crmath.578

Research article - Combinatorics, Probability theory

Erdős–Rényi Poissonized

Nicolas Curien ¹

¹ Université Paris-Saclay

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

Abstract
Résumé

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.

Received: 2022-11-27
Revised: 2023-08-25
Accepted: 2023-10-10
Published online: 2024-07-09

DOI: 10.5802/crmath.578

Author's affiliations:

Nicolas Curien ¹

¹ Université Paris-Saclay

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@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/

References
Cited by

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

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

Cited by Sources:

Comments - Policy