BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Département de mathématiques et applications - ECPv6.2.2//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Département de mathématiques et applications
X-ORIGINAL-URL:https://www.math.ens.psl.eu
X-WR-CALDESC:évènements pour Département de mathématiques et applications
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20140330T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20141026T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20140303T110000
DTEND;TZID=Europe/Paris:20140303T120000
DTSTAMP:20260410T194351
CREATED:20140303T100000Z
LAST-MODIFIED:20211104T095154Z
UID:8177-1393844400-1393848000@www.math.ens.psl.eu
SUMMARY:The scaling limit of the minimum spanning tree of the complete graph
DESCRIPTION:Consider the complete graph on n vertices with independent andidentically distributed edge-weights having some absolutely continuousdistribution. The minimum spanning tree (MST) is simply the spanningsubtree of smallest weight.  It is straightforward to construct theMST using one of several natural algorithms. Kruskal’s algorithmbuilds the tree edge by edge starting from the globally lowest-weightedge and then adding other edges one by one in increasing order ofweight\, as long as they do not create any cycles. At each step of thisprocess\, the algorithm has generated a forest\, which becomes connectedon the final step. In this talk\, I will explain how it is possible toexploit a connection between the forest generated by Kruskal’salgorithm and the Erdös-Rényi random graph in order to prove that M_n\,the MST of the complete graph\, possesses a scaling limit as n tends toinfinity.  In particular\, if we think of M_n as a metric space (usingthe graph distance)\, rescale edge-lengths by n^{-1/3}\, and endow thevertices with the uniform measure\, then M_n converges in distributionin the sense of the Gromov-Hausdorff-Prokhorov distance to a certainrandom measured real tree.This is joint work with Louigi Addario-Berry (McGill)\, Nicolas Broutin(INRIA Paris-Rocquencourt) and Grégory Miermont (ENS Lyon).
URL:https://www.math.ens.psl.eu/evenement/the-scaling-limit-of-the-minimum-spanning-tree-of-the-complete-graph/
LOCATION:Salle W
CATEGORIES:Séminaire informel de probabilités
END:VEVENT
END:VCALENDAR