BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Steiner trees in the stochastic mean-field model of distance - Aya
 lvadi Ganesh (Bristol)
DTSTART:20160308T163000Z
DTEND:20160308T173000Z
UID:TALK64960@talks.cam.ac.uk
CONTACT:Perla Sousi
DESCRIPTION:Consider the complete graph on n nodes with iid exponential we
 ights of unit mean on the edges. A number of properties of this model have
  been investigated including first passage percolation\, diameter\, minimu
 m spanning tree\, etc. In particular\, Janson showed that the typical dist
 ance 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. sho
 wed that\, for any fixed k\, the weight of the Steiner tree connecting k t
 ypical nodes scales as (k-1)log n/n\, which recovers Janson's result for k
 =2. We extend this result to show that the worst case k-Steiner tree\, ove
 r 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 betwee
 n two nodes. We refine the result of Bollobas et al. and present a perhaps
  surprising result in this direction for the typical Steiner tree which ha
 s implications for the limiting shape of the 3-Steiner tree.\n\nThis is jo
 int work with Angus Davidson and Balint Toth.
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0WB
END:VEVENT
END:VCALENDAR