Browse issues
no. 6
Hyperoctahedral group characters and a type-BC analog of graph coloring
Skandera, Mark A.1
1 Lehigh University, Dept. of mathematics, 17 Memorial Drive E., Bethlehem, PA 18015 (USA)
Algebraic Combinatorics, Volume 8 (2025) no. 6, pp. 1651-1711

We state combinatorial formulas for hyperoctahedral group ($\mathfrak{B}_n$) character evaluations of the form $\chi (\widetilde{C}^{\mathsf {BC}}_w(1))$ where $\widetilde{C}^{\mathsf {BC}}_w(1) \in \mathbb{Z}[\mathfrak{B}_n]$ is a type-$\mathsf {BC}$ Kazhdan–Lusztig basis element, with $w \in \mathfrak{B}_n$ corresponding to simultaneously smooth type-$\mathsf {B}$ and $\mathsf {C}$ Schubert varieties. We also extend the definition of symmetric group codominance to elements of $\mathfrak{B}_n$ and show that for each element $w \in \mathfrak{B}_n$ as above, there exists a $\mathsf {BC}$-codominant element $v \in \mathfrak{B}_n$ satisfying $\chi (\widetilde{C}^{\mathsf {BC}}_w(1)) = \chi (\widetilde{C}^{\mathsf {BC}}_v(1))$ for all $\mathfrak{B}_n$-characters $\chi $. Combinatorial structures and maps appearing in these formulas are type-$\mathsf {BC}$ extensions of planar networks, unit interval orders, indifference graphs, poset tableaux, and colorings. Using the ring of type-$\mathsf {BC}$ symmetric functions, we introduce natural generating functions $Y(\widetilde{C}^{\mathsf {BC}}_w(1))$ for the above evaluations. These provide a new type-$\mathsf {BC}$ analog of Stanley’s chromatic symmetric functions [Adv. Math. 111 (1995) pp. 166–194].

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.459
Classification: 05A05, 05A15, 05E05, 05E10, 15A15
Keywords: hyperoctahedral group, characters, type-BC, graph coloring

Skandera, Mark A. 1

1 Lehigh University, Dept. of mathematics, 17 Memorial Drive E., Bethlehem, PA 18015 (USA)
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2025__8_6_1651_0,
     author = {Skandera, Mark A.},
     title = {Hyperoctahedral group characters and a {type-BC} analog of graph coloring},
     journal = {Algebraic Combinatorics},
     pages = {1651--1711},
     year = {2025},
     publisher = {The Combinatorics Consortium},
     volume = {8},
     number = {6},
     doi = {10.5802/alco.459},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.459/}
}
TY  - JOUR
AU  - Skandera, Mark A.
TI  - Hyperoctahedral group characters and a type-BC analog of graph coloring
JO  - Algebraic Combinatorics
PY  - 2025
SP  - 1651
EP  - 1711
VL  - 8
IS  - 6
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.459/
DO  - 10.5802/alco.459
LA  - en
ID  - ALCO_2025__8_6_1651_0
ER  - 
%0 Journal Article
%A Skandera, Mark A.
%T Hyperoctahedral group characters and a type-BC analog of graph coloring
%J Algebraic Combinatorics
%D 2025
%P 1651-1711
%V 8
%N 6
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.459/
%R 10.5802/alco.459
%G en
%F ALCO_2025__8_6_1651_0
Skandera, Mark A. Hyperoctahedral group characters and a type-BC analog of graph coloring. Algebraic Combinatorics, Volume 8 (2025) no. 6, pp. 1651-1711. doi: 10.5802/alco.459

[1] Abe, Hiraku; DeDieu, Lauren; Galetto, Federico; Harada, Megumi Geometry of Hessenberg varieties with applications to Newton–Okounkov bodies, Selecta Math. (N.S.), Volume 24 (2018) no. 3, pp. 2129-2163 | DOI | MR | Zbl

[2] Abe, Takuro; Horiguchi, Tatsuya; Masuda, Mikiya; Murai, Satoshi; Sato, Takashi Hessenberg varieties and hyperplane arrangements, J. Reine Angew. Math., Volume 764 (2020), pp. 241-286 | DOI | MR | Zbl

[3] Abreu, Alex; Nigro, Antonio Splitting the cohomology of Hessenberg varieties and e-positivity of chromatic symmetric functions, 2023 | arXiv | Zbl

[4] Abreu, Alex; Nigro, Antonio An update on Haiman’s conjectures, Forum Math. Sigma, Volume 12 (2024), Paper no. e86, 15 pages | DOI | MR | Zbl

[5] Abreu, Alex; Nigro, Antonio A geometric approach to characters of Hecke algebras, J. Reine Angew. Math., Volume 821 (2025), pp. 53-114 | DOI | MR | Zbl

