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 (University of Bristol)
DTSTART:20161103T140000Z
DTEND:20161103T150000Z
UID:TALK68761@talks.cam.ac.uk
CONTACT:INI IT
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&#39\;s result 
 for k=2. We extend this result to show that the worst case k-Steiner tree\
 , over all choices of k nodes\, has weight scaling as (2k-1)log n/n.  &nbs
 p\;  Further\, Janson derived the limiting distribution of the typical dis
 tance between two nodes. We refine the result of Bollobas et al. and prese
 nt a perhaps surprising result in this direction for the typical Steiner t
 ree which has implications for the limiting shape of the 3-Steiner tree.  
 &nbsp\;  This is joint work with Angus Davidson and Balint Toth.
LOCATION:Seminar Room 2\, Newton Institute
END:VEVENT
END:VCALENDAR