Partition と Young tableaux

対称群に関係したことを考えると, 必ず自然数や finite totally ordered set の partition や Young tableaux (Young diagram) が現れる。代数的トポロジーでは, 例えば多重ループ空間など。

• 自然数 \(n\) の partition
• 自然数 \(n\) の partition の Ferrers diagram
• 自然数 \(n\) の partition の Young tableaux
• \(\Sigma _n\) の共役類と \(n\) の partition が1対1に対応すること。
• \(p\)-regular partition と \(p\)-singular partition

Young tableaux の解説としては, AMS の Notices の “WHAT IS ...?” の連載にある Yong の [Yon07] がある。 また対称群の既約表現との直接の関係を解説したものとして, [VO04] がある。

Yong の解説によると, Young tableaux については, Robinson-Schensted 対応を抜きには話せない, らしい。対称群の元に対し同じ shape の Young tableau の組を対応させる規則である。

• Robinson-Schensted 対応 (algorighm)

Lam と Shimozono の [LS07] には, algebraic combinatorics で最も重要な algorithm であると書いてある。 様々な人により一般化が考えられている。

Partition は symmetric function に密接に関係している。

• symmetric function

よって, symmetric function の一般化を扱うために, 様々な Young tableaux の変種が考えられている。とりあえず目にしたものを列挙してみた:

• ribbon tableaux [LLT97]
• 列だけ考えたものやその pair [LT96]
• domino tableaux [BK00; TV09]
• excited Young diagram [IN09]
• plane partition と \(3\)次元Young diagram

Berenstein と Kirillov の [BK00] によると, domino tableaux の shortest definition は Macdonald の本 [Mac95] の139ページにあるものらしい。

\(3\)次元版については, 最近数理物理でも使われている。 Okounkov と Reshetikhin と Vara の [ORV06] や Young と Bryan の [You10] など。Richard Szabo の [Sza11] では, MacMahon による plane partition の generating function の公式については, Stanley の本 [Sta99] が参照されている。§7.20 と §7.21 あたりに plane partition について書いてある。MacMahon の公式は、 Corollary 7.20.3 として書かれている。また401ページの最後の段落から, plane partition についての歴史についてまとめられている。

Govindarajar [Gov13] によると, 任意の次元で通用する高次元の partition の数え上げについては, Atkin らの [Atk+67], Bratley と McKay の [BM67], Knuthの[Knu70] などがある。

Partition の中でも noncrossing partition は様々な分野に関係があり, 一般化も考えられている。

• noncrossing partition

Partition に関することを一般化しようとするときによくやるのは, Dowling analogue, つまり有限群 \(G\) の作用を考えたものである。より正確には \(\{1,\cdots ,n\}\times G\) の partition を考える。 Delucchi [Del07] によると Dowling lattice は T.A. Dowling のある種の hyperplane arrangement の intersection lattice に関する仕事 [Dow73] にちなんで名付けられたようである。

• Dowling lattice

Dowling lattice については, この Delucchi の [Del07] に書いてある文献をみるとよい。

群の作用を持つ集合のより一般の equivariant partition を調べたものとして, Bergner らの [Ber+] がある。

• equivariant partition

Bipartition というものもある。Foata と Zeilberger の [FZ96] で導入された。Hetyei と Krattenthaler の [HK11] で bipartition の成す poset が調べられている。

• bipartition

References

[Atk+67]

A. O. L. Atkin, P. Bratley, I. G. Macdonald, and J. K. S. McKay. “Some computations for \(m\)-dimensional partitions”. In: Proc. Cambridge Philos. Soc. 63 (1967), pp. 1097–1100. url: https://doi.org/10.1017/s0305004100042171.

[Ber+]

Julia E. Bergner, Peter Bonventre, Maxine E. Calle, David Chan, and Maru Sarazola. Equivariant Trees and Partition Complexes. arXiv: 2302.08949.

[BK00]

Arkady Berenstein and Anatol N. Kirillov. “Domino tableaux, Schützenberger involution, and the symmetric group action”. In: Discrete Math. 225.1-3 (2000). Formal power series and algebraic combinatorics (Toronto, ON, 1998), pp. 15–24. arXiv: q-alg/9709010. url: http://dx.doi.org/10.1016/S0012-365X(00)00145-X.

[BM67]

P. Bratley and J. K. S. McKay. “Algorithm 313: Multi-dimensional partition generator”. In: Commun. ACM 10.10 (Oct. 1967), pp. 666–. eprint: \url{http://doi.acm.org/10.1145/363717.363783}.

[Del07]

Emanuele Delucchi. “Nested set complexes of Dowling lattices and complexes of Dowling trees”. In: J. Algebraic Combin. 26.4 (2007), pp. 477–494. arXiv: math/0603383. url: http://dx.doi.org/10.1007/s10801-007-0067-2.

[Dow73]

T. A. Dowling. “A \(q\)-analog of the partition lattice”. In: A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Ft Collins, Colo., 1971). 1973, pp. 101–115.

