Séminaire

Pas de possibilité de visio-conférence A celebrated Theorem of de Bruijn and Erd®s [3] states that every noncol-linear set of n points in the plane determines at least n distinct lines. Line uv in the plane consists of all points p such that – dist(p, u) + dist(u, v) = dist(p, v) or – dist(u, p) + dist(p, v) = dist(u, v) or – dist(u, v) + dist(v, p) = dist(u, p). With this definition of line uv in an arbitrary metric space (V, dist), Chen and Chvatal [2] conjectured that every metric space on n points, where n is at least 2, has at least n distinct lines or a line that consists of all n points. Although the conjecture has been proved in several special cases, it is still wide open. I’ll discuss this definition of lines in metric space, then I’ll survey the results supporting this conjecture and some variations of it and I’ll present in more details some of the most recent results [1] : We prove that in any metric space with n points, either there is a line containing all the points, or else there are at least pn/2 distinct lines. This is the first polynomial lower bound on the number of lines in a general metric space, and also improves the previous (n2/7) lower bound on the number of lines in metric spaces induced by connected graphs. We also prove that the number of lines in a metric space is at least n/5w, where w is the number of different distances in the metric space. Références [1] P. Aboulker, X. Chen, G. Huzhang, R. Kapadia and C.Supko, Lines in metric spaces. Manuscript. [2] X. Chen and V. Chvatal, Problems related to a de Bruijn - Erd®s theorem, Discrete Applied Mathematics 156 (2008), 2101 – 2108. [3] N. G. De Bruijn, P. Erd®s, On a combinatorial problem, Indagationes Mathematicae 10 (1948), 421 – 423.