TransWikia.com

Permutations with bounded displacement on a circle

MathOverflow Asked by lemon314 on November 3, 2021

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP