Extremal problems in combinatorial geometry and graph theory with algorithmic applications

According to Ramsey's classical theorem, every graph contains a relatively large subgraph which is either complete or empty. This result has many analogues, extensions, and applications in several fields of mathematics. However, Ramsey's theorem had remained unnoticed until Erdos and Szekeres rediscovered it in 1935, and put it in a quantitative form. They applied this result to establish the following beautiful theorem. Every set of n points in the plane in general position contains roughly {dollar}rm{lcub}1over2{rcub}logsb2{dollar} n points in convex position.; In this dissertation, I focus on Ramsey-type problems in combinatorial geometry and related extremal problems. In Chapter 2, I summarize my results in Euclidean Ramsey theory. The fundamental problem is to show that for any coloring of the points of Euclidean d-space with a given number of colors, one can find a monochromatic subconfiguration of some fixed type. In particular, we partially settle several problems of Erdos, Graham, et al.; In Chapter 3, we study some natural extensions of Ramsey's theorem to geometric graphs, i.e., to graphs drawn in the plane with (possibly crossing) straight-line segments. Here we want to find monochromatic subgraphs satisfying certain geometric constraints. Among several other results, we prove two conjectures of Bialostocki and Dierker.; The oldest--still unsolved--question in Euclidean Ramsey theory is the Hadwiger-Nelson problem: what is the chromatic number of the so-called unit distance graph of the plane? In Chapter 4, we concentrate on properties of the unit distance graph, and partially answer some questions of Brass and Erdos.; Recently, Szekely discovered that many of these questions are strongly related to a general lower bound on crossing numbers of graphs, due to Ajtai et al. and Leighton. We improve this lower bound and apply it to establish several properties of the unit distance graph and to deduce the best currently known bounds on the number of incidences between n points and m lines in the plane.