Probabilités sur le graphe complet : l’exemple des arbres couvrants uniforme et minimal
Grégory Miermont1
1 Université de Lyon, ÉNS de Lyon & Institut Universitaire de France
Journées mathématiques X-UPS, Arbres et marches aléatoires (2016), pp. 59-102.

Ce texte propose quelques exemples d’analyse de grandes structures combinatoires aléatoires, que l’on peut définir naturellement en termes de modèles simples d’arbres couvrants sur le graphe complet.

Publié le :
DOI : 10.5802/xups.2016-02
Grégory Miermont 1

1 Université de Lyon, ÉNS de Lyon & Institut Universitaire de France 
@incollection{XUPS_2016____59_0,
     author = {Gr\'egory Miermont},
     title = {Probabilit\'es sur le graphe complet~: l{\textquoteright}exemple des arbres couvrants uniforme et minimal},
     booktitle = {Arbres et marches al\'eatoires},
     series = {Journ\'ees math\'ematiques X-UPS},
     pages = {59--102},
     publisher = {Les \'Editions de l{\textquoteright}\'Ecole polytechnique},
     year = {2016},
     doi = {10.5802/xups.2016-02},
     language = {fr},
     url = {https://proceedings.centre-mersenne.org/articles/10.5802/xups.2016-02/}
}
TY  - JOUR
AU  - Grégory Miermont
TI  - Probabilités sur le graphe complet : l’exemple des arbres couvrants uniforme et minimal
JO  - Journées mathématiques X-UPS
PY  - 2016
SP  - 59
EP  - 102
PB  - Les Éditions de l’École polytechnique
UR  - https://proceedings.centre-mersenne.org/articles/10.5802/xups.2016-02/
DO  - 10.5802/xups.2016-02
LA  - fr
ID  - XUPS_2016____59_0
ER  - 
%0 Journal Article
%A Grégory Miermont
%T Probabilités sur le graphe complet : l’exemple des arbres couvrants uniforme et minimal
%J Journées mathématiques X-UPS
%D 2016
%P 59-102
%I Les Éditions de l’École polytechnique
%U https://proceedings.centre-mersenne.org/articles/10.5802/xups.2016-02/
%R 10.5802/xups.2016-02
%G fr
%F XUPS_2016____59_0
Grégory Miermont. Probabilités sur le graphe complet : l’exemple des arbres couvrants uniforme et minimal. Journées mathématiques X-UPS, Arbres et marches aléatoires (2016), pp. 59-102. doi : 10.5802/xups.2016-02. https://proceedings.centre-mersenne.org/articles/10.5802/xups.2016-02/

[ABBG10] L. Addario-Berry; N. Broutin; C. Goldschmidt Critical random graphs : limiting constructions and distributional properties, Electron. J. Probab., Volume 15 (2010), p. 741-775, art.  no. 25, | DOI | MR | Zbl

[ABBG12] L. Addario-Berry; N. Broutin; C. Goldschmidt The continuum limit of critical random graphs, Probab. Theory Relat. Fields, Volume 152 (2012) no. 3-4, pp. 367-406 | DOI | MR | Zbl

[ABBGM17] L. Addario-Berry; N. Broutin; C. Goldschmidt; G. Miermont The scaling limit of the minimum spanning tree of the complete graph, Ann. Probab., Volume 45 (2017) no. 5, pp. 3075-3144 | DOI | MR | Zbl

[Ald90] D. Aldous The random walk construction of uniform spanning trees and uniform labelled trees, SIAM J. Discrete Math., Volume 3 (1990) no. 4, pp. 450-465 | DOI | MR | Zbl

[Ald91] D. Aldous The continuum random tree. I, Ann. Probab., Volume 19 (1991) no. 1, pp. 1-28 | DOI | MR | Zbl

[Ald92] D. Aldous Asymptotics in the random assignment problem, Probab. Theory Relat. Fields, Volume 93 (1992) no. 4, pp. 507-534 | DOI | MR | Zbl

[Ald93] D. Aldous The continuum random tree. III, Ann. Probab., Volume 21 (1993) no. 1, pp. 248-289 | DOI | MR | Zbl

[AP98] D. Aldous; J. Pitman The standard additive coalescent, Ann. Probab., Volume 26 (1998) no. 4, pp. 1703-1726 | DOI | MR | Zbl

[AS92] D. Aldous; J. M. Steele Asymptotics for Euclidean minimal spanning trees on random points, Probab. Theory Relat. Fields, Volume 92 (1992) no. 2, pp. 247-258 | DOI | MR | Zbl

[AS04] D. Aldous; J. M. Steele The objective method : probabilistic combinatorial optimization and local weak convergence, Probability on discrete structures (Encyclopaedia Math. Sci.), Volume 110, Springer, Berlin, 2004, pp. 1-72 | DOI | MR | Zbl

[BBI01] D. Burago; Y. Burago; S. Ivanov A course in metric geometry, Graduate Studies in Math., 33, American Mathematical Society, Providence, RI, 2001 | DOI | MR

[Ber06] J. Bertoin Random fragmentation and coagulation processes, Cambridge Studies in Advanced Math., 102, Cambridge University Press, Cambridge, 2006 | DOI | MR

[BS01] I. Benjamini; O. Schramm Recurrence of distributional limits of finite planar graphs, Electron. J. Probab., Volume 6 (2001), 23 | DOI | MR | Zbl

[CL02] P. Chassaing; G. Louchard Phase transition for parking blocks, Brownian excursion and coalescence, Random Structures Algorithms, Volume 21 (2002) no. 1, pp. 76-119 | DOI | MR | Zbl

[CP00] M. Camarri; J. Pitman Limit distributions and random trees derived from the birthday problem with unequal probabilities, Electron. J. Probab., Volume 5 (2000), 2 | DOI | MR | Zbl

[DLG05] T. Duquesne; J.-F. Le Gall Probabilistic and fractal aspects of Lévy trees, Probab. Theory Relat. Fields, Volume 131 (2005) no. 4, pp. 553-603 | DOI | MR | Zbl

[DS98] E. Derbez; G. Slade The scaling limit of lattice trees in high dimensions, Comm. Math. Phys., Volume 193 (1998) no. 1, pp. 69-104 | DOI | MR | Zbl

[ER60] P. Erdős; A. Rényi On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl., Volume 5 (1960), pp. 17-61 | MR | Zbl

[Fri85] A. M. Frieze On the value of a random minimum spanning tree problem, Discrete Appl. Math., Volume 10 (1985) no. 1, pp. 47-56 | DOI | MR | Zbl

[Kor16] Igor Kortchemski Arbres et marches aléatoires, Arbres et marches aléatoires (Journées X-UPS), Les Éditions de l’École polytechnique, Palaiseau, 2016 (ce volume) | DOI | MR | Zbl

[LG93] Jean-François Le Gall The uniform random tree in a Brownian excursion, Probab. Theory Relat. Fields, Volume 96 (1993) no. 3, pp. 369-383 | DOI | MR | Zbl

[LG05] Jean-François Le Gall Random trees and applications, Probab. Surv., Volume 2 (2005), pp. 245-311 | DOI | MR | Zbl

[LGM12] Jean-François Le Gall; G. Miermont Scaling limits of random trees and planar maps, Probability and statistical physics in two and more dimensions (Clay Math. Proc.), Volume 15, American Mathematical Society, Providence, RI, 2012, pp. 155-211 | MR | Zbl

[NP89] J. Neveu; J. Pitman The branching process in a Brownian excursion, Séminaire de Probabilités, XXIII (Lect. Notes in Math.), Volume 1372, Springer, Berlin, 1989, pp. 248-257 | DOI | Numdam | MR | Zbl

[Pit99] J. Pitman Coalescent random forests, J. Combin. Theory Ser. A, Volume 85 (1999) no. 2, pp. 165-193 | DOI | MR | Zbl

[Wil96] D. B. Wilson Generating random spanning trees more quickly than the cover time, Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), ACM, New York, 1996, pp. 296-303 | DOI | MR | Zbl

Cité par Sources :