From distances to graphs and back

Janos Pach
École Polytechnique Fédérale de Lausanne (EPFL)

Organizers: Igor Pak and Greta Panova; Location: MS 7608; Abstract: Take n>2 points in the plane such that the maximum distance between them is 1. At most how many pairs of points can be at unit distance? This question and its generalizations by Erdos and his collaborators have led to a lot of difficult problems in incidence geometry. The present special program at IPAM concentrates on new algebraic techniques that proved to be relevant in this area. The same questions have also motivated a lot of research in extremal graph and hypergraph theory. However, combinatorial and algebraic methods appear to be insufficient in solving many problems concerning graphs defined in geometric terms.

We survey problems and results that fall into this category. A sample question, partially solved by Konrad Swanepoel and myself: Given n points in d-space, what is the maximum number of "double-normal" pairs {p,q} with the property that all points lie between the hyperplanes that pass through p and q and are orthogonal to pq? For d=3, the answer is (1/4+o(1))n^2. We do not have an asymptotically tight solution in 4 dimensions.

Back to Algebraic Techniques for Combinatorial and Computational Geometry