Ph.D Thesis

Ph.D StudentPerlstein Amitai
SubjectTopics in Combinatorial Geometry and Combinatorics
DepartmentDepartment of Mathematics
Supervisor PROF. Rom Pinchasi
Full Thesis textFull thesis text - English Version


In this work we present a collection of results in combinatorial geometry aggregated in two chapters. The first one deals with geometric graphs and the second one with problems that rise naturally from the Gallai-Sylvester theorem.

We use known bounds to the number of edges of some geometric graphs in R2 in order to provide tight upper bounds to the number of lenses created in arrangements of finite sets of pair wise intersecting discs (or unit discs) in R2.  

KLV theorem states that the number of edges in geometric graphs in R2 with n vertices and no pair of edges which are opposite edges of a convex quadrilateral is 2n-2. This is also the maximum number of diameters of a set of n points in R3 (Vazsonyi's Conjecture). We bring an analog of the KLV theorem to R3 and use it also to provide a new proof to Vazsonyi's conjecture. The proof is quite different in nature from the previously known proofs.

The Gallai-Sylvester theorem states that in a finite set P of non collinear points in the plane, there exists a line that passes through precisely two points. Such a line is called ordinary. One can ask then how many such lines are there and whether there exists a point of P through which many lines connecting points of P pass.

We introduce Duality and state the equivalent dual problems:

Given a finite set L of lines in the plane, how many ordinary intersection points (of precisely two lines) are there?


Is there necessarily a line that contains many intersection points of L?

Csima and Sawyer provided in 1993 the best (very close to the best possible) lower bound known today to the first question. We introduce our own lower linear bound for a closely related problem that deals with arrangement of pseudo-parabolas rather than arrangement of lines.

Dirac conjectured in 1951 that the answer to the second question is positive and suggested a lower linear bound for the maximum number of intersection points contained in a line of the arrangement. We prove this conjecture to be true when there are not 'too many' ordinary intersection points.

In both of the results presented above, we use Euler's formula that relates the number of vertices, edges and faces of a planar map.