Graduate Students
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

Apply Now
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, 2015
Time: 5:30 pm
Location: Wean Hall 8220
Submitted by:  Zilin Jiang