Incidences and extremal problems on finite point sets

This thesis consists of three papers, each addressing a different collection of problems on the extremal combinatorics of finite point sets. The first collection of results is on the number of flats of each dimensions spanned by a set of points in $mathbb{R}^d$. These results generalize a theorem of Beck cite{beck1983lattice} from 1983, and answer a question of Purdy cite{erdos1996extremal} from 1995. We also apply the ideas behind the main results of the chapter to generalize an incidence bound between points and planes proved by Elekes and T'oth cite{elekes2005incidences} to all dimensions. With the exception of the generalization of the Elekes-T'oth incidence bound, all of the material in this chapter has previously appeared as cite{lund2016essential}. The second collection of results is on the set of perpendicular bisectors determined by a set of points in the plane. We show that if $P$ is a set of points in $mathbb{R}^2$ such that no line or circle contains more than a large constant fraction of the points of $P$, the the pairs of points of $P$ determine a substantially superlinear number of distinct perpendicular bisectors. This is the first substantial progress toward a conjecture of the author, Sheffer, and de Zeeuw cite{lund2015bisector} that such a set of points must determine $Omega(n^2)$ distinct perpendicular bisectors. This chapter also includes a new proof of a known result on an old question ErdH{o}s cite{erdos1946sets} on the distances between pairs of points in the plane. This chapter is cite{lund2016refined}. The third collection of results concerns the set of flats spanned by a set of points in $mathbb{F}_q^d$. For a set of points $P$ in $mathbb{F}_q^2$, this result implies that, for any $eps > 0$, if $|P| > (1+eps)q$, then $Omega(q^2)$ lines each contain at least two points of $P$. We obtain a tight generalization of this statement to all dimensions, as well as a more general result for block designs. We use this theorem to improve a result of Iosevich, Rudnev, and Zhai cite{iosevich2012areas} on the distinct areas of triangles determined by points in $mathbb{F}_q^2$. This chapter is joint work with Shubhangi Saraf, and has been published as cite{lund2016incidence}.Ph.D.Includes bibliographical referencesby Benjamin Lun