Olga Azenhas ; Alessandro Conflitti ; Ricardo Mamede - Linear time equivalence of Littlewood―Richardson coefficient symmetry maps

dmtcs:2725 - Discrete Mathematics & Theoretical Computer Science, January 1, 2009, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) - https://doi.org/10.46298/dmtcs.2725
Linear time equivalence of Littlewood―Richardson coefficient symmetry mapsArticle

Authors: Olga Azenhas 1; Alessandro Conflitti 1; Ricardo Mamede 1

  • 1 Center for Mathematics [Coimbra]

Benkart, Sottile, and Stroomer have completely characterized by Knuth and dual Knuth equivalence a bijective proof of the Littlewood―Richardson coefficient conjugation symmetry, i.e. $c_{\mu, \nu}^{\lambda} =c_{\mu^t,\nu^t}^{\lambda ^t}$. Tableau―switching provides an algorithm to produce such a bijective proof. Fulton has shown that the White and the Hanlon―Sundaram maps are versions of that bijection. In this paper one exhibits explicitly the Yamanouchi word produced by that conjugation symmetry map which on its turn leads to a new and very natural version of the same map already considered independently. A consequence of this latter construction is that using notions of Relative Computational Complexity we are allowed to show that this conjugation symmetry map is linear time reducible to the Schützenberger involution and reciprocally. Thus the Benkart―Sottile―Stroomer conjugation symmetry map with the two mentioned versions, the three versions of the commutative symmetry map, and Schützenberger involution, are linear time reducible to each other. This answers a question posed by Pak and Vallejo.


Volume: DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
Section: Proceedings
Published on: January 1, 2009
Imported on: January 31, 2017
Keywords: Symmetry maps of Littlewood―Richardson coefficients,conjugation symmetry map,linearly time reduction of Young tableaux bijections,tableau―switching,Schützenberger involution,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • ALGEBRAIC COMBINATORICS ON Q,T-SYMMETRIC FUNCTIONS AND ENUMERATION ON POSETS AND COXETER SYSTEMS; Funder: Fundação para a Ciência e a Tecnologia, I.P.; Code: SFRH/BPD/30471/2006

Consultation statistics

This page has been seen 187 times.
This article's PDF has been downloaded 194 times.