The Computational Complexity of Rules for the Character Table of S_n

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

24 pages

Scientific paper

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

The Computational Complexity of Rules for the Character Table of S_n does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Computational Complexity of Rules for the Character Table of S_n, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Computational Complexity of Rules for the Character Table of S_n will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-161007

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.