ترغب بنشر مسار تعليمي؟ اضغط هنا

Lines, betweenness and metric spaces

129   0   0.0 ( 0 )
 نشر من قبل Xiaomin Chen
 تاريخ النشر 2014
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

A classic theorem of Euclidean geometry asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chvatal conjectured that this holds for an arbitrary finite metric space, with a certain natural definition of lines in a metric space. We prove that in any metric space with $n$ points, either there is a line containing all the points or there are at least $Omega(sqrt{n})$ lines. This is the first polynomial lower bound on the number of lines in general finite metric spaces. In the more general setting of pseudometric betweenness, we prove a corresponding bound of $Omega(n^{2/5})$ lines. When the metric space is induced by a connected graph, we prove that either there is a line containing all the points or there are $Omega(n^{4/7})$ lines, improving the previous $Omega(n^{2/7})$ bound. We also prove that the number of lines in an $n$-point metric space is at least $n / 5w$, where $w$ is the number of different distances in the space, and we give an $Omega(n^{4/3})$ lower bound on the number of lines in metric spaces induced by graphs with constant diameter, as well as spaces where all the positive distances are from {1, 2, 3}.



قيم البحث

اقرأ أيضاً

The line generated by two distinct points, $x$ and $y$, in a finite metric space $M=(V,d)$, denoted by $overline{xy}^M$, is the set of points given by $$overline{xy}^M:={zin V: d(x,y)=|d(x,z)pm d(z,y)|}.$$ A 2-set ${x,y}$ such that $overline{xy}^M=V$ is called a universal pair and its associated line a universal line. Chen and Chvatal conjectured that in any finite metric space either there is a universal line or there are at least $|V|$ different (non-universal) lines. Chvatal proved that this is indeed the case when the metric space has distances in the set ${0,1,2}$. Aboulker et al. proposed the following strengthening for Chen and Chvatal conjecture in the context of metric spaces induced by finite graphs. The number of lines plus the number of universal pairs is at least the number of point of the space. In this work we first prove that metric spaces with distances in the set ${0,1,2}$ satisfy this stronger conjecture. We also prove that for metric spaces induced by bipartite graphs the number of lines plus the number of bridges of the graph is at least the number its vertices, unless the graph is $C_4$ or $K_{2,3}$.
We relate the existence of many infinite geodesics on Alexandrov spaces to a statement about the average growth of volumes of balls. We deduce that the geodesic flow exists and preserves the Liouville measure in several important cases. The developed analytic tool has close ties to integral geometry.
We characterize the topological configurations of points and lines that may arise when placing n points on a circle and drawing the n perpendicular bisectors of the sides of the corresponding convex cyclic n-gon. We also provide exact and asymptotic formulas describing a random realizable configuration, obtained either by sampling the points uniformly at random on the circle or by sampling a realizable configuration uniformly at random.
We prove a compactness result for bounded sequences $(u_j)_j$ of functions with bounded variation in metric spaces $(X,d_j)$ where the space $X$ is fixed but the metric may vary with $j$. We also provide an application to Carnot-Caratheodory spaces.
We describe the behavior of p-harmonic Greens functions near a singularity in metric measure spaces equipped with a doubling measure and supporting a Poincare inequality.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا