Ghent University Academic Bibliography

Advanced

Applications of character estimates to statistical problems for the symmetric group

Jan-Christoph Schlage-Puchta UGent (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:
author
organization
year
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.