Discrete Geometry and Combinatorics Seminar

Lou BilleraCornell University
In pursuit of a white whale: On the real linear algebra of vectors of zeros and ones

Monday, August 28, 2017 - 2:30pm
Malott 206

In particular, in many applications it is of interest to know the number of regions in $\mathbb{R}^{n}$ that are determined by the set of $2^{n}-1$ linear hyperplanes having 0-1 normals. This number, known asymptotically to be on the order of $2^{n^{2}}$, can be obtained exactly from the characteristic polynomial of the geometric lattice of all subspaces spanned over $\mathbb{R}$ by these 0-1 vectors. These characteristic polynomials are known only through $n=7$, while just the number of regions is known for $n=8$.

This question has roots that trace back to the first problem I was given as an aspiring game theorist almost exactly 51 years ago. Needless to say, I never solved that problem.

We discuss several contexts in which this question has come up, describe various general approaches toward obtaining the characteristic polynomial, and give some very partial results toward a general solution. My main purpose here is to try to arouse some interest in this question. As in the fictional tale of the white whale, it's been a very interesting journey, passing through many different (relatively exotic) regions of mathematics.