BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Probability
SUMMARY:Steiner trees in the stochastic mean-field model o
f distance - Ayalvadi Ganesh (Bristol)
DTSTART;TZID=Europe/London:20160308T163000
DTEND;TZID=Europe/London:20160308T173000
UID:TALK64960AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/64960
DESCRIPTION:Consider the complete graph on n nodes with iid ex
ponential weights of unit mean on the edges. A num
ber of properties of this model have been investig
ated including first passage percolation\, diamete
r\, minimum spanning tree\, etc. In particular\, J
anson showed that the typical distance between two
nodes scales as (log n)/n\, whereas the diameter
(maximum distance between any two nodes) scales as
3(log n)/n. Bollobas et al. showed that\, for any
fixed k\, the weight of the Steiner tree connecti
ng k typical nodes scales as (k-1)log n/n\, which
recovers Janson's result for k=2. We extend this r
esult to show that the worst case k-Steiner tree\,
over all choices of k nodes\, has weight scaling
as (2k-1)log n/n.\n\nFurther\, Janson derived the
limiting distribution of the typical distance betw
een two nodes. We refine the result of Bollobas et
al. and present a perhaps surprising result in th
is direction for the typical Steiner tree which ha
s implications for the limiting shape of the 3-Ste
iner tree.\n\nThis is joint work with Angus Davids
on and Balint Toth.
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0W
B
CONTACT:Perla Sousi
END:VEVENT
END:VCALENDAR