### DIMACS Theoretical Computer Science Seminar

Title: The Sylvester-Chvatal Theorem

Speaker: **Xiaomin Chen**, Rutgers University

Date: November 3, 2003 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Sylvester conjectured in 1893 and Gallai proved some forty years
later that every finite set S of points in the plane includes two
points such that the line passing through them includes either no
other point of S or all other points of S. There are several ways
of extending the notion of lines from Euclidean spaces to arbitrary
metric spaces. Chvatal presented one of them and conjecture that,
with lines in metric spaces defined in this way, the Sylvester-
Gallai theorem generalizes as follows: in every finite metric space,
there is a line consisting of either two points or all the points
of the space. In this talk we prove the conjecture to be true.
This is part of an on-going joint research with V. Chvatal.