Speaker:  Lou Billera, Cornell University
Title: In pursuit of a white whale: On the real linear algebra of vectors of zeros and ones
Time: 2:30 PM, Monday, August 28, 2017
Place:  Malott 206

Abstract: We are interested in understanding the real linear relations among the set of all 0-1 vectors in $\mathbb{R}^{n}$, that is, the linear matroid over $\mathbb{R}$ of the set of the $2^n -1$ nonzero $n$-vectors, all of whose coordinates are 0 or 1. Equivalently, we seek the affine real matroid of all barycenters of nonempty faces of an (n-1)-dimensional simplex. This fundamental combinatorial object is behind questions that have arisen over the past 50 years in a variety of fields, from economics to circuit theory to quantum physics. (This is roughly the same period during which much of modern enumerative combinatorics was being developed.) There are even traces to an 1893 problem of Hadamard. Yet there has been little real progress in understanding some of the most basic questions here.

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.


Back to main seminar page.