BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Successive shortest paths - Stefanie Gerke (Royal Holloway UL)
DTSTART:20190502T133000Z
DTEND:20190502T143000Z
UID:TALK120649@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:The cost of the shortest path $P_1$ in a complete graph $K_n$ 
 with random edge weights is known to converge in probability to $\\ln n / 
 n$. We define a second\nshortest path $P_2$ to be the cheapest path edge-d
 isjoint from $P_1$\, and consider more generally the cheapest path $P_k$ e
 dge-disjoint from all earlier paths. We show that for $k=o(n^{1/3})$\, the
  cost of $P_k$ converges in\nprobability to $\\ln n \\\, / \\\, n + 2k/n$\
 , and we conjecture that a certain mild adaptation of this formula holds u
 p to $k=n-o(n)$. We then hint how this result can be improved for fixed $k
 $. This talk is based on joint work with Paul Balister and Balazs Mezei an
 d Gregory Sorkin.\n
LOCATION:MR12
END:VEVENT
END:VCALENDAR