Dvir, Zeev ;
Hu, Guangda
SylvesterGallai for Arrangements of Subspaces
Abstract
In this work we study arrangements of kdimensional 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 2kdimensional 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 nonintersecting (otherwise it is false). This generalizes the SylvesterGallai 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 = {{SylvesterGallai for Arrangements of Subspaces}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {2943},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897835},
ISSN = {18688969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5130},
URN = {urn:nbn:de:0030drops51303},
doi = {10.4230/LIPIcs.SOCG.2015.29},
annote = {Keywords: SylvesterGallai, Locally Correctable Codes}
}
12.06.2015
Keywords: 

SylvesterGallai, Locally Correctable Codes 
Seminar: 

31st International Symposium on Computational Geometry (SoCG 2015)

Issue date: 

2015 
Date of publication: 

12.06.2015 