turkmath.org

I will talk about recent work of Adam Marcus, Daniel Spielman and Nikhil Srivastava(MSS) where they use ideas from combinatorics and spectral graph theory to settle several important problems in computer science and mathematics. Two of these are constructions of Ramanjuan graphs(expander graphs with the best possible expansion constants) and a solution of the famous Kadison-Singer problem. Ramanujan graphs were first constructed by Lubotzy, Philips and Sarnak and independently by Margulis using deep ideas from number theory and geometric group theory respectively. MSS provided a new construction in 2013, using more or less elementary ideas, a construction that further removes important numerical restrictions in all prior work. The Kadison-Singer problem was one of the thorniest problems in operator algebras till it was settled by this trio, also in 2013. The problem is further related to dozens of problems in areas as disparate as C* algebras, signal processing and harmonic analysis. Notably, a majority of the mathematical community expected a negative solution to the problem, an expectation that was confounded by Marcus, Spielman and Srivastava. The techniques of their proofs are both remarkably elementary, requiring little more than linear algebra and extremely powerful. I expect to even be able to sketch their proofs within the time allocated to the talk.