Ph.D Thesis

Ph.D StudentZerbib-Gelaki Shira
SubjectProblems in Combinatorial Geometry
DepartmentDepartment of Mathematics
Supervisors PROF. Rom Pinchasi
Full Thesis textFull thesis text - English Version


This thesis deals with problems in combinatorial geometry. In its first part we study the ration between the covering number and the matching number in families of d-intervals. Ingenious topological methods have been introduced by Tardos and Kaiser to obtain upper bounds on this ratio. We discuss two extensions: that of putting weights on the d-intervals, and that of considering the fractional versions of the two parameters. One of the results requires a weighted version of the famous Turan theorem, on the maximal independent set in a graph. We also introduce a new topological method, used give simpler proofs to the Kaiser-Tardos results.

The second part of the thesis has evolved from a famous problem posed by Erdos in 1946: given a number n, what is the maximal number such that every set of points in the plane determines at least this many distinct distances between its elements. We deal with the special case in which the points in question are in convex position. Erdos conjectured that every n-point set in convex position contains a point that determines at least n/2 distinct distances to the other points in the set. The best known lower bound, due to Dumitrescu, was 13n/36. We slightly improve on this result to (13/36 0.0004)plus a small error term. 

In the third part of this thesis we study certain geometrical parameters of arrange- ments of lines in the plane. The zone of a line is the collection of all faces that the line intersects, and the zone theorem asserts that the complexity of the zone of every line is at most 5.5n. The zone theorem is known to be tight, and it is an open question whether it can be improved on average. We provide a piece of evidence that the answer to this question is positive. To this end we define the notion of a zone of a vertex - the collection of all faces in that the vertex intersects. A consequence of the zone theorem is that every line passes through a vertex with zone complexity at most 7. We show that in every arrangement of lines there must be a vertex with zone complexity at most 5.