Applications of character estimates to statistical problems for symmetric group
This paper studies the probabilistic behaviour of properties of randomly chosen permutations from the symmetric group \(S_n\) (\(n\) a natural number). Let \(\sigma\), \(\pi\) be random permutations from \(S_n\) not both in \(A_n\). Then it is proved that various aspects of elements \(\pi\sigma^i\) behave like independent variables. From this it follows with the probability tending to \(1\) (if \(n\) goes to infinity) that \(\{\pi,\sigma \}\) generates \(S_n\), the Cayley graph of \(\{\sigma,\pi\}\) has diameter \(\leq n^3\log n\) and the directed Cayley graph has almost surely diameter \(\leq n^4\log n\). If \(G\) is a black box group isomorphic to \(A_n\) or \(S_n\) then for every \(k<n^{\frac 1{64}}\) there exists a Las Vegas algorithm giving an effective isomorphism with probability \(1-O(k^{-1})\) which takes \(2\) random elements and \(kn\log n\) multiplications in \(G\). For a given \(\alpha>0\) and \(\tau\in S_n\) which moves at least \(\alpha n\) elements it is proved that if we choose \(\sigma\in S_n\) at random then the number of cycles of \(\sigma\) and \(\tau\sigma\) are nearly independent variables. A precise estimate of their dependency is given.
- On the Diameter of Random Cayley Graphs of the Symmetric Group
- Bounds for the probability of generating the symmetric and alternating groups.
- Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group
- On Random Generation of the Symmetric Group
- scientific article; zbMATH DE number 1047740
- Character theory of symmetric groups, subgroup growth of Fuchsian groups, and random walks.
- Fast constructive recognition of a black box group isomorphic to \(S_n\) or \(A_n\) using Goldbach's conjecture
- Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group
- On some problems of a statistical group-theory. II
- On the diameter of Cayley graphs of the symmetric group
- On the diameter of Eulerian orientations of graphs
- On the Diameter of Random Cayley Graphs of the Symmetric Group
- The probability of generating the symmetric group
- The probability of generating the symmetric group
- Characters of the symmetric groups and correlation functions of point processes
- Gaussian limit for projective characters of large symmetric groups
- Babai's conjecture for high-rank classical groups with random generators
- Application of character estimates to the number of \(\mathrm{T}_2\)-systems of the alternating group
- Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group
- scientific article; zbMATH DE number 1245636 (Why is no real title available?)
- scientific article; zbMATH DE number 1552119 (Why is no real title available?)
- Random generators of the symmetric group: diameter, mixing time and spectral gap.
- Random generation of the special linear group
- Navigating directed Cayley graphs of small diameter: a potent Solovay-Kitaev procedure
- Growth in groups: ideas and perspectives
- On the diameter of the symmetric group: polynomial bounds.
- Mini-workshop: Growth and expansion in groups. Abstracts from the mini-workshop held April 7--12, 2024
This page was built for publication: Applications of character estimates to statistical problems for symmetric group
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2448934)
