Improved lower bound towards Chen-Chvátal conjecture

Congkai Huang

We prove that in every metric space where no line contains all the points, there are at least $\Omega (n^{2/3})$ lines. This improves the previous $\Omega (\sqrt{n})$ lower bound on the number…