Chen–Chvátal conjecture for finite metric spaces

From papers

Let (V,d)(V,d) be a finite metric space with nn points. For distinct points x,y,zVx,y,z\in V, say that zz lies between xx and yy when

d(x,y)=d(x,z)+d(z,y).d(x,y)=d(x,z)+d(z,y).

For distinct x,yVx,y\in V, define the line generated by xx and yy by

xy={x,y}{zV:d(z,y)=d(z,x)+d(x,y)  d(x,y)=d(x,z)+d(z,y)  d(x,z)=d(x,y)+d(y,z)}.\overline{xy}=\{x,y\}\cup\{z\in V: d(z,y)=d(z,x)+d(x,y)\ \lor\ d(x,y)=d(x,z)+d(z,y)\ \lor\ d(x,z)=d(x,y)+d(y,z)\}.

A metric space has a universal line if its whole point set is a line. Chen–Chvátal conjecture. Every finite metric space of nn points without a universal line determines at least nn distinct lines. The conjecture extends the de Bruijn–Erdős theorem from the Euclidean plane to arbitrary finite metric spaces and remains open in general, although it is known for graphs of diameter three.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Martín Matamala and Luciano Villarroel-Sepúlveda, “Chen-Chvátal Conjecture for Graphs of Diameter 3”, arXiv:2512.12047 (2025).

Additional references

9 papers in this index state this conjecture (2013–2025). The statement above is taken from the most recent of them; the others are arXiv:2511.17156, arXiv:2310.15058, arXiv:1808.08710, arXiv:1803.07154, arXiv:1501.06681, arXiv:1412.8283, arXiv:1402.5627, arXiv:1312.3214.

Solutions 0

No solutions have been posted yet.