### Applications of character estimates to statistical problems for the symmetric group

(2012) COMBINATORICA. 32(3). p.309-323- abstract
- Let g,h in S_n be chosen at random. Using character estimates we show that in various aspects the elements gh^i behave like independent random variables. As application we show that almost surely the Cayley graph determined by g and h has diameter O(n^3 log n), and the directed Cayley graph has almost surely diameter O(n^4 log n). Further we desribe an algorithm for the black-box-recognition of the symmetric group, and show that for each element g moving a positive proportion of all points, the number of cycles of a random element h and of gh are nearly independent.

Please use this url to cite or link to this publication:
http://hdl.handle.net/1854/LU-1989495

- author
- Jan-Christoph Schlage-Puchta UGent
- organization
- year
- 2012
- type
- journalArticle (original)
- publication status
- published
- subject
- keyword
- random generation, Representation theory, Statistical group theory, Cayley graph, PROBABILITY, Symmetric group
- journal title
- COMBINATORICA
- Combinatorica
- volume
- 32
- issue
- 3
- pages
- 309 - 323
- Web of Science type
- Article
- Web of Science id
- 000308285700004
- JCR category
- MATHEMATICS
- JCR impact factor
- 0.56 (2012)
- JCR rank
- 147/296 (2012)
- JCR quartile
- 2 (2012)
- ISSN
- 0209-9683
- DOI
- 10.1007/s00493-012-2502-9
- language
- English
- UGent publication?
- yes
- classification
- A1
- copyright statement
*I have transferred the copyright for this publication to the publisher*- id
- 1989495
- handle
- http://hdl.handle.net/1854/LU-1989495
- date created
- 2012-01-17 12:34:36
- date last changed
- 2014-11-07 09:16:14

@article{1989495, abstract = {Let g,h in S\_n be chosen at random. Using character estimates we show that in various aspects the elements gh\^{ }i behave like independent random variables. As application we show that almost surely the Cayley graph determined by g and h has diameter O(n\^{ }3 log n), and the directed Cayley graph has almost surely diameter O(n\^{ }4 log n). Further we desribe an algorithm for the black-box-recognition of the symmetric group, and show that for each element g moving a positive proportion of all points, the number of cycles of a random element h and of gh are nearly independent.}, author = {Schlage-Puchta, Jan-Christoph}, issn = {0209-9683}, journal = {COMBINATORICA}, keyword = {random generation,Representation theory,Statistical group theory,Cayley graph,PROBABILITY,Symmetric group}, language = {eng}, number = {3}, pages = {309--323}, title = {Applications of character estimates to statistical problems for the symmetric group}, url = {http://dx.doi.org/10.1007/s00493-012-2502-9}, volume = {32}, year = {2012}, }

- Chicago
- Schlage-Puchta, Jan-Christoph. 2012. “Applications of Character Estimates to Statistical Problems for the Symmetric Group.”
*Combinatorica*32 (3): 309–323. - APA
- Schlage-Puchta, J.-C. (2012). Applications of character estimates to statistical problems for the symmetric group.
*COMBINATORICA*,*32*(3), 309–323. - Vancouver
- 1.Schlage-Puchta J-C. Applications of character estimates to statistical problems for the symmetric group. COMBINATORICA. 2012;32(3):309–23.
- MLA
- Schlage-Puchta, Jan-Christoph. “Applications of Character Estimates to Statistical Problems for the Symmetric Group.”
*COMBINATORICA*32.3 (2012): 309–323. Print.