Tag Archives: expander


The Kadison-Singer Problem is an old question from von Neumann algebra theory, whose roots lie in Dirac’s writings on quantum mechanics. Its classical expression is as follows: Consider the algebra \(B\) of all bounded operators on a separable Hilbert space, and the maximal abelian subalgebra \(D\) of all diagonal operators (relative to some fixed orthonormal basis).  Does every pure state of \(D\) extend uniquely to a pure state of \(B\)?

Some remarks of Dirac can be read as asserting that the answer should be “yes”, not merely for \(D\) but for every masa.  For other masa’s this is definitely false, but the original question remained tantalizingly open.  Penn State’s Joel Anderson showed in the seventies or early eighties how to relate this question to a number of other “paving” problems, including some which are purely finite-dimensional.  More recently these have gotten connected to engineering questions in signal processing and time-frequency analysis.

This summer, the problem has finally been solved (affirmatively) by finite-dimensional methods.  As I understand it, these methods have to do with “discrepancy theory”: you have a large number of individually not-too-large objects (here vectors in a Euclidean space) and you want to split them into two subsets in such a way that some notion of “total mass” is evenly distributed between the two subsets.  The catch here is that the “total mass” is measured by a quadratic form

\[ \sum_{v\in S} \langle x,v\rangle^2 \]

defined on the whole unit sphere in \({\mathbb R}^n\).  The method does not just prove Kadison-Singer but also gives an procedure for splitting any reasonably well-connected graph into two sparser but still well-connected graphs; iterating this constructs expanders.

There’s lots of good writing about this online: see some references below.


Anderson, J., 1979. Extensions, restrictions, and representations of states on C*-algebras. Trans. Amer. Math. Soc. 249, 303–329.

Casazza, P.G., Tremain, J.C., 2006. The Kadison–Singer Problem in mathematics and engineering. PNAS 103, 2032–2039.

Harvey, N., 2013. An introduction to the Kadison-Singer problem and the paving conjecture.

Marcus, A., Spielman, D.A., Srivastava, N., 2013a. Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees (arXiv e-print No. 1304.4132).

Marcus, A., Spielman, D.A., Srivastava, N., 2013b. Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem (arXiv e-print No. 1306.3969).

Srivastava, N., 2013. Discrepancy, Graphs, and the Kadison-Singer Problem [WWW Document]. Windows On Theory. URL http://windowsontheory.org/2013/07/11/discrepancy-graphs-and-the-kadison-singer-conjecture-2/ (accessed 9.9.13).


A last-minute extra talk was scheduled on the Wednesday morning at the Banff meeting – Assaf Naor on Superexpanders.  I would have loved to attend that talk, but I had a prior commitment to Aftenroe, a beautiful eight-pitch limestone climb above the road to Lake Louise.

Fortunately, thanks to the video system at BIRS, this doesn’t mean that I missed the talk.   One can find the excellent video of the talk here.  It’s a great presentation, as gratifying and elegant as Aftenroe‘s third pitch.  Below, I will try to describe some of the ideas. Continue reading