Videos

Points, Lines and Ranks of Design Matrices<br><em>Introduced by: Bill Steiger</em>

Presenter
November 29, 2012
Keywords:
  • Design Matrices
Abstract
The Sylvester-Gallai theorem in Euclidean geometry asserts that if a set of points has the property that every line through two of them contains a third point (such lines are called "special"), then they must all be on the same line, namely, 1-dimensional. There are many proofs, all elementary. When one moves to the complex numbers the same condition can be met in two dimensions, and Kelly's theorem asserts that the points mus lie in a 2-dimensional space. The first proof used algebraic geometry, and a later more elementary proof of this fact is still quite complicated. We prove several extensions and quantitative versions of these theorems (and related ones), in which the assumption is relaxed to having "many" special lines in the given point set (but not all), still imply a constant upper bound on the dimension of the point set. We also address "robust" versions in which triples of points are "nearly collinear" - here we infer that all points are "close" to a low dimensional subspace. These relaxations are motivated from questions about locally correctable codes, matrix rigidity, arithmetic combinatorics and more. Our results are obtained via general, tight rank lower bounds on matrices about with certain zero/non-zero pattern of entries. The proofs use an interesting combination of combinatorial, algebraic and analytic tools. In particular, they supply a simple new proof of Kelly's theorem. Based on several joint works with Albert Ai, Boaz Barak, Zeev Dvir, Shubhangi Saraf and Amir Yehudayoff.