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.
|Number of pages
|Proceedings of the National Academy of Sciences of the United States of America
|Published - Nov 26 2013
All Science Journal Classification (ASJC) codes
- Discrete geometry
- Line arrangements