Random induced subgraphs of Cayley graphs induced by transpositions

Details Random induced subgraphs of Cayley graphs induced by transpositions Random induced subgraphs of Cayley graphs induced by transpositions

2009-09-22

arxiv.org/abs/0909.4037v2

Mathematics

Probability

18 pages, 1 figure

Scientific paper

In this paper we study random induced subgraphs of Cayley graphs of the symmetric group induced by an arbitrary minimal generating set of transpositions. A random induced subgraph of this Cayley graph is obtained by selecting permutations with independent probability, $\lambda_n$. Our main result is that for any minimal generating set of transpositions, for probabilities $\lambda_n=\frac{1+\epsilon_n}{n-1}$ where $n^{-{1/3}+\delta}\le \epsilon_n<1$ and $\delta>0$, a random induced subgraph has a.s. a unique largest component of size $\wp(\epsilon_n)\frac{1+\epsilon_n}{n-1}n!$, where $\wp(\epsilon_n)$ is the survival probability of a specific branching process.

Affiliated with

Also associated with

No associations

Rating

Random induced subgraphs of Cayley graphs induced by transpositions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Random induced subgraphs of Cayley graphs induced by transpositions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random induced subgraphs of Cayley graphs induced by transpositions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-301273