# Successive shortest paths

• Stefanie Gerke (Royal Holloway UL)
• Thursday 02 May 2019, 14:30-15:30
• MR12.

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 shortest path $P_2$ to be the cheapest path edge-disjoint from $P_1$, and consider more generally the cheapest path $P_k$ edge-disjoint from all earlier paths. We show that for $k=o(n^{1/3})$, the cost of $P_k$ converges in probability to $\ln n \, / \, n + 2k/n$, and we conjecture that a certain mild adaptation of this formula holds up 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 and Gregory Sorkin.

This talk is part of the Combinatorics Seminar series.