Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Evasive sets, covering by subspaces, and point-hyperplane incidences
ETH Zurich, Zurich, Switzerland.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2024 (English)In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 72, p. 1333-1347Article in journal (Refereed) Published
Abstract [en]

Given positive integers k≤ d and a finite field F, a set S⊂ Fd is (k, c)-subspace evasive if every k-dimensional affine subspace contains at most c elements of S. By a simple averaging argument, the maximum size of a (k, c)-subspace evasive set is at most c|F|d-k . When k and d are fixed, and c is sufficiently large, the matching lower bound Ω (|F|d-k) is proved by Dvir and Lovett. We provide an alternative proof of this result using the random algebraic method. We also prove sharp upper bounds on the size of (k, c)-evasive sets in case d is large, extending results of Ben-Aroya and Shinkar. The existence of optimal evasive sets has several interesting consequences in combinatorial geometry. We show that the minimum number of k-dimensional linear hyperplanes needed to cover the grid [n]d⊂ Rd is Ωd(n*d(d-k)/d-1) , which matches the upper bound proved by Balko et al., and settles a problem proposed by Brass et al. Furthermore, we improve the best known lower bound on the maximum number of incidences between points and hyperplanes in Rd assuming their incidence graph avoids the complete bipartite graph Kc,c for some large constant c= c(d) .

Place, publisher, year, edition, pages
Springer, 2024. Vol. 72, p. 1333-1347
Keywords [en]
Codes, Covering problems, Evasive sets
National Category
Computer Sciences Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-215842DOI: 10.1007/s00454-023-00601-1ISI: 001087477400001PubMedID: 39376994Scopus ID: 2-s2.0-85174284680OAI: oai:DiVA.org:umu-215842DiVA, id: diva2:1808170
Available from: 2023-10-30 Created: 2023-10-30 Last updated: 2024-10-24Bibliographically approved

Open Access in DiVA

fulltext(295 kB)34 downloads
File information
File name FULLTEXT02.pdfFile size 295 kBChecksum SHA-512
fd12a8d2a1fa8985a31adc657b648299c8be139b0378bb60608616683ff173f2c3d1073406b1980aa7e0e702b4c5c4920262c58746293c6bcd47aab5db72c829
Type fulltextMimetype application/pdf

Other links

Publisher's full textPubMedScopus

Authority records

Tomon, István

Search in DiVA

By author/editor
Tomon, István
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Discrete & Computational Geometry
Computer SciencesDiscrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 80 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
pubmed
urn-nbn

Altmetric score

doi
pubmed
urn-nbn
Total: 261 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf