Packing analogue of k-radius sequences

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

Let k be a positive integer. A sequence s1, s2,.., sm over an n-element A alphabet is a packing k-radius sequence, if for all pairs of indices (i, j), such that 1≤i<j≤m and j-i≤k, the sets {si, sj} are pairwise different 2-element subsets of A. Let gk(n) denote the length of a longest k-radius sequence over A. We give a construction demonstrating that for every k=⌊cnα⌋, where c and α are fixed reals such that c>0 and 0≤α<1/2, gk(n)=n2/2k(1-o(1)). For a constant k we show that gk(n)=n2/2k-O(n1.525). Moreover, we prove an upper bound for gk(n) that allows us to show that gk(n)=n(1+o(1)) for every k=⌊cnα⌋, where c>0 and 1/2<α<1.

Original languageEnglish
Pages (from-to)57-70
Number of pages14
JournalEuropean Journal of Combinatorics
Volume57
DOIs
StatePublished - Oct 1 2016

Bibliographical note

Funding Information:
Zbigniew Lonc acknowledges a support from the Polish National Science Centre , decision no. DEC-2012/05/B/ST1/00652 .

Publisher Copyright:
© 2016 Elsevier Ltd.

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Packing analogue of k-radius sequences'. Together they form a unique fingerprint.

Cite this