Fractional Sylvester-Gallai theorems

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

We prove fractional analogs of the classical Sylvester-Gallai theorem. Our theorems translate local information about collinear triples in a set of points into global bounds on the dimension of the set. Specifically, we show that if for every points v in a finite set V d, there are at least δ|V| other points u ∈ V for which the line through v,u contains a third point in V, then the V resides in a (13/δ2)-dimensional affine subspace of d. This result, which is one of several variants we study, is motivated by questions in theoretical computer science and, in particular, from the area of error correcting codes. Our proofs combine algebraic, analytic, and combinatorial arguments. A key ingredient is a new lower bound for the rank of design matrices, specified only by conditions on their zero/non-zero pattern.

Original languageEnglish (US)
Pages (from-to)19213-19219
Number of pages7
JournalProceedings of the National Academy of Sciences of the United States of America
Volume110
Issue number48
DOIs
StatePublished - Nov 26 2013

All Science Journal Classification (ASJC) codes

  • General

Keywords

  • Discrete geometry
  • Line arrangements

Cite this