Sylvester-Gallai for Arrangements of Subspaces

Zeev Dvir, Guangda Hu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this work we study arrangements of κ-dimensional subspaces V1, . . . , Vn ⊂ Cl. Our main result shows that, if every pair Va, Vb of subspaces is contained in a dependent triple (a triple Va, Vb, Vc contained in a 2κ-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 Va \ Vb = {0} for every pair (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. [1]. One of the main ingredients in the proof is a strengthening of a theorem of Barthe [3] (from the k = 1 to κ>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).

Original languageEnglish (US)
Title of host publication31st International Symposium on Computational Geometry, SoCG 2015
EditorsJanos Pach, Janos Pach, Lars Arge
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages29-43
Number of pages15
ISBN (Electronic)9783939897835
DOIs
StatePublished - Jun 1 2015
Event31st International Symposium on Computational Geometry, SoCG 2015 - Eindhoven, Netherlands
Duration: Jun 22 2015Jun 25 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume34
ISSN (Print)1868-8969

Other

Other31st International Symposium on Computational Geometry, SoCG 2015
Country/TerritoryNetherlands
CityEindhoven
Period6/22/156/25/15

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Locally Correctable Codes
  • Sylvester-Gallai

Fingerprint

Dive into the research topics of 'Sylvester-Gallai for Arrangements of Subspaces'. Together they form a unique fingerprint.

Cite this