[6] Adin, Ron; Athanasiadis, Christos; Elizalde, Sergi; Roichman, Yuval Character formulas and descents for the hyperoctahedral group, Adv. in Appl. Math., Volume 87 (2017), pp. 128-169 | DOI | MR | Zbl

[7] Anderson, David; Fulton, William Degeneracy loci, Pfaffians, and vexillary signed permutations in types B, C, and D, 2012 | arXiv | Zbl

[8] Anderson, David; Fulton, William Vexillary signed permutations revisited, Algebr. Comb., Volume 3 (2020) no. 5, pp. 1041-1057 | DOI | MR | Numdam | Zbl

[9] Athanasiadis, Christos Power sum expansion of chromatic quasisymmetric functions, Electron. J. Combin., Volume 22 (2015) no. 2, Paper no. 2.7, 9 pages | DOI | MR | Zbl

[10] Beck, Desiree; Remmel, Jeffrey; Whitehead, Tamsen The combinatorics of transition matrices between the bases of the symmetric functions and the B n analogues, Discrete Math., Volume 153 (1996), pp. 3-27 | DOI | Zbl | MR

[11] Billey, Sara Pattern avoidance and rational smoothness of Schubert varieties, Adv. Math., Volume 139 (1998), pp. 141-156 | DOI | Zbl | MR

[12] Billey, Sara; Lakshmibai, V. Singular loci of Schubert varieties, Progress in Mathematics, 182, Birkhäuser Boston Inc., 2000, xii+251 pages | DOI | Zbl | MR

[13] Billey, Sara; Lam, Tao Kai Vexillary elements in the hyperoctahedral group, J. Algebraic Combin., Volume 8 (1998) no. 2, pp. 139-152 | DOI | MR | Zbl

[14] Billey, Sara; Warrington, Gregory Kazhdan–Lusztig polynomials for 321-hexagon-avoiding permutations, J. Algebraic Combin., Volume 13 (2001) no. 2, pp. 111-136 | DOI | Zbl | MR

[15] Björner, Anders; Brenti, Francesco Combinatorics of Coxeter groups, Graduate Texts in Mathmatics, 231, Springer, 2005 | Zbl | MR

[16] Brosnan, Patrick; Chow, Timothy Unit interval orders and the dot action on the cohomology of regular semisimple Hessenberg varieties, Adv. Math., Volume 329 (2018), pp. 955-1001 | DOI | MR | Zbl

[17] Cellini, Paola; Papi, Paolo Ad-Nilpotent Ideals of a Borel Subalgebra, J. Algebra, Volume 225 (2000), pp. 130-141 | DOI | Zbl | MR

[18] Clearman, Samuel; Hyatt, Matthew; Shelton, Brittany; Skandera, Mark Evaluations of Hecke algebra traces at Kazhdan-Lusztig basis elements, Electron. J. Combin., Volume 23 (2016) no. 2, Paper no. 2.7, 56 pages | DOI | MR | Zbl

[19] Clearwater, Adam; Skandera, Mark Total nonnegativity and Hecke algebra trace evaluations, Ann. Combin., Volume 25 (2021), pp. 757-787 | DOI | Zbl

[20] Coll, Vincent Jr.; Mayers, Nicholas; Russoniello, Nicholas The index and spectrum of Lie poset algebras of types B, C, and D, Electron. J. Combin., Volume 28 (2021) no. 3, Paper no. 3.47, 23 pages | DOI | MR | Zbl

[21] Csar, Sebastian Alexander Root and weight semigroup rings for signed posets, Ph. D. Thesis, University of Minnesota (2014), 183 pages https://www.proquest.com/...

[22] De Mari, Filippo; Procesi, Claudio; Shayman, Mark Hessenberg varieties, Trans. Amer. Math. Soc., Volume 332 (1992) no. 2, pp. 529-534 | DOI | MR | Zbl

[23] De Mari, Filippo; Shayman, Mark Generalized Eulerian numbers and the topology of the Hessenberg variety of a matrix, Acta Appl. Math., Volume 12 (1988) no. 3, pp. 213-235 | DOI | MR | Zbl

[24] Deodhar, Vinay A combinatorial setting for questions in Kazhdan–Lusztig theory, Geom. Dedicata, Volume 36 (1990) no. 1, pp. 95-119 | DOI | Zbl | MR

[25] Dipper, Richard; James, Gordon Representations of Hecke algebras of type B n , J. Algebra, Volume 146 (1992), pp. 454-481 | DOI | Zbl | MR

[26] Ehresmann, Charles Sur la topologie de certains espaces homogènes, Ann. Math., Volume 35 (1934), pp. 396-443 | DOI | Zbl

[27] Fischer, Steven D. Signed poset homology and q-analog Möbius functions, Ph. D. Thesis, University of Michigan (1993) https://www.proquest.com/...

