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:Isaac Newton Institute Seminar Series
SUMMARY:Steiner trees in the stochastic mean-field model o
f distance - Ayalvadi Ganesh (University of Bristo
l)
DTSTART;TZID=Europe/London:20161103T140000
DTEND;TZID=Europe/London:20161103T150000
UID:TALK68761AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/68761
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 t
his result to show that the worst case k-Steiner t
ree\, over all choices of k nodes\, has weight sca
ling as (2k-1)log n/n. \; Further\, Janson
derived the limiting distribution of the typical d
istance between two nodes. We refine the result of
Bollobas et al. and present 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. \; This is joint wor
k with Angus Davidson and Balint Toth.
LOCATION:Seminar Room 2\, Newton Institute
CONTACT:INI IT
END:VEVENT
END:VCALENDAR