On k-neighbor separated permutations

Kovács, István and Soltész, Dániel (2019) On k-neighbor separated permutations. SIAM JOURNAL ON DISCRETE MATHEMATICS, 33 (3). pp. 1691-1711. ISSN 0895-4801 (print); 1095-7146 (online)

Preview

Text 1711.pdf Available under License Creative Commons Attribution. Download (264kB) | Preview

Abstract

Two permutations of [n]={1,2…n} are \textit{k-neighbor separated} if there are two elements that are neighbors in one of the permutations and that are separated by exactly k−2 other elements in the other permutation. Let the maximal number of pairwise k-neighbor separated permutations of [n] be denoted by P(n,k). In a previous paper, the authors have determined P(n,3) for every n, answering a question of Körner, Messuti and Simonyi affirmatively. In this paper we prove that for every fixed positive integer ℓ, P(n,2ℓ+1)=2n−o(n). We conjecture that for every fixed even k, P(n,k)=2n−o(n). We also show that this conjecture is asymptotically true in the following sense limk→∞limn→∞P(n,k)−−−−−−√n=2. Finally, we show that for even n, P(n,n)=3n/2.

Actions (login required)

Edit Item