The Maximal Length of a $k$-Separator Permutation

Abstract

A permutation $\sigma\in S_n$ is a $k$-separator if all of its patterns of length $k$ are distinct. Let $F(k)$ denote the maximal length of a $k$-separator. Hegarty (2013) showed that $k+\left\lfloor\sqrt{2k-1}\right\rfloor-1\leq F(k)\leq k+\left\lfloor\sqrt{2k-3}\right\rfloor$, and conjectured that $F(k)=k+\left\lfloor\sqrt{2k-1}\right\rfloor-1$. This paper will strengthen the upper bound to prove the conjecture for all sufficiently large $k$ (in particular, for all $k\geq 320801$).