[28] Fishburn, Peter C. Interval orders and interval graphs, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1985, xi+215 pages | MR | Zbl

[29] Geck, Meinolf; Pfeiffer, Götz Characters of finite Coxeter groups and Iwahori-Hecke algebras, London Mathematical Society Monographs. New Series, 21, The Clarendon Press Oxford University Press, 2000, xvi+446 pages | DOI | MR | Zbl

[30] Gessel, Ira; Viennot, Gérard Determinants and plane partitions (1989) https://xavierviennot.org/... (Unpublished)

[31] Goulden, Ian; Jackson, David Immanants, Schur functions, and the MacMahon master theorem, Proc. Amer. Math. Soc., Volume 115 (1992) no. 3, pp. 605-612 | DOI | MR | Zbl

[32] Guay-Paquet, Mathieu A second proof of the Shareshian–Wachs conjecture, by way of a new Hopf algebra, 2016 | arXiv | Zbl

[33] Haiman, Mark Hecke algebra characters and immanant conjectures, J. Amer. Math. Soc., Volume 6 (1993) no. 3, pp. 569-595 | DOI | MR | Zbl

[34] Harada, Megumi; Precup, Martha; Tymoczko, Julianna Toward permutation bases in the equivariant cohomology rings of regular semisimple Hessenberg varieties, Matematica, Volume 1 (2022) no. 1, pp. 263-316 | DOI | MR | Zbl

[35] Harary, Frank On the notion of balance of a signed graph, Michigan Math. J., Volume 2 (1953/54), pp. 143-146 | DOI | MR | Zbl

[36] Hikita, Tatsuyuki A proof of the Stanley–Stembridge conjecture, 2024 | arXiv

[37] Hoefsmit, Peter Norbert Representations of Hecke algebras of finite groups with BN-pairs of classical type, Ph. D. Thesis, University of British Columbia (1974) https://www.proquest.com/...

[38] Humphreys, James E. Introduction to Lie algebras and representation theory, Graduate Texts in Mathematics, 9, Springer-Verlag, New York-Berlin, 1978, xii+171 pages | MR | Zbl

[39] Kaliszewski, Ryan; Lambright, Justin; Skandera, Mark Bases of the quantum matrix bialgebra and induced sign characters of the Hecke algebra, J. Algebraic Combin., Volume 49 (2019) no. 4, pp. 475-505 | DOI | MR | Zbl

[40] Karlin, Samuel; McGregor, James Coincidence probabilities, Pacific J. Math., Volume 9 (1959), pp. 1141-1164 | DOI | MR | Zbl

[41] Kazhdan, David; Lusztig, George Representations of Coxeter groups and Hecke algebras, Invent. Math., Volume 53 (1979), pp. 165-184 | DOI | MR | Zbl

[42] Kazhdan, David; Lusztig, George Schubert varieties and Poincaré duality, Proc. Symp. Pure. Math., A.M.S., Volume 36 (1980), pp. 185-203 | DOI | Zbl

[43] Kiem, Young-Hoon; Lee, Donggun Birational geometry of generalized Hessenberg varieties and the generalized Shareshian-Wachs conjecture, J. Combin. Theory Ser. A, Volume 206 (2024), Paper no. 105884, 45 pages | DOI | MR | Zbl

[44] Kiem, Young-Hoon; Lee, Donggun Geometry of the twin manifolds of regular semisimple Hessenberg varieties and unicellular LLT polynomials, Algebr. Comb., Volume 7 (2024) no. 3, pp. 861-885 | DOI | MR | Zbl

[45] Konvalinka, Matjaž; Skandera, Mark Generating functions for Hecke algebra characters, Canad. J. Math., Volume 63 (2011) no. 2, pp. 413-435 | DOI | MR | Zbl

[46] Kuroda, Masamichi; Tsujie, Shuhei Chromatic Signed-Symmetric Functions of Signed Graphs, 2021 | arXiv | Zbl

[47] Lakshmibai, V.; Sandhya, B. Criterion for smoothness of Schubert Varieties in SL(n)/B, Proc. Indian Acad. Sci. (Math Sci.), Volume 100 (1990) no. 1, pp. 45-52 | DOI | MR | Zbl

[48] Lambert, Jordan Theta-vexillary signed permutations, Electron. J. Combin., Volume 25 (2018) no. 4, Paper no. 4.53, 30 pages | DOI | MR | Zbl

[49] Lascoux, Alain; Schützenberger, Marcel-Paul Schubert Polynomials and the Littlewood–Richardson Rule, Letters in Math. Physics, Volume 10 (1985), pp. 111-124 | DOI | MR | Zbl

[50] Lindström, Berndt On the vector representations of induced matroids, Bull. London Math. Soc., Volume 5 (1973), pp. 85-90 | DOI | MR | Zbl

