2003-07: On a Conjecture of Chvatal

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