ALGEBRAIC COMBINATORICS

no. 3

The perfect matching association scheme
Algebraic Combinatorics, Volume 3 (2020) no. 3, pp. 559-591.

We revisit the Bose–Mesner algebra of the perfect matching association scheme. Our main results are

  • An inductive algorithm, based on solving linear equations, to compute the eigenvalues of the orbital basis elements given the central characters of the symmetric groups.
  • Universal formulas, as content evaluations of symmetric functions, for the eigenvalues of fixed orbitals.
  • An inductive construction of an eigenvector (the so called first Gelfand–Tsetlin vector) in each eigenspace leading to a different inductive algorithm (not using central characters) for the eigenvalues of the orbital basis elements.
Received: 2018-08-13
Revised: 2019-11-28
Accepted: 2019-11-29
Published online: 2020-06-02
DOI: https://doi.org/10.5802/alco.104
Classification: 05E10,  05E05,  05E30
Keywords: perfect matching association scheme, content evaluation of symmetric functions, Gelfand–Tsetlin vectors. 
@article{ALCO_2020__3_3_559_0,
     author = {Srinivasan, Murali K.},
     title = {The perfect matching association scheme},
     journal = {Algebraic Combinatorics},
     pages = {559--591},
     publisher = {MathOA foundation},
     volume = {3},
     number = {3},
     year = {2020},
     doi = {10.5802/alco.104},
     language = {en},
     url = {alco.centre-mersenne.org/item/ALCO_2020__3_3_559_0/}
}
Srinivasan, Murali K. The perfect matching association scheme. Algebraic Combinatorics, Volume 3 (2020) no. 3, pp. 559-591. doi : 10.5802/alco.104. https://alco.centre-mersenne.org/item/ALCO_2020__3_3_559_0/

[1] Aker, Kürşat; Can, Mahir Bilen Generators of the Hecke algebra of (S 2n ,B n ), Adv. Math., Volume 231 (2012) no. 5, pp. 2465-2483 | Article | Zbl 1254.20005

[2] Bannai, Eiichi; Ito, Tatsuro Algebraic Combinatorics I: Association Schemes, Benjamin/Cummings, Menlo Park, California, 1984 | Zbl 0555.05019

[3] Bump, Daniel Lie Groups, 2nd edition, Grad. Texts Math., Volume 225, Springer, New York, 2013 | MR 3136522 | Zbl 1279.22001

[4] Can, Mahir Bilen; Özden, Şafak Corrigendum to “Generators of the Hecke algebra of (S 2n ,B n )” [Adv. Math. 231 (2012), no. 5, 2465–2483], Adv. Math., Volume 308 (2017), pp. 1337-1339 | Zbl 1419.20002

[5] Ceccherini-Silberstein, Tullio; Scarabotti, Fabio; Tolli, Filippo Representation Theory of the Symmetric Groups. The Okounkov–Vershik approach, Character formulas, and Partition Algebras, Camb. Stud. Adv. Math., Volume 121, Cambridge University Press, Cambridge, 2010 | Zbl 1230.20002

[6] Corteel, Sylvie; Goupil, Alain; Schaeffer, Gilles Content evaluation and class symmetric functions, Adv. Math., Volume 188 (2004) no. 2, pp. 315-336 | Article | MR 2087230 | Zbl 1059.05104

