Skip to main content
2 of 2
added 47 characters in body
lemon314
  • 323
  • 3
  • 9

Permutations with bounded displacement on a circle

I am interested in references to results on permutations $\sigma$ of $\{0,\ldots,n-1\}$ satisfying $\text{min}\{ \sigma(i)-i\text{ (mod } n),i-\sigma(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