Configurations of points with many collinear triples: going beyond Sylvester-Gallai
speaker: Zeev Dvir (Princeton University)abstract: The Sylvester-Gallai theorem states that a configuration of points in Rn in which every pair is in some collinear triple, has to lie on a single line. I will discuss some recent results that go beyond this theorem, dealing with more robust scenarios. The first type of results deal with configurations in which many pairs are in collinear triples. For example: If a constant fraction of the pairs are in a collinear triple then there is a constant fraction of the points that lie in a subspace of constant dimension. Another type of results deal with configurations in which there are many almost, or epsilon-collinear triples (that is, points that are epsilon-close to being on a line). We will see that, under some uniformity conditions on the distances between points, one can find a subspace of low dimension that approximates all (or most) of the points. All of these results, which deal with points in complex space, are obtained by understanding the rank (or, more generally, the number of small singular values) of sparse complex matrices with specific patterns of zerosnon-zeros.
Based on joint works with Albert Ai, Boaz Barak, Subhangi Saraf, Avi Wigderson and Amir Yehudayoff.
timetable:
Mon 3 Sep, 10:30 - 11:30, Aula Dini
Tue 4 Sep, 14:00 - 15:00, Aula Dini
<< Go back