Graduate Programs      Graduate Home Ph D Programs Masters Degree Ph D Program Requirements Course Descriptions Current Courses Admissions Current Graduate Students Graduate Student Seminar SIAM Chapter Seminar Recent Graduates Incoming Students Graduate Seminar Tony Johansson Carnegie Mellon University Title: Random optimization on graphs and Riemann's zeta function Abstract: In 1985, Frieze found a surprising connection between random graph optimization and the zeta function; in a complete graph with uniformly random $[0, 1]$ cost, the min-cost spanning tree has expected total cost $\zeta(3)$. It was later conjectured that the minimum spanning tree in a complete bipartite graph with exponentially distributed costs with mean $1$ has expected total cost $\zeta(2)$. This was proved independently by two groups in 2004-2005 before Wastlund came up with a short proof in 2009. I will present this proof, and a generalization of the proof to regular bipartite graphs.Date: Thursday, April 2, 2015Time: 5:30 pmLocation: Wean Hall 8220Submitted by:  Zilin Jiang