Geodesic
The maximal length of a \(k\)-separator permutation
Benjamin Gunby1
1Massachusetts Institute of Technology, Undergraduate
The electronic journal of combinatorics, Tome 21 (2014) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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$).
DOI : 10.37236/3765
Classification : 05A05, 05A20
Mots-clés : permutations, pattern containment

Benjamin Gunby  1

1 Massachusetts Institute of Technology, Undergraduate 
@article{10_37236_3765,
     author = {Benjamin Gunby},
     title = {The maximal length of a \(k\)-separator permutation},
     journal = {The electronic journal of combinatorics},
     year = {2014},
     volume = {21},
     number = {3},
     doi = {10.37236/3765},
     zbl = {1300.05013},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3765/}
}
TY  - JOUR
AU  - Benjamin Gunby
TI  - The maximal length of a \(k\)-separator permutation
JO  - The electronic journal of combinatorics
PY  - 2014
VL  - 21
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3765/
DO  - 10.37236/3765
ID  - 10_37236_3765
ER  - 
%0 Journal Article
%A Benjamin Gunby
%T The maximal length of a \(k\)-separator permutation
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/3765/
%R 10.37236/3765
%F 10_37236_3765
Benjamin Gunby. The maximal length of a \(k\)-separator permutation. The electronic journal of combinatorics, Tome 21 (2014) no. 3. doi: 10.37236/3765

Cité par Sources :