Benny Sudakov: Evasive sets, covering by subspaces, and point-hyperplane incidences

Description of video

Date: 10/28/22
Speaker :Sudakov Benny

Given positive integers kd and a finite field F, a set SFd 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|dk. In this talk we discuss the construction of evasive sets, matching this bound. The existence of optimal evasive sets has several interesting consequences in combinatorial geometry. Using it we determine the minimum number of k-dimensional linear hyperplanes needed to cover the grid [n]d. This extends the work by Balko, Cibulka, and Valtr, and settles a problem proposed by Brass, Moser, and Pach. Furthermore, we improve the best known lower bound on the maximum number of incidences between points and hyperplanes in dimension d assuming their incidence graph avoids the complete bipartite graph Kt,t for some large constant t=t(d). Joint work with Istvan Tomon.