Sylvester-Gallai for Arrangements of Subspaces

Authors Zeev Dvir, Guangda Hu



PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.29.pdf
  • Filesize: 483 kB
  • 15 pages

Document Identifiers

Author Details

Zeev Dvir
Guangda Hu

Cite AsGet BibTex

Zeev Dvir and Guangda Hu. Sylvester-Gallai for Arrangements of Subspaces. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 29-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.SOCG.2015.29

Abstract

In this work we study arrangements of k-dimensional subspaces V_1,...,V_n over the complex numbers. Our main result shows that, if every pair V_a, V_b of subspaces is contained in a dependent triple (a triple V_a, V_b, V_c contained in a 2k-dimensional space), then the entire arrangement must be contained in a subspace whose dimension depends only on k (and not on n). The theorem holds under the assumption that the subspaces are pairwise non-intersecting (otherwise it is false). This generalizes the Sylvester-Gallai theorem (or Kelly's theorem for complex numbers), which proves the k=1 case. Our proof also handles arrangements in which we have many pairs (instead of all) appearing in dependent triples, generalizing the quantitative results of Barak et. al. One of the main ingredients in the proof is a strengthening of a theorem of Barthe (from the k=1 to k>1 case) proving the existence of a linear map that makes the angles between pairs of subspaces large on average. Such a mapping can be found, unless there is an obstruction in the form of a low dimensional subspace intersecting many of the spaces in the arrangement (in which case one can use a different argument to prove the main theorem).
Keywords
  • Sylvester-Gallai
  • Locally Correctable Codes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Boaz Barak, Zeev Dvir, Avi Wigderson, and Amir Yehudayoff. Fractional Sylvester-Gallai theorems. Proceedings of the National Academy of Sciences, 110(48):19213-19219, 2013. Google Scholar
  2. Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC'11, pages 519-528, 2011. Google Scholar
  3. Franck Barthe. On a reverse form of the Brascamp-Lieb inequality. Inventiones mathematicae, 134(2):335-361, 1998. Google Scholar
  4. P. Borwein and W. O. J. Moser. A survey of Sylvester’s problem and its generalizations. Aequationes Mathematicae, 40(1):111-135, 1990. Google Scholar
  5. Zeev Dvir. On matrix rigidity and locally self-correctable codes. computational complexity, 20(2):367-388, 2011. Google Scholar
  6. Zeev Dvir, Shubhangi Saraf, and Avi Wigderson. Breaking the quadratic barrier for 3-LCC’s over the reals. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC'14, pages 784-793, 2014. Google Scholar
  7. Zeev Dvir, Shubhangi Saraf, and Avi Wigderson. Improved rank bounds for design matrices and a new proof of Kelly’s theorem. Forum of Mathematics, Sigma, 2, 10 2014. Google Scholar
  8. Noam Elkies, Lou M Pretorius, and Konrad J Swanepoel. Sylvester-Gallai theorems for complex numbers and quaternions. Discrete & Computational Geometry, 35(3):361-373, 2006. Google Scholar
  9. P. Erdös, Richard Bellman, H. S. Wall, James Singer, and V. Thébault. Problems for solution: 4065-4069. The American Mathematical Monthly, 50(1):65-66, 1943. Google Scholar
  10. Sten Hansen. A generalization of a theorem of Sylvester on the lines determined by a finite point set. Mathematica Scandinavica, 16:175-180, 1965. Google Scholar
  11. L. M. Kelly. A resolution of the Sylvester-Gallai problem of J.-P. Serre. Discrete & Computational Geometry, 1(1):101-104, 1986. Google Scholar
  12. Peter D. Lax. Linear algebra and its applications. Pure and Applied Mathematics. Wiley-Interscience, 2007. Google Scholar
  13. E. Melchior. Uber vielseite der projektive ebene. Deutsche Math., 5:461-475, 1940. Google Scholar
  14. J. J. Sylvester. Mathematical question 11851. Educational Times, 59:98, 1893. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail