## DIMACS TR: 2003-07

## On a Conjecture of Chvatal

### Authors: Xiaomin Chen

**
ABSTRACT
**

The Sylvester-Gallai theorem asserts that every finite
set $S$ of points in two-dimensional Euclidean space includes two
points, $a$ and $b$, such that either there is no other point in $S$
is on the line $ab$, or the line $ab$ contains all the points in $S$.
Recently, V. Chv\'{a}tal extended the notion of lines to arbitrary
metric spaces and made a conjecture that generalizes the
Sylvester-Gallai theorem. We prove this conjecture for subspaces of
$\ell_1^2$, the two-dimensional space with the $\ell_1$-metric.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-07.ps.gz

DIMACS Home Page