License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.29
URN: urn:nbn:de:0030-drops-51303
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5130/
Go to the corresponding LIPIcs Volume Portal

Dvir, Zeev ; Hu, Guangda

Sylvester-Gallai for Arrangements of Subspaces

pdf-format:
47.pdf (0.5 MB)

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).

BibTeX - Entry

@InProceedings{dvir_et_al:LIPIcs:2015:5130,
  author =	{Zeev Dvir and Guangda Hu},
  title =	{{Sylvester-Gallai for Arrangements of Subspaces}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{29--43},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5130},
  URN =		{urn:nbn:de:0030-drops-51303},
  doi =		{10.4230/LIPIcs.SOCG.2015.29},
  annote =	{Keywords: Sylvester-Gallai, Locally Correctable Codes}
}

Keywords: Sylvester-Gallai, Locally Correctable Codes
Collection: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 12.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI