Probabilités sur le graphe complet : l’exemple des arbres couvrants uniforme et minimal
Miermont, Grégory1
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
Miermont, Grégory 1

1 Université de Lyon, ÉNS de Lyon & Institut Universitaire de France 
@incollection{XUPS_2016____59_0,
     author = {Miermont, Gr\'egory},
     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 = {http://archive.numdam.org/articles/10.5802/xups.2016-02/}
}
TY  - JOUR
AU  - Miermont, Grégory
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  - http://archive.numdam.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 Miermont, Grégory
%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 http://archive.numdam.org/articles/10.5802/xups.2016-02/
%R 10.5802/xups.2016-02
%G fr
%F XUPS_2016____59_0
Miermont, Grégory. 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. http://archive.numdam.org/articles/10.5802/xups.2016-02/

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

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

[ABBGM17] Addario-Berry, L.; Broutin, N.; Goldschmidt, C.; Miermont, G. 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] Aldous, D. 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] Aldous, D. The continuum random tree. I, Ann. Probab., Volume 19 (1991) no. 1, pp. 1-28 | DOI | MR | Zbl

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

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

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

[AS92] Aldous, D.; Steele, J. M. 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] Aldous, D.; Steele, J. M. 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] Burago, D.; Burago, Y.; Ivanov, S. A course in metric geometry, Graduate Studies in Math., 33, American Mathematical Society, Providence, RI, 2001 | DOI | MR

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

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

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

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

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

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

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

[Fri85] Frieze, A. M. 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] Kortchemski, Igor 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] Le Gall, Jean-François The uniform random tree in a Brownian excursion, Probab. Theory Relat. Fields, Volume 96 (1993) no. 3, pp. 369-383 | DOI | MR | Zbl

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

[LGM12] Le Gall, Jean-François; Miermont, G. 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] Neveu, J.; Pitman, J. 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] Pitman, J. Coalescent random forests, J. Combin. Theory Ser. A, Volume 85 (1999) no. 2, pp. 165-193 | DOI | MR | Zbl

[Wil96] Wilson, D. B. 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 :