Text

theses

ETD_7964

Ph.D.

Includes bibliographical references

This dissertation explores problems in combinatorial geometry relating to incidences and to applications of incidence problems in other areas of combinatorics. In recent years, various tools from algebra have been applied to make significant progress on longstanding combinatorial geometric problems. These breakthroughs have stimulated work in developing additional algebraic tools and applying them to other problems. We study two different flavors of incidence problems using algebraic techniques.
• Given a set of points P and a set of objects V, an incidence is defined to be a point-object pair (p, v) ∈ P × V such that p ∈ v, i.e., the point is contained in the object. In Chapter 2, we introduce a new notion of degeneracy and give bounds on the maximum number of point-plane and point-sphere incidences in R 3 that are non-degenerate under this notion.
• Given a set of points P, an ordinary line is defined to be a line incident to exactly two points. In 1893, Sylvester posed the following question: “Prove that it is not possible to arrange any finite number of real points so that a right line through every two of them shall pass through a third, unless they all lie in the same right line.” In other words, Sylvester asked if every finite point set in R 2 , not all on a ii line, determines an ordinary line. The question was resolved in the affirmative by Gallai in 1944 and many others subsequently. For point sets in complex space, Kelly’s theorem states that point sets in C 3 , not all on a plane, must determine an ordinary line. In Chapter 3, we give bounds on the minimum number of ordinary lines determined by sets of points in C 3 .
Lastly, we give some applications of incidence bounds to other combinatorial problems. We study the k-most-frequent distances problem in R 3 . This generalizes the unit distance problem of Erdos, which asks for the maximum number of times a distance can be realized among the n 2 pairs of n given points. In the k-most-frequent distances problem, we give a bound on the number of times a set of k distances can be realized by a set of n points in R 3 . Next, we consider the sum product conjecture, first stated by Erdos and Szemeredi in 1983. Informally, the conjecture states that a finite subset of the reals can not have both additive and multiplicative structure at the same time. We give new bounds for a more general version of this problem which considers subsets of complex numbers.

by Abdul Basit

doi:10.7282/T3QJ7M8T

ETD doctoral

The author owns the copyright to this work.