ELibM Journals • ELibM Home • EMIS Home • EMIS Mirrors

  EMIS Electronic Library of Mathematics (ELibM)
The Open Access Repository of Mathematics
  EMIS ELibM Electronic Journals

JOURNAL OF
ALGEBRAIC
COMBINATORICS
  Editors-in-chief: C. A. Athanasiadis, T. Lam, A. Munemasa, H. Van Maldeghem
ISSN 0925-9899 (print) • ISSN 1572-9192 (electronic)
 

Kakeya-type sets in finite vector spaces

Swastik Kopparty , Vsevolod F. Lev , Shubhangi Saraf and Madhu Sudan

DOI: 10.1007/s10801-011-0274-8

Abstract

For a finite vector space V and a nonnegative integer r\leq dim\thinspace  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\subseteq  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\leq  rq r - 1, we have | V\setminus  K|= Θ ( nq n -  r+1); this improves the previously known bounds | V\setminus  K|= Ω ( q n -  r+1) and | V\setminus  K|= O( n 2 q n -  r+1).

Pages: 337–355

Keywords: keywords Kakeya set; Kakeya problem; polynomial method; finite field

Full Text: PDF

References

1. Alon, N., Spencer, J.H.: The Probabilistic Method, 3rd edn. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, Hoboken (2008). xviii+352 pp.



© 1992–2009 Journal of Algebraic Combinatorics
© 2012 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition