Kakeya-type sets in finite vector spaces
- Saraf, Shubhangi
- Kopparty, Swastik
- Sudan, Madhu
- Lev, Vsevolod F.
Publication date
January 2011
DOI Publisher
Springer Science and Business Media LLC ISSN
0925-9899 Journal
Journal of Algebraic Combinatorics Citation count (estimate)
4Abstract
For a finite vector space V and a nonnegative integer r≤dim V, we estimate the smallest possible size of a subset of V, containing a translate of every r-dimensional subspace. In particular, we show that if K⊆V is the smallest subset with this property, n denotes the dimension of V, and q is the size of the underlying field, then for r bounded and r<n≤rq [superscript r−1], we have |V∖K|=Θ(nq [superscript n-r+1]); this improves the previously known bounds |V∖K|=Ω(q [superscript n−r+1]) and |V∖K|=O(n[superscript 2] q [superscript n−r+1])
Add to ORKG