6
$\begingroup$

I am seeking to understand the properties of a typical pair of permutations $(\sigma,\tau) \in \mathrm{Sym}(n)^2$ chosen uniformly at random from all pairs such that $\sigma$ and $\tau$ commute. In particular, I would like to prove that the following holds.

$(\ast)$ With high probability, the graph on $\{1,\ldots,n\}$ induced by $\sigma$ and $\tau$ has few 'unnecessary' short cycles (i.e. short cycles which do not correspond to commutators).

It seems that the best way to do this would be to have a straightforward algorithm to generate such a random pair. I have been unable to find such an algorithm in the literature and I would appreciate if someone could tell me what is known about this subject.

I would be equally happy to have a way of establishing $(\ast)$ for a random pair of approximately commuting permutations. To make the last statement precise, for each $\epsilon > 0$ I would like to know that if $n$ is large enough then $(\ast)$ holds for a pair chosen uniformly at random from of the set of all pairs $(\sigma,\tau) \in \mathrm{Sym}(n)^2$ such that $\sigma \tau \sigma^{-1} \tau^{-1}$ has at least $(1-\epsilon)n$ fixed points.

$\endgroup$
  • $\begingroup$ If $n$ is not too large, you could just use one of the fast algorithms to generate random permutations described here, and then keep only pairs of permutations that commute; these become rare as $\exp(\sqrt{n}-n\ln n)$ when $n$ is large, so then a direct approach to find them would be needed; it seems like something a Monte Carlo algorithm might be able to achieve... $\endgroup$ – Carlo Beenakker Feb 5 '17 at 8:10
  • $\begingroup$ If I didn't make a mistake, the total number of ordered pairs of commuting permutations on $n$ letters is $p(n)n!$, where $p(n)$ is the number of partitions of $n$. If you could turn this identity into a combinatorial bijection somehow, then you just need to sample an ordered pair of a permutation and a partition and then apply the hypothetical bijection. $\endgroup$ – zeb Feb 5 '17 at 10:05
4
$\begingroup$

Here's a method for sampling two commuting elements of a group $G$, given that you can sample a random element of $G$ and that you can also sample a random conjugacy class of $G$ (and assuming as well that for any two elements $a,x \in G$ which are in the same conjugacy class, you can efficiently compute some $z \in G$ with $zxz^{-1} = a$). It's based on Theorem IV of the paper "On some problems of a statistical group-theory. IV" by Erdős and Turán.

Step 1: Let $C$ be a uniformly random conjugacy class of $G$, and let $x$ be an arbitrary element of $C$.

Step 2: Let $y$ be a uniformly random element of $G$.

Step 3: Let $a = yxy^{-1}$.

Step 4: Compute an element $z \in G$ such that $zxz^{-1} = a$, such that $z$ depends only on $a$ and $x$.

Step 5: Let $b = yz^{-1}$.

Then $ab = ba$ and $(a,b)$ is uniformly distributed among ordered pairs of commuting elements of $G$.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.