<p>We prove that in every metric space where no line contains all the points, there are at least <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_137_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="54" /> </InlineMediaObject> <EquationSource Format="TEX">$\Omega (n^{2/3})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mn>2</mn> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> lines. This improves the previous <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_137_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">$\Omega (\sqrt{n})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <msqrt> <mi>n</mi> </msqrt> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> lower bound on the number of lines in general metric space, and also improves the previous <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_137_Article_IEq3.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="54" /> </InlineMediaObject> <EquationSource Format="TEX">$\Omega (n^{4/7})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mn>4</mn> <mo stretchy="false">/</mo> <mn>7</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> lower bound on the number of lines in metric spaces generated by connected graphs.</p>

Improved Lower Bound Towards Chen–Chvátal Conjecture

期刊论文
发表日期：

2025年3月14日

查看全文

Congkai Huang

摘要

We prove that in every metric space where no line contains all the points, there are at least $\Omega (n^{2/3})$ $Ω (n^{2 / 3})$ lines. This improves the previous $\Omega (\sqrt{n})$ $Ω (\sqrt{n})$ lower bound on the number of lines in general metric space, and also improves the previous $\Omega (n^{4/7})$ $Ω (n^{4 / 7})$ lower bound on the number of lines in metric spaces generated by connected graphs.