Mixing
Random pairs of commuting permutations
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Let $Omega_n subseteq mathrmSym(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 $mathbbF_r$ be the free group on $r$ generators and let $G = mathbbF_2 times mathbbF_2$. Fixing an indexation for the generators of $G$, each element of $Omega_n$ determines a unique homomorphism from $G$ to $mathrmSym(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 $frac1n|mathrmFix(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 $frac1n|mathrmFix(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 mathrmSym(n))_n=1^infty$ of homomorphisms such that for each $g in G$ the set $mathrmFix(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 $mathbbF_4$ has a positive answer.
co.combinatorics gr.group-theory pr.probability
asked 3 hours ago
burtonpeterj
588213
add a comment |Â
up vote
2
down vote
favorite
Let $Omega_n subseteq mathrmSym(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 $mathbbF_r$ be the free group on $r$ generators and let $G = mathbbF_2 times mathbbF_2$. Fixing an indexation for the generators of $G$, each element of $Omega_n$ determines a unique homomorphism from $G$ to $mathrmSym(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 $frac1n|mathrmFix(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 $frac1n|mathrmFix(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 mathrmSym(n))_n=1^infty$ of homomorphisms such that for each $g in G$ the set $mathrmFix(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 $mathbbF_4$ has a positive answer.
co.combinatorics gr.group-theory pr.probability
asked 3 hours ago
burtonpeterj
588213
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Let $Omega_n subseteq mathrmSym(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 $mathbbF_r$ be the free group on $r$ generators and let $G = mathbbF_2 times mathbbF_2$. Fixing an indexation for the generators of $G$, each element of $Omega_n$ determines a unique homomorphism from $G$ to $mathrmSym(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 $frac1n|mathrmFix(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 $frac1n|mathrmFix(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 mathrmSym(n))_n=1^infty$ of homomorphisms such that for each $g in G$ the set $mathrmFix(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 $mathbbF_4$ has a positive answer.
co.combinatorics gr.group-theory pr.probability
asked 3 hours ago
burtonpeterj
588213
Let $Omega_n subseteq mathrmSym(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 $mathbbF_r$ be the free group on $r$ generators and let $G = mathbbF_2 times mathbbF_2$. Fixing an indexation for the generators of $G$, each element of $Omega_n$ determines a unique homomorphism from $G$ to $mathrmSym(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 $frac1n|mathrmFix(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 $frac1n|mathrmFix(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 mathrmSym(n))_n=1^infty$ of homomorphisms such that for each $g in G$ the set $mathrmFix(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 $mathbbF_4$ has a positive answer.
co.combinatorics gr.group-theory pr.probability
co.combinatorics gr.group-theory pr.probability
asked 3 hours ago
burtonpeterj
588213
asked 3 hours ago
burtonpeterj
588213
asked 3 hours ago
burtonpeterj
588213
asked 3 hours ago
burtonpeterj
588213
asked 3 hours ago
burtonpeterj
588213
588213
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
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 mathrmSym(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 $mathrmSym(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$.
answered 25 mins ago
Jean Raimbault
1,803920
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
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 mathrmSym(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 $mathrmSym(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$.
answered 25 mins ago
Jean Raimbault
1,803920
add a comment |Â
up vote
3
down vote
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 mathrmSym(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 $mathrmSym(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$.
answered 25 mins ago
Jean Raimbault
1,803920
add a comment |Â
up vote
3
down vote
up vote
3
down vote
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 mathrmSym(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 $mathrmSym(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$.
answered 25 mins ago
Jean Raimbault
1,803920
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 mathrmSym(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 $mathrmSym(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$.
answered 25 mins ago
Jean Raimbault
1,803920
answered 25 mins ago
Jean Raimbault
1,803920
answered 25 mins ago
Jean Raimbault
1,803920
answered 25 mins ago
Jean Raimbault
1,803920
1,803920
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f313904%2frandom-pairs-of-commuting-permutations%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password