Evasive Sets, Covering by Subspaces, and Point-Hyperplane Incidences.

Area of Science:

• Combinatorics
• Finite Fields
• Algebraic Geometry

Background:

• Introduces (k, c)-subspace evasive sets, where k-dimensional affine subspaces intersect the set S in at most c elements.
• Highlights existing bounds on the maximum size of such sets, particularly when c is large, referencing Dvir and Lovett's work.

Purpose of the Study:

• To provide an alternative proof for the lower bound of (k, c)-subspace evasive sets using the random algebraic method.
• To establish sharp upper bounds for (k, c)-evasive sets when the field size d is large, extending prior research.
• To explore consequences in combinatorial geometry, specifically related to covering grids with hyperplanes and point-hyperplane incidences.

Main Methods:

• Employs the random algebraic method for proving bounds on subspace evasive sets.
• Utilizes techniques from combinatorial geometry to analyze grid coverings and point-hyperplane incidences.
• Leverages averaging arguments and algebraic methods to derive upper and lower bounds.

Main Results:

• Presents an alternative proof for the lower bound on the size of (k, c)-subspace evasive sets.
• Establishes new sharp upper bounds for (k, c)-evasive sets in large fields.
• Determines the minimum number of k-dimensional hyperplanes to cover a grid, matching existing upper bounds.
• Improves the lower bound for point-hyperplane incidences under specific graph avoidance conditions.

Conclusions:

• The study offers new insights into the structure and bounds of subspace evasive sets.
• The findings have direct implications for problems in combinatorial geometry, including grid covering and point-hyperplane incidences.
• The use of the random algebraic method provides a powerful alternative for tackling these types of problems.