Extremal problems in combinatorial geometry and Ramsey theory

The work presented in this thesis falls under the broad umbrella of combinatorics of Erd's type. We describe diverse facets of interplay between geometry and combinatorics and consider several questions about existence of structures in various combinatorial settings. We make contributions to specific problems in combinatorial geometry, Ramsey theory and graph theory. We first study extremal questions in geometric graph theory, that is, the existence of collections of edges with a specified crossing pattern in drawings of graphs in the plane with sufficiently many edges. Among other results, we prove that any drawing of a graph on n vertices and Cn edges, where C is a sufficiently large constant, contains each of the following crossing patterns: (1) three pairwise crossing edges, (2) two edges that cross and are crossed by k other edges, (3) an edge crossed by four other edges. In the latter, we show that C = 5.5 is the best possible constant, which, through Szekely's method, gives the best known value for a constant in the well known "Crossing Lemma" due to Ajtai, Chvatal, Leighton, Newborn and Szemeredi. After relaxing graph planarity in several ways, we proceed to study ... the maximum number of edges in a drawing of a graph on n vertices without self-crossing copy of C4, the cycle of four vertices. We prove that ... The importance of this and the above mentioned results comes from numerous applications of "Crossing Lemma" and the bounds on ... in discrete and computational geometry (incidence and Gallai-Sylvester type problems, k-set problems,

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Mathematics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2004

Author dc:creator

• RadoiÄ iÄ , RadoÅ¡, 1978-

Advisor dc:contributor.advisor

• János Pach.

• Mathematics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/32246

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/32246