[FZ96]

Dominique Foata and Doron Zeilberger. “Graphical major indices”. In: J. Comput. Appl. Math. 68.1-2 (1996), pp. 79–101. url: http://dx.doi.org/10.1016/0377-0427(95)00254-5.

[Gov13]

Suresh Govindarajan. “Notes on higher-dimensional partitions”. In: J. Combin. Theory Ser. A 120.3 (2013), pp. 600–622. arXiv: 1203. 4419. url: https://doi.org/10.1016/j.jcta.2012.11.005.

[HK11]

Gábor Hetyei and Christian Krattenthaler. “The poset of bipartitions”. In: European J. Combin. 32.8 (2011), pp. 1253–1281. arXiv: 0906.3879. url: http://dx.doi.org/10.1016/j.ejc.2011.03.019.

[IN09]

Takeshi Ikeda and Hiroshi Naruse. “Excited Young diagrams and equivariant Schubert calculus”. In: Trans. Amer. Math. Soc. 361.10 (2009), pp. 5193–5221. arXiv: math/0703637. url: https://doi.org/10.1090/S0002-9947-09-04879-X.

[Knu70]

Donald E. Knuth. “A note on solid partitions”. In: Math. Comp. 24 (1970), pp. 955–961. url: https://doi.org/10.2307/2004628.

[LLT97]

Alain Lascoux, Bernard Leclerc, and Jean-Yves Thibon. “Ribbon tableaux, Hall-Littlewood functions, quantum affine algebras, and unipotent varieties”. In: J. Math. Phys. 38.2 (1997), pp. 1041–1068. arXiv: q-alg/9512031. url: http://dx.doi.org/10.1063/1.531807.

[LS07]

Thomas F. Lam and Mark Shimozono. “Dual graded graphs for Kac-Moody algebras”. In: Algebra Number Theory 1.4 (2007), pp. 451–488. arXiv: math/0702090. url: http://dx.doi.org/10.2140/ant.2007.1.451.

[LT96]

Bernard Leclerc and Jean-Yves Thibon. “The Robinson-Schensted correspondence, crystal bases, and the quantum straightening at \(q=0\)”. In: Electron. J. Combin. 3.2 (1996). The Foata Festschrift, Research Paper 11, approx. 24 pp. (electronic). arXiv: q-alg/9504004. url: http://www.combinatorics.org/Volume_3/Abstracts/v3i2r11.html.

[Mac95]

I. G. Macdonald. Symmetric functions and Hall polynomials. Second. Oxford Mathematical Monographs. With contributions by A. Zelevinsky, Oxford Science Publications. New York: The Clarendon Press Oxford University Press, 1995, pp. x+475. isbn: 0-19-853489-2.

[ORV06]

Andrei Okounkov, Nikolai Reshetikhin, and Cumrun Vafa. “Quantum Calabi-Yau and classical crystals”. In: The unity of mathematics. Vol. 244. Progr. Math. Boston, MA: Birkhäuser Boston, 2006, pp. 597–618. arXiv: hep-th/0309208.

[Sta99]

Richard P. Stanley. Enumerative combinatorics. Vol. 2. Vol. 62. Cambridge Studies in Advanced Mathematics. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. Cambridge: Cambridge University Press, 1999, pp. xii+581. isbn: 0-521-56069-1; 0-521-78987-7. url: http://dx.doi.org/10.1017/CBO9780511609589.

[Sza11]

Richard J. Szabo. “Crystals, instantons and quantum toric geometry”. In: Acta Phys. Polon. B Proc. Suppl. 4.3 (2011), pp. 461–493. arXiv: 1102.3861.

[TV09]

Nathaniel Thiem and C. Ryan Vinroot. “Gelfand-Graev characters of the finite unitary groups”. In: Electron. J. Combin. 16.1 (2009), Research Paper 146, 37. arXiv: math / 0611010. url: https://doi.org/10.37236/235.

[VO04]

A. M. Vershik and A. Yu. Okun\('\)kov. “A new approach to representation theory of symmetric groups. II”. In: Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 307.Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 10 (2004), pp. 57–98, 281. arXiv: math/0503040. url: http://dx.doi.org/10.1007/s10958-005-0421-7.

[Yon07]

Alexander Yong. “What is \(\dots \) a Young tableau?” In: Notices Amer. Math. Soc. 54.2 (2007), pp. 240–241. arXiv: math/0611030.

[You10]

Benjamin Young. “Generating functions for colored 3D Young diagrams and the Donaldson-Thomas invariants of orbifolds”. In: Duke Math. J. 152.1 (2010). With an appendix by Jim Bryan, pp. 115–153. arXiv: 0802.3948. url: https://doi.org/10.1215/00127094-2010-009.