Skip to main content
1 of 2
lemon314
  • 323
  • 3
  • 9

Permutations with bounded displacement on a circle

I am interested in references to results on permutations $\sigma$ of $\{1,\ldots,n\}$ satisfying $|\sigma(i)-i \text{ mod } n|\leq k$ for some $k$ for all $i$. I don't know if there is a common term for these, so I settled for the "bounded displacement" in the title.

I was only able to find two related topics, but both with the linear order, without the "mod $n$" part. These are the band permutations and probabilistic results about them, concerned with random walks (and relaxing the "all $i$" assumption to just "most $i$"), discussed in this video, and the enumeration problem for permutations with bounded drop (bounding the value of $i-\sigma(i)$ instead) inspired by sorting problems, and solved in this paper. It also seems like such permutations might arise with Schreier graphs, but I was unable to find any references, nor analogues of the previous two on the circle.

I am not primarily concerned with counting these permutations (but will be happy to see that too). Ideally, I would like to see dynamical results about such a permutation of a discrete set, or about quantities invariant or bounded under such permutation acting on $\mathbb{R}^n$, since this is the context we encountered them in.

lemon314
  • 323
  • 3
  • 9