Home
Resource
Incidences and extremal problems on finite point sets
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(558.69 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Lund, Benjamin. Incidences and extremal problems on finite point sets. Retrieved from https://doi.org/doi:10.7282/T3R78J3B

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleIncidences and extremal problems on finite point sets
NameLund, Benjamin (author); Saraf, Shubhangi (chair); Rutgers University; Graduate School - New Brunswick
Date Created2017
Other Date2017-05 (degree)
SubjectComputer Science, Discrete geometry
Extent1 online resource (vii, 93 p. : ill.)
DescriptionThis 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}.
NotePh.D.
NoteIncludes bibliographical references
Noteby Benjamin Lund
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T3R78J3B
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024