Cayley Graph of permutations

27 Views Asked by At

Let $[p]=\{1,..,p\}$ where $p\in \mathbb{N}$. Let $P(n,r)$ denote the set of all injective functions from $[r]$ to $[n]$ and write a typical element as $\sigma=[\sigma(1),...,\sigma(r)]$ where $1\leq\sigma(i)\leq n$. Then the Hamming distance between two elements of $P(n,r)$ can be defined as the number of points in the domain they disagree on. Construct a graph with vertices being the elements of $P(n,r)$ and edges is between the vertices whose Hamming distance is 1. It is known that when $r=n$, or when we consider the bijective functions(permutations), the graph is a Cayley Graph. I want to know if the result holds for for $r<n$ as well. I was trying to find a regular and transitive action of $S_r\times Z_{\binom{n}{r}}$ but failed.