[7] Diaconis, Persi; Greene, Curtis Applications of Murphy’s elements (1989) (http://statweb.stanford.edu/~cgates/PERSI/papers/EFSNSF335.pdf)

[8] Diaconis, Persi; Holmes, Susan P. Random walks on trees and matchings, Electron. J. Probab., Volume 7 (2002), 6, 17 pages | MR 1887626 | Zbl 1007.60071

[9] Garsia, Adriano Young’s seminormal representation and Murphy elements of S n (2003) (http://www.math.ucsd.edu/~garsia/somepapers/Youngseminormal.pdf)

[10] Godsil, Christopher; Meagher, Karen Erdős–Ko–Rado Theorems: Algebraic Approaches, Cambridge Studies in Advanced Mathematics, Volume 149, Cambridge University Press, Cambridge, 2016 | Zbl 1343.05002

[11] Godsil, Christopher; Meagher, Karen An algebraic proof of the Erdős–Ko–Rado theorem for intersecting families of perfect matchings, Ars Math. Contemp., Volume 12 (2017) no. 2, pp. 205-217 | Article | Zbl 1370.05102

[12] Hanlon, Philip J.; Stanley, Richard P.; Stembridge, John R. Some combinatorial aspects of the spectra of normally distribited random matrices, Hypergeometric functions on domains of positivity, Jack polynomials, and applications (Tampa, FL, 1991) (Contemporary Mathematics) Volume 138, American Mathematical Society, Providence, RI, 1992, pp. 151-175 | Article | Zbl 0789.05092

[13] James, Gordon; Kerber, Adalbert The representation theory of the symmetric group, Encyclopedia of Mathematics and its Applications, Volume 16, Addison-Wesley Publishing Co., Reading, Mass., 1981 | MR 644144 | Zbl 0491.20010

[14] Jucys, Algimantas -A. A. Symmetric polynomials and the center of the symmetric group ring, Rep. Math. Phys., Volume 5 (1974), pp. 107-112 | Article | MR 419576 | Zbl 0288.20014

[15] Ku, Cheng Yeaw; Wong, Kok Bin Eigenvalues of the matching derangement graph, J. Algebr. Comb., Volume 48 (2018) no. 4, pp. 627-646 | MR 3871093 | Zbl 1401.05184

[16] Lindzey, Nathan Erdős–Ko–Rado for perfect matchings, Eur. J. Comb., Volume 65 (2017), pp. 130-142 | Article | MR 3679841 | Zbl 1369.05173

[17] Macdonald, Ian Grant Symmetric Functions and Hall Polynomials, Oxford University Press, Oxford, 1995 | Zbl 0824.05059

[18] Moran, Gadi The center of ℤ[S n+1 ] is the set of symmetric polynomials in n commuting transposition-sums, Trans. Am. Math. Soc., Volume 332 (1992) no. 1, pp. 167-180 | MR 1062873 | Zbl 0777.20003

[19] Murphy, G. E. A new construction of Young’s seminormal representation of the symmetric groups, J. Algebra, Volume 69 (1981) no. 2, pp. 287-297 | Article | MR 617079 | Zbl 0455.20007

[20] Murphy, G. E. The idempotents of the symmetric groups and Nakayama’s conjecture, J. Algebra, Volume 81 (1983) no. 1, pp. 258-265 | Article | MR 696137 | Zbl 0521.20005

[21] Muzychuk, Mikhail On association schemes of the symmetric group S 2n acting on partitions of type 2 n , Bayreuther Mathematische Schriften, Volume 47 (1994), pp. 151-164 | MR 1285207 | Zbl 0817.05080

[22] Okounkov, Andrei; Vershik, Anatoliĭ M. A new approach to the representation theory of the symmetric groups. II, (Russian) Zap. Nauchn. Sem. S.-Peterburg. Otdel. mat. Inst. Steklov. (POMI) 307 (2004), Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 10, 57-98, 281; translation in J. Math. Sci. (New York), Volume 131 (2005), pp. 5471-5494 | MR 2050688

[23] Prasad, Amritanshu Representation Theory. A Combinatorial Viewpoint, Camb. Stud. Adv. Math., Volume 147, Cambridge University Press, Delhi, 2015 | MR 3287258 | Zbl 1331.20007

[24] Sagan, Bruce E. The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Functions, Grad. Texts Math, Volume 203, Springer-Verlag, New York, 2001 | Zbl 0964.05070

[25] Saxl, Jan On multiplicity free permutation representations, Finite geometries and designs (Lond. Math. Soc. Lect. Note Ser.) Volume 49, Cambridge University Press, 1981, pp. 337-353 | Article | MR 627512 | Zbl 0454.20010

[26] Srinivasan, Murali K. A Maple program for computing θ ^ 2μ 2λ (2018) (http://www.math.iitb.ac.in/~mks/papers/EigenMatch.pdf)

[27] Stanley, Richard P. Enumerative Combinatorics - Volume 2, Camb. Stud. Adv. Math., Volume 62, Cambridge University Press, Cambridge, 1999 | Zbl 0928.05001

[28] Tout, Omar Structure coefficients of the Hecke algebra of (𝒮 2n ,ℬ n ), Electronic Journal of Combinatorics, Volume 21 (2014) no. 4, Paper 4.35, 41 pages | MR 3292272 | Zbl 1302.05207