Abstract
We prove an upper bound for characters of the symmetric groups. In particular, we show that there exists a constant $a>0$ with a property that for every Young diagram $\lambda$ with $n$ boxes, $r(\lambda)$ rows and $c(\lambda)$ columns $$ \left| \frac{\mathrm{Tr}\, \rho^{\lambda}(\pi)}{\mathrm{Tr}\, \rho^{\lambda}(e)} \right| \leq \left[a \max\left(\frac{r(\lambda)}{n},\frac{c(\lambda)}{n},\frac{|\pi|}{n} \right)\right]^{|\pi|}, $$ where $|\pi|$ is the minimal number of factors needed to write $\pi\in S_n$ as a product of transpositions. We also give uniform estimates for the error term in the Vershik-Kerov’s and Biane’s character formulas and give a new formula for free cumulants of the transition measure.
-
[Biane1997]
P. Biane, "Some properties of crossings and partitions," Discrete Math., vol. 175, iss. 1-3, pp. 41-53, 1997.
@article {Biane1997, MRKEY = {1475837},
AUTHOR = {Biane, Philippe},
TITLE = {Some properties of crossings and partitions},
JOURNAL = {Discrete Math.},
FJOURNAL = {Discrete Mathematics},
VOLUME = {175},
YEAR = {1997},
NUMBER = {1-3},
PAGES = {41--53},
ISSN = {0012-365X},
CODEN = {DSMHA4},
MRCLASS = {05A18 (05C25 06A07)},
MRNUMBER = {1475837},
MRREVIEWER = {Konrad Engel},
DOI = {10.1016/S0012-365X(96)00139-2},
ZBLNUMBER = {0892.05006},
} -
[Biane1998]
P. Biane, "Representations of symmetric groups and free probability," Adv. Math., vol. 138, iss. 1, pp. 126-181, 1998.
@article {Biane1998, MRKEY = {1644993},
AUTHOR = {Biane, Philippe},
TITLE = {Representations of symmetric groups and free probability},
JOURNAL = {Adv. Math.},
FJOURNAL = {Advances in Mathematics},
VOLUME = {138},
YEAR = {1998},
NUMBER = {1},
PAGES = {126--181},
ISSN = {0001-8708},
CODEN = {ADMTA4},
MRCLASS = {05E10 (20C30 46L54)},
MRNUMBER = {1644993},
MRREVIEWER = {Dimitri Y. Shlyakhtenko},
DOI = {10.1006/aima.1998.1745},
ZBLNUMBER = {0927.20008},
} -
[Biane2003]
P. Biane, "Characters of symmetric groups and free cumulants," in Asymptotic Combinatorics with Applications to Mathematical Physics, New York: Springer-Verlag, 2003, vol. 1815, pp. 185-200.
@incollection {Biane2003, MRKEY = {2009840},
AUTHOR = {Biane, Philippe},
TITLE = {Characters of symmetric groups and free cumulants},
BOOKTITLE = {Asymptotic Combinatorics with Applications to Mathematical Physics},
VENUE={{S}t. {P}etersburg, 2001},
SERIES = {Lecture Notes in Math.},
VOLUME = {1815},
PAGES = {185--200},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
YEAR = {2003},
MRCLASS = {20C30 (05E10 46L54)},
MRNUMBER = {2009840},
MRREVIEWER = {Burkhard K{ü}lshammer},
DOI = {10.1007/3-540-44890-X_8},
ZBLNUMBER = {1035.05098},
} -
[Dolega2010]
M. Dolega, V. Féray, and P. Śniady, "Explicit combinatorial interpretation of Kerov character polynomials as numbers of permutation factorizations," Adv. Math., vol. 225, pp. 81-120, 2010.
@article{Dolega2010,
author={Dolega, M. and Féray, V. and {\'S}niady, P.},
TITLE={Explicit combinatorial interpretation of {K}erov character polynomials as numbers of permutation factorizations},
JOURNAL={Adv. Math.},
VOLUME={225},
YEAR={2010},
PAGES={81--120},
DOI={10.1016/j.aim.2010.02.011},
} -
[Feray2010]
V. Féray, "Stanley’s formula for characters of the symmetric group," Ann. Comb., vol. 13, pp. 453-461, 2010.
@article{Feray2010,
author={F{é}ray, V.},
TITLE={{S}tanley's formula for characters of the symmetric group},
JOURNAL={Ann. Comb.},
VOLUME={13},
YEAR={2010},
PAGES={453--461},
MRNUMBER = {2581097},
DOI = {10.1007/S00026-009-0038-5},
} -
[GouldenJackson1992]
I. P. Goulden and D. M. Jackson, "The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group," European J. Combin., vol. 13, iss. 5, pp. 357-365, 1992.
@article {GouldenJackson1992, MRKEY = {1181077},
AUTHOR = {Goulden, I. P. and Jackson, D. M.},
TITLE = {The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group},
JOURNAL = {European J. Combin.},
FJOURNAL = {European Journal of Combinatorics},
VOLUME = {13},
YEAR = {1992},
NUMBER = {5},
PAGES = {357--365},
ISSN = {0195-6698},
MRCLASS = {05E15 (05C25 20B30)},
MRNUMBER = {1181077},
MRREVIEWER = {Andrea Brini},
ZBLNUMBER = {0804.05023},
DOI = {10.1016/S0195-6698(05)80015-0},
} -
[Kerov1993] S. Kerov, "The asymptotics of interlacing sequences and the growth of continual Young diagrams," Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), vol. 205, iss. 13, pp. 21-29, 179, 1993.
@article {Kerov1993, MRKEY = {1255301},
AUTHOR = {Kerov, S.},
TITLE = {The asymptotics of interlacing sequences and the growth of continual {Y}oung diagrams},
JOURNAL = {Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. {\rm (POMI)}},
FJOURNAL = {Rossiĭskaya Akademiya Nauk. Sankt-Peterburgskoe Otdelenie. MatematicheskiĭInstitut im. V. A. Steklova. Zapiski Nauchnykh Seminarov (POMI)},
VOLUME = {205},
YEAR = {1993},
NUMBER = {13},
PAGES = {21--29, 179},
ISSN = {0373-2703},
MRCLASS = {05E10 (60B99 60C05)},
MRNUMBER = {1255301},
ZBLNUMBER = {0804.33018},
} -
[Kerov1999] S. Kerov, "A differential model for the growth of Young diagrams," in Proc. St. Petersburg Math. Soc., Vol. IV, Providence, RI: Amer. Math. Soc., 1999, vol. 188, pp. 111-130.
@incollection{Kerov1999,
author={Kerov, S.},
TITLE = {A differential model for the growth of {Y}oung diagrams},
BOOKTITLE={Proc. St. Petersburg Math. Soc., Vol. {\rm IV}},
SERIES={Amer. Math. Soc. Transl. Ser. 2},
VOLUME={188},
PUBLISHER={Amer. Math. Soc.},
ADDRESS={Providence, RI},
YEAR={1999},
PAGES={111--130},
MRNUMBER={1732430},
ZBLNUMBER = {0929.05090},
} -
[MooreRussellSniady]
C. Moore, A. Russell, and P. Śniady, "On the impossibility of a quantum sieve algorithm for graph isomorphism," in STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, New York: ACM, 2007, pp. 536-545.
@incollection {MooreRussellSniady, MRKEY = {2402479},
AUTHOR = {Moore, Cristopher and Russell, Alexander and {\'S}niady, Piotr},
TITLE = {On the impossibility of a quantum sieve algorithm for graph isomorphism},
BOOKTITLE = {{\rm S{TOC}'07}---{P}roceedings of the 39th {A}nnual {\rm ACM} {S}ymposium on {T}heory of {C}omputing},
PAGES = {536--545},
PUBLISHER = {ACM},
ADDRESS = {New York},
YEAR = {2007},
MRCLASS = {81P68 (05C60 05C85 68Q05)},
MRNUMBER = {2402479},
DOI = {10.1145/1250790.1250868},
ZBLNUMBER = {05485489},
} -
[RattanSniady2008]
A. Rattan and P. Śniady, "Upper bound on the characters of the symmetric groups for balanced Young diagrams and a generalized Frobenius formula," Adv. Math., vol. 218, iss. 3, pp. 673-695, 2008.
@article {RattanSniady2008, MRKEY = {2414318},
AUTHOR = {Rattan, Amarpreet and {\'S}niady, Piotr},
TITLE = {Upper bound on the characters of the symmetric groups for balanced {Y}oung diagrams and a generalized {F}robenius formula},
JOURNAL = {Adv. Math.},
FJOURNAL = {Advances in Mathematics},
VOLUME = {218},
YEAR = {2008},
NUMBER = {3},
PAGES = {673--695},
ISSN = {0001-8708},
CODEN = {ADMTA4},
MRCLASS = {20C30 (05E10)},
MRNUMBER = {2414318},
MRREVIEWER = {Mark J. Wildon},
DOI = {10.1016/j.aim.2008.01.008},
ZBLNUMBER = {1155.20011},
} -
[Roichman1996]
Y. Roichman, "Upper bound on the characters of the symmetric groups," Invent. Math., vol. 125, iss. 3, pp. 451-485, 1996.
@article {Roichman1996, MRKEY = {1400314},
AUTHOR = {Roichman, Yuval},
TITLE = {Upper bound on the characters of the symmetric groups},
JOURNAL = {Invent. Math.},
FJOURNAL = {Inventiones Mathematicae},
VOLUME = {125},
YEAR = {1996},
NUMBER = {3},
PAGES = {451--485},
ISSN = {0020-9910},
CODEN = {INVMBH},
MRCLASS = {20C30},
MRNUMBER = {1400314},
MRREVIEWER = {David Gluck},
DOI = {10.1007/s002220050083},
ZBLNUMBER = {0854.20015},
} -
[SinaiSoshnikov1998]
Y. G. Sinai and A. B. Soshnikov, "A refinement of Wigner’s semicircle law in a neighborhood of the spectrum edge for random symmetric matrices," Funktsional. Anal. i Prilozhen., vol. 32, iss. 2, pp. 56-79, 96, 1998.
@article {SinaiSoshnikov1998, MRKEY = {1647832},
AUTHOR = {Sinai, Ya. G. and Soshnikov, A. B.},
TITLE = {A refinement of {W}igner's semicircle law in a neighborhood of the spectrum edge for random symmetric matrices},
JOURNAL = {Funktsional. Anal. i Prilozhen.},
FJOURNAL = {Rossiĭskaya Akademiya Nauk. Funktsional\cprime nyĭAnaliz i ego Prilozheniya},
VOLUME = {32},
YEAR = {1998},
NUMBER = {2},
PAGES = {56--79, 96},
ISSN = {0374-1990},
MRCLASS = {82B41 (15A52 60F99)},
MRNUMBER = {1647832},
MRREVIEWER = {Boris A. Khoruzhenko},
DOI = {10.1007/BF02482597},
ZBLNUMBER = {0930.15025},
} -
[Speicher1998] R. Speicher, "Combinatorial theory of the free product with amalgamation and operator-valued free probability theory," Mem. Amer. Math. Soc., vol. 132, iss. 627, p. x, 1998.
@article {Speicher1998, MRKEY = {1407898},
AUTHOR = {Speicher, Roland},
TITLE = {Combinatorial theory of the free product with amalgamation and operator-valued free probability theory},
JOURNAL = {Mem. Amer. Math. Soc.},
FJOURNAL = {Memoirs of the American Mathematical Society},
VOLUME = {132},
YEAR = {1998},
NUMBER = {627},
PAGES = {x+88},
ISSN = {0065-9266},
CODEN = {MAMCAU},
MRCLASS = {46L50 (81S25)},
MRNUMBER = {1407898},
MRREVIEWER = {Hari Bercovici},
ZBLNUMBER = {0935.46056},
} -
[Stanley2003/04] R. P. Stanley, "Irreducible symmetric group characters of rectangular shape," Sém. Lothar. Combin., vol. 50, p. 11, 2003/04.
@article {Stanley2003/04, MRKEY = {2049555},
AUTHOR = {Stanley, Richard P.},
TITLE = {Irreducible symmetric group characters of rectangular shape},
JOURNAL = {Sém. Lothar. Combin.},
FJOURNAL = {Séminaire Lotharingien de Combinatoire},
VOLUME = {50},
YEAR = {2003/04},
PAGES = {11},
ISSN = {1286-4889},
MRCLASS = {20C30 (05E10)},
MRNUMBER = {2049555},
MRREVIEWER = {Christine Bessenrodt},
ZBLNUMBER= {1068.20017},
} -
[Stanley-preprint] R. P. Stanley, A conjectured combinatorial interpretation of the normalized irreducible character values of the symmetric group, 2006.
@misc{Stanley-preprint,
author={Stanley, Richard P.},
TITLE = {A conjectured combinatorial interpretation of the normalized irreducible character values of the symmetric group},
NOTE={preprint},
YEAR={2006},
ARXIV={math.CO/0606467},
} -
[VershikKerov1981] A. M. Vershik and S. V. Kerov, "Characters and factor representations of the infinite symmetric group," Dokl. Akad. Nauk SSSR, vol. 257, iss. 5, pp. 1037-1040, 1981.
@article {VershikKerov1981, MRKEY = {0614033},
AUTHOR = {Vershik, A. M. and Kerov, S. V.},
TITLE = {Characters and factor representations of the infinite symmetric group},
JOURNAL = {Dokl. Akad. Nauk SSSR},
FJOURNAL = {Doklady Akademii Nauk SSSR},
VOLUME = {257},
YEAR = {1981},
NUMBER = {5},
PAGES = {1037--1040},
ISSN = {0002-3264},
MRCLASS = {20C32},
MRNUMBER = {0614033},
ZBLNUMBER = {0534.20008},
} -
[VoiculescuDykemaNica1992] D. V. Voiculescu, K. J. Dykema, and A. Nica, Free Random Variables, Providence, RI: Amer. Math. Soc., 1992, vol. 1.
@book {VoiculescuDykemaNica1992, MRKEY = {1217253},
AUTHOR = {Voiculescu, D. V. and Dykema, K. J. and Nica, A.},
TITLE = {Free Random Variables},
SERIES = {{\rm CRM} Monogr. Series},
VOLUME = {1},
NOTE = {A noncommutative probability approach to free products with applications to random matrices, operator algebras and harmonic analysis on free groups},
PUBLISHER = {Amer. Math. Soc.},
ADDRESS = {Providence, RI},
YEAR = {1992},
PAGES = {vi+70},
ISBN = {0-8218-6999-X},
MRCLASS = {46L50 (46L10 47B80 60H99)},
MRNUMBER = {1217253},
MRREVIEWER = {Roland Speicher},
ZBLNUMBER = {0795.46049},
} -
[Zvonkin1997]
A. Zvonkin, "Matrix integrals and map enumeration: an accessible introduction," Math. Comput. Modelling, vol. 26, iss. 8-10, pp. 281-304, 1997.
@article {Zvonkin1997, MRKEY = {1492512},
AUTHOR = {Zvonkin, A.},
TITLE = {Matrix integrals and map enumeration: an accessible introduction},
NOTE = {Combinatorics and physics (Marseilles, 1995)},
JOURNAL = {Math. Comput. Modelling},
FJOURNAL = {Mathematical and Computer Modelling},
VOLUME = {26},
YEAR = {1997},
NUMBER = {8-10},
PAGES = {281--304},
ISSN = {0895-7177},
CODEN = {MCMOEG},
MRCLASS = {81Q30 (05C30 81T18)},
MRNUMBER = {1492512},
MRREVIEWER = {R{\u{a}}zvan Gelca},
DOI = {10.1016/S0895-7177(97)00210-0},
ZBLNUMBER = {1185.81083},
}