Ph.D Thesis | |

Ph.D Student | Zerbib-Gelaki Shira |
---|---|

Subject | Problems in Combinatorial Geometry |

Department | Department of Mathematics |

Supervisors | PROF. Rom Pinchasi |

PROFESSOR EMERITUS Ron Aharoni | |

Full Thesis text |

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 *n *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 13*n*/36. We slightly improve on this result to
(13/36 0.0004)*n *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.