Let $\Omega\_n \subseteq \mathrm{Sym}(n)^4$ be the set of all $4$-tuples $(\sigma\_1,\sigma\_2,\tau\_1,\tau\_2)$ of permutations of $\{1,\ldots,n\}$ such that $\sigma\_j \tau\_k = \tau\_k \sigma\_j$ for each pair $(j,k) \in \{1,2\}^2$.


Any four permutations determine a $8$-regular edge-labeled directed graph on $\{1,\ldots,n\}$. (Of course, the graph might not be simple.) I am interested in understanding the local structure of this graph when the four permutations are chosen uniformly at random from $\Omega\_n$. In particular, I would like to know whether the commutativity constraint enforces any other kind of constraint on the structure of the graph, in the sense that a significant number of short cycles other than commutators need to occur.


A more precise formulation of the problem is as follows. Let $\mathbb{F}\_r$ be the free group on $r$ generators and let $G = \mathbb{F}\_2 \times \mathbb{F}\_2$. Fixing an indexation for the generators of $G$, each element of $\Omega\_n$ determines a unique homomorphism from $G$ to $\mathrm{Sym}(n)$. We identify a uniform random element of $\Omega\_n$ with the associated random homomorphism, to be denoted $\phi$. Consider the following questions.


(1) Is it the case that for every nontrivial element $g \in G$ and every $\epsilon > 0$ the probability that $\frac{1}{n}|\mathrm{Fix}(\phi(g))| \leq \epsilon$ tends to $1$ as $n \to \infty$? I emphasize that $g$ and $\epsilon$ are fixed before the limit. 


(2) Is it the case that for every nontrivial element $g \in G$ the expectation of the random variable $\frac{1}{n}|\mathrm{Fix}(\phi(g))|$ tends to $0$ as $n \to \infty$?


Clearly a positive answer to Question (1) implies a positive answer to Question (2). A positive answer to Question (1) is exactly the assertion that the uniform measures on $\Omega\_n$ form a random sofic approximation to $G$. Intuitively, this would mean that a uniform random element of $\Omega\_n$ has no 'unnecessary' structure.


Note that residual finiteness of $G$ implies that there exists a sequence $(\phi\_n:G \to \mathrm{Sym}(n))\_{n=1}^\infty$ of homomorphisms such that for each $g \in G$ the set $\mathrm{Fix}(\phi\_n(g))$ is empty for sufficiently large $n$. 


A final (vague) question is whether this model can be generated in any way other than its definition. The model given by a uniformly chosen $4$-tuple of permutations with no additional constraints is contiguous with a uniform random $8$-regular graph, and there are multiple ways of generating this. In this case the elementary theory shows that the analog of Question (1) with $G$ replaced by $\mathbb{F}\_4$ has a positive answer.



Random pairs of commuting permutations
This is not the case, in fact in both cases the limit is 1/2. This is because with probability going to 1 as $n \to +\infty$ a uniformly random morphism $\mathbb F\_2 \times \mathbb F\_2 \to \mathrm{Sym}(n)$ is trivial on one of the factors. The latter claim follows from Dixon's theorem that a random pair of independently chosen permutations almost surely generates a primitive group, in fact the full alternating or symmetric group so it has a trivial commutant, so for large $n$ a typical representation of $\mathbb F\_2 \times F\_2$ to $\mathrm{Sym}(n)$ has one factor acting with primitive image and the other trivially. 


In terms of graphs this means that the graphs you defined converge to the mean of the Schreier coset graphs of $1 \times \mathbb F\_2$ and $\mathbb F\_2 \times 1$. 


**EDIT** As noted in the comments the above does not contain an actual proof of its statements. To provide such a proof one needs to look onto Dixon's arguments a bit. The reference for Dixon's paper, which I will use below, is : *The Probability of Generating the Symmetric Group*, Math. Zeitschrift 110 (1969). 


The first claim is that there are at most $(n!)^2(1 + O(C^{-n}))$ representations of $\mathbb F\_2\times \mathbb F\_2$ such that the first factor acts transitively. To prove this note that if it acts primitively then the image of the second factor has to act trivially. On the other hand even if it acts nonprimitively (but still transitively) its centraliser in $\mathrm{Sym}(n)$ is of cardinality at most $n$ (see eg. Lemma A.2 in <https://arxiv.org/pdf/1805.03893.pdf>). In the proof of his Lemma 2 Dixon shows that the number of such imprimitive representations is at most $n2^{-n/4}(n!)^2$. So we get in fine that the number of representations of $\mathbb F\_2 \times \mathbb F\_2$ where $\mathbb F\_2 \times 1$ acts transitively is at most equal to  

$$
(1 + n^3 2^{-n/4})(n!)^2
$$
which is what we wanted. 


The second claim is that the number of representations where $\mathbb F\_2 \times \mathbb F\_2$ acts transitively, but not $\mathbb F\_2 \times 1$ is $O(C^{-n}(n!)^2)$. This is in fact simpler : the number of such representations where the orbits of the first factor are of size $2 \le d \le n/2$ is at most equal to 
$$
\frac{n!}{(n/d)!(d!)^{n/d}} \cdot (d!)^{2n/d} \cdot \left((n/d)!\right)^2 \cdot d^{n/d} = n!\cdot (d!)^{n/d} \cdot (n/d)! \cdot d^{n/d}
$$
and by Stirling's approximation this is $O((n!)^{3/2}C^n)$. 


It remains to check that nontransitive representations of $\mathbb F\_2 \times \mathbb F\_2$ are also rare. I'm going to give a formula which should be estimable by elementary means but leave the estimate for now. Using the two facts proven above we can estimate the number of such representations by:
$$
\sum\_\pi \frac{n!}{\prod\_{1\le i \le n} \pi\_i! (i!)^{\pi\_i}} \prod\_{1\le i\le n} \left(1 + O(C^{-i})\right) (i!)^{2\pi\_i} \\= (n!)^2 \sum\_\pi \prod\_{1\le i \le n}\frac{1 + O(C^{-i})}{\pi\_i!} \cdot\frac{\prod\_{1\le i\le n} (i!)^{\pi\_i}}{n!}
$$
where the sum goes over all partitions of $n$ ($\pi = (\pi\_1, \ldots, \pi\_n$ with $\sum\_i i\pi\_i = n$) with $\pi\_1 = \pi\_n = 0$ (these correspond to actions where the first factor acts trivially or transitively). I think in the form on the second line it should be possible to evaluate the sum to prove that it is $o(1)$. 


