Title: Points, Lines and Ranks of Design Matrices
Speaker: Avi Wigderson, IAS Princeton
Date: Wednesday, February 13, 2013
Time: 2:00pm – 3:00pm
Place: Lecture Hall 102, Simons Center
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 must 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. We also address “robust” versions in which triples of points are “nearly collinear”. 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.
No special background is required.
Based on several joint works with Albert Ai, Boaz Barak, Zeev Dvir, Shubhangi Saraf and Amir Yehudayoff.