University of Cambridge > Talks.cam > Combinatorics Seminar > Successive shortest paths

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Successive shortest paths

Download to your calendar using vCal

  • UserStefanie Gerke (Royal Holloway UL)
  • ClockThursday 02 May 2019, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact Andrew Thomason .

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Goldsmiths 2 & https://us06web.zoom.us/j/81688365420?pwd=b3RpdHgxNVhWbWQrbXluMUxYNWVtQT09 Meeting ID: 816 8836 5420 Passcode: 047859 Critical Theory and Practice Seminar Series Rooms 8 & 9, Faculty of Asian & Middle Eastern Studies

Other talks

Title to follow Title TBC Title TBC FILM: One With The Whale Title and abstract tba TBC
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity