Note on a construction of short -radius sequences

详细信息    查看全文

• 作者：Zbigniew Lonc ^{zblonc@mini.pw.edu.pl}
• 关键词：kk-radius sequence ; Difference family
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：340
• 期：3
• 页码：504-507
• 全文大小：373 K
• 卷排序：340

文摘

A sequence over an nn-element alphabet is called a kk-radius sequence if any two distinct elements of the alphabet occur within distance kk of each other somewhere in the sequence. Let fk(n)fk(n) be the shortest length of a kk-radius sequence over an nn-element alphabet. In this note we give a new construction of “short” kk-radius sequences, based on the concept of a difference family. It allows us to prove that for every fixed positive integer kk there are infinitely many values of nn such that fk(n)=1kn2+O(n). This way we improve an earlier result by Blackburn and McKee (2012) who showed that the same formula holds for infinitely many values of nn only when kk satisfies some special conditions.