文章基本信息

标题：Almost Sharp Bounds on the Number of Discrete Chains in the Plane
本地全文：下载
作者：N{'o}ra Frankl ; Andrey Kupavskii
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：164
页码：48:1-48:15
DOI：10.4230/LIPIcs.SoCG.2020.48
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The following generalisation of the ErdÅ's unit distance problem was recently suggested by Palsson, Senger and Sheffer. For a sequence Î´=(Î´â,,â¦ ,Î´_k) of k distances, a (k+1)-tuple (pâ,,â¦ ,p_{k+1}) of distinct points in â"^d is called a (k,Î´)-chain if â-p_j-p_{j+1}â- = Î´_j for every 1 â¤ j â¤ k. What is the maximum number C_k^d(n) of (k,Î´)-chains in a set of n points in â"^d, where the maximum is taken over all Î´? Improving the results of Palsson, Senger and Sheffer, we essentially determine this maximum for all k in the planar case. It is only for k â¡ 1 (mod 3) that the answer depends on the maximum number of unit distances in a set of n points. We also obtain almost sharp results for even k in dimension 3.
关键词：unit distance problem; unit distance graphs; discrete chains