[51] Littlewood, Dudley E. The theory of group characters and matrix representations of groups, AMS Chelsea Publishing, Providence, RI, 2006, viii+314 pages | DOI | MR | Zbl

[52] Macdonald, I. G. Symmetric functions and Hall polynomials, Oxford Classic Texts in the Physical Sciences, The Clarendon Press, Oxford University Press, New York, 2015, xii+475 pages | MR | Zbl

[53] Merris, Russell; Watkins, William Inequalities and identities for generalized matrix functions, Linear Algebra Appl., Volume 64 (1985), pp. 223-242 | DOI | MR | Zbl

[54] Precup, Martha Affine pavings of Hessenberg varieties for semisimple groups, Selecta Math. (N.S.), Volume 19 (2013) no. 4, pp. 903-922 | DOI | MR | Zbl

[55] Proctor, Robert Classical Bruhat Orders and Lexicographic Shellability, J. Algebra, Volume 77 (1982), pp. 104-126 | DOI | MR | Zbl

[56] Reiner, Victor Signed posets, J. Combin. Theory Ser. A, Volume 62 (1993) no. 2, pp. 324-360 | DOI | MR | Zbl

[57] Rok, Alexandre; Szenes, Andras Eschers and Stanley’s chromatic e-positivity conjecture in length-2, 2023 | arXiv | Zbl

[58] Shareshian, John, 2018 (Personal communication)

[59] Shareshian, John; Wachs, Michelle Chromatic quasisymmetric functions and Hessenberg varieties, Configuration Spaces (Bjorner, A; Cohen, F; De Concini, C; Procesi, C; Salvetti, M, eds.), Edizione Della Normale (2012), pp. 433-460 | DOI | Zbl

[60] Shareshian, John; Wachs, Michelle Chromatic quasisymmetric functions, Adv. Math., Volume 295 (2016), pp. 497-551 | DOI | MR | Zbl

[61] Skandera, Mark On the dual canonical and Kazhdan-Lusztig bases and 3412-, 4231-avoiding permutations, J. Pure Appl. Algebra, Volume 212 (2008) no. 5, pp. 1086-1104 | DOI | MR | Zbl

[62] Skandera, Mark Characters and chromatic symmetric functions, Electron. J. Combin., Volume 28 (2021) no. 2, Paper no. P2.19, 39 pages | DOI | MR | Zbl

[63] Skandera, Mark Generating functions for monomial characters of wreath products ℤ/dℤ≀𝔖 n , Enum. Combin. Appl., Volume 1 (2021) no. 2, Paper no. S2R10, 10 pages | DOI | MR | Zbl

[64] Stanley, Richard P. A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math., Volume 111 (1995) no. 1, pp. 166-194 | DOI | MR | Zbl

[65] Stanley, Richard P. Positivity problems and conjectures in algebraic combinatorics, Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, pp. 295-319 | MR | Zbl

[66] Stanley, Richard P. Enumerative combinatorics. Volume 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, Cambridge, 2012, xiv+626 pages | MR | Zbl

[67] Stanley, Richard P. Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 208, Cambridge University Press, Cambridge, 2024, xvi+783 pages | MR

[68] Stanley, Richard P.; Stembridge, John R. On immanants of Jacobi-Trudi matrices and permutations with restricted position, J. Combin. Theory Ser. A, Volume 62 (1993) no. 2, pp. 261-279 | DOI | MR | Zbl

[69] Stembridge, John R. Ordinary representations of B n (1987) (Unpublished)

[70] Stembridge, John R. Some conjectures for immanants, Canad. J. Math., Volume 44 (1992) no. 5, pp. 1079-1099 | DOI | MR | Zbl

[71] Tamvakis, Harry Degeneracy locus formulas for amenable Weyl group elements, 2022 | arXiv | Zbl

[72] Trotter, William T. Combinatorics and partially ordered sets, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1992, xvi+307 pages | MR | Zbl

[73] Tymoczko, Julianna Linear conditions imposed on flag varieties, Amer. J. Math., Volume 128 (2006) no. 6, pp. 1587-1604 | MR | DOI | Zbl

[74] Tymoczko, Julianna Permutation actions on equivariant cohomology of flag varieties, Toric topology (Contemp. Math), Volume 460, Amer. Math. Soc., Providence, RI, 2008, pp. 365-384 | DOI | MR | Zbl

[75] Tymoczko, Julianna Permutation representations on Schubert varieties, Amer. J. Math., Volume 130 (2008) no. 5, pp. 1171-1194 | DOI | MR | Zbl

[76] Zaslavsky, Thomas Signed graph coloring, Discrete Math., Volume 39 (1982), pp. 215-228 | DOI | MR | Zbl

Cited by Sources: