ALGEBRAIC COMBINATORICS

no. 1
Chromatic symmetric functions via the group algebra of S n
Pawlowski, Brendan1
1 University of Southern California Los Angeles, California, USA
Algebraic Combinatorics, Volume 5 (2022) no. 1, pp. 1-20.

We prove some Schur positivity results for the chromatic symmetric function X G of a (hyper)graph G, using connections to the group algebra of the symmetric group. The first such connection works for (hyper)forests F: we describe the Schur coefficients of X F in terms of eigenvalues of a product of Hermitian idempotents in the group algebra, one factor for each edge (a more general formula of similar shape holds for all chordal graphs). Our main application of this technique is to prove a conjecture of Taylor on the Schur positivity of certain X F , which implies Schur positivity of the formal group laws associated to various combinatorial generating functions. We also introduce the pointed chromatic symmetric function X G,v associated to a rooted graph (G,v). We prove that if X G,v and X H,w are positive in the generalized Schur basis of Strahov, then the chromatic symmetric function of the wedge sum of (G,v) and (H,w) is Schur positive.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.134
Classification: 05E05, 05E10, 05C15
Keywords: Chromatic symmetric function, pointed chromatic symmetric function, Schur positivity.
Pawlowski, Brendan 1

1 University of Southern California Los Angeles, California, USA
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2022__5_1_1_0,
     author = {Pawlowski, Brendan},
     title = {Chromatic symmetric functions via the group algebra of $S_n$},
     journal = {Algebraic Combinatorics},
     pages = {1--20},
     publisher = {MathOA foundation},
     volume = {5},
     number = {1},
     year = {2022},
     doi = {10.5802/alco.134},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.134/}
}
TY  - JOUR
AU  - Pawlowski, Brendan
TI  - Chromatic symmetric functions via the group algebra of $S_n$
JO  - Algebraic Combinatorics
PY  - 2022
SP  - 1
EP  - 20
VL  - 5
IS  - 1
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.134/
DO  - 10.5802/alco.134
LA  - en
ID  - ALCO_2022__5_1_1_0
ER  - 
%0 Journal Article
%A Pawlowski, Brendan
%T Chromatic symmetric functions via the group algebra of $S_n$
%J Algebraic Combinatorics
%D 2022
%P 1-20
%V 5
%N 1
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.134/
%R 10.5802/alco.134
%G en
%F ALCO_2022__5_1_1_0
Pawlowski, Brendan. Chromatic symmetric functions via the group algebra of $S_n$. Algebraic Combinatorics, Volume 5 (2022) no. 1, pp. 1-20. doi : 10.5802/alco.134. https://alco.centre-mersenne.org/articles/10.5802/alco.134/

[1] Björner, Anders; Ziegler, Günter M. Broken circuit complexes: factorizations and generalizations, J. Combin. Theory Ser. B, Volume 51 (1991) no. 1, pp. 96-126 | DOI | MR | Zbl

[2] Dénes, József The representation of a permutation as the product of a minimal number of transpositions, and its connection with the theory of graphs, Publ. Math. Inst. Hung. Acad. Sci., Volume 4 (1959), pp. 63-71 | MR | Zbl

[3] Gasharov, Vesselin Incomparability graphs of (3+1)-free posets are s-positive, Discrete Math., Volume 157 (1996) no. 1-3, pp. 193-197 | DOI | MR | Zbl

[4] Guay-Paquet, Mathieu A modular law for the chromatic symmetric functions of (3+1)-free posets (2013) (https://arxiv.org/abs/1306.2400)

[5] Horn, Roger A.; Johnson, Charles R. Matrix analysis, Cambridge University Press, Cambridge, 2013, xviii+643 pages | MR

[6] Macdonald, Ian G. Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995, x+475 pages | MR

[7] Moszkowski, Paul A solution to a problem of Dénes: a bijection between trees and factorizations of cyclic permutations, European J. Combin., Volume 10 (1989) no. 1, pp. 13-16 | DOI | MR | Zbl

[8] Stanley, Richard P. A Schur positivity conjecture related to row and column permutations, MathOverflow https://mathoverflow.net/q/254782 (version: 2017-04-13)

[9] 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

[10] Stanley, Richard P. Graph colorings and related symmetric functions: ideas and applications: a description of results, interesting applications, & notable open problems, Discrete Math., Volume 193 (1998) no. 1-3, pp. 267-286 Selected papers in honor of Adriano Garsia (Taormina, 1994) | DOI | MR | Zbl

[11] Stanley, Richard P. Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, Cambridge, 1999, xii+581 pages | DOI | MR

[12] 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

[13] Strahov, Eugene Generalized characters of the symmetric group, Adv. Math., Volume 212 (2007) no. 1, pp. 109-142 | DOI | MR | Zbl

[14] Taylor, Jair Formal group laws and hypergraph colorings, Ph. D. Thesis, University of Washington (2016) | MR

[15] Taylor, Jair Chromatic symmetric functions of hypertrees, Electron. J. Combin., Volume 24 (2017) no. 2, Paper no. 2.2, 18 pages | MR | Zbl

[16] Vershik, Anatoli M.; Okounkov, Andrei Yu. A new approach to the representation theory of symmetric groups. II, J. Math. Sci., Volume 131 (2005) no. 2, pp. 5471-5494 | DOI | MR

Cited by Sources: