The computational complexity of rules for the character table of S_n.

DOI10.1016/J.JSC.2003.11.001zbMATH Open1125.20302arXivmath/0309225OpenAlexW2023010579MaRDI QIDQ2643536FDOQ2643536

Authors: Dan Bernstein 

Publication date: 24 August 2007

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: The Murnaghan-Nakayama rule is the classical formula for computing the character table of S_n. Y. Roichman has recently discovered a rule for the Kazhdan-Lusztig characters of q-Hecke algebras of type A, which can also be used for the character table of S_n. For each of the two rules, we give an algorithm for computing entries in the character table of S_n. We then analyze the computational complexity of the two algorithms, and in the case of characters indexed by partitions in the (k,l)-hook, compare their complexities to each other. It turns out that the algorithm based on the Murnaghan-Nakayama rule requires far less operations than the other algorithm. We note the algorithms' complexities' relation to two enumeration problems of Young diagrams and Young tableaux.

Full work available at URL: https://arxiv.org/abs/math/0309225

Recommendations

• A \(q\)-rational Murnaghan-Nakayama rule
• Murnaghan-Nakayama Rules for Characters of Iwahori-Hecke Algebras of the Complex Reflection Groups G(r, p, n)
• An algoritm for calculating characters of hecke algebrasH_n(q) of typeA_n-1whenqis a root of unity
• A rational-function identity related to the Murnaghan-Nakayama formula for the characters of \(S_ n\)
• A proof of the Murnaghan-Nakayama rule using Specht modules and tableau combinatorics

zbMATH Keywords

algorithmsYoung diagramsYoung tableauxHecke algebrascharacter tablesMurnaghan-Nakayama rulecomputational complexitiesKazhdan-Lusztig characters

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40) Combinatorial aspects of representation theory (05E10) Hecke algebras and their representations (20C08) Representations of finite symmetric groups (20C30)

Cites Work

• Title not available (Why is that?)
• Representations of Coxeter groups and Hecke algebras
• Title not available (Why is that?)
• A recursive rule for Kazhdan-Lusztig characters
• Title not available (Why is that?)
• Title not available (Why is that?)
• On hooks of Young diagrams
• Title not available (Why is that?)
• The Characters of the Symmetric Group
• Maximal degrees for Young diagrams in the \((k,l)\) hook

Cited In (6)

• The number of steps in the Robinson-Schensted algorithm
• Generating weighted Hurwitz numbers
• Involutions and the Gelfand character
• RTNI—A symbolic integrator for Haar-random tensor networks
• On the number of \(\lambda\)-unimodal involutions
• On permutation statistics and Hecke algebra characters

This page was built for publication: The computational complexity of rules for the character table of \(S_n\).

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2643536)