Extremal Problems For Finite Sets PDF Download

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 $