TY - GEN
T1 - Sylvester-Gallai for Arrangements of Subspaces
AU - Dvir, Zeev
AU - Hu, Guangda
PY - 2015/6/1
Y1 - 2015/6/1
N2 - 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).
AB - 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).
KW - Locally Correctable Codes
KW - Sylvester-Gallai
UR - http://www.scopus.com/inward/record.url?scp=84958182842&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958182842&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SOCG.2015.29
DO - 10.4230/LIPIcs.SOCG.2015.29
M3 - Conference contribution
AN - SCOPUS:84958182842
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 29
EP - 43
BT - 31st International Symposium on Computational Geometry, SoCG 2015
A2 - Pach, Janos
A2 - Pach, Janos
A2 - Arge, Lars
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 31st International Symposium on Computational Geometry, SoCG 2015
Y2 - 22 June 2015 through 25 June 2015
ER -