Schur and \(e\)-positivity of trees and cut vertices

Samantha Dahlberg¹ ; Adrian She² ; Stephanie van Willigenburg³

¹Arizona State University
²University of Toronto
³University of British Columbia

The electronic journal of combinatorics, Tome 27 (2020) no. 1

Résumé

We prove that the chromatic symmetric function of any $n$-vertex tree containing a vertex of degree $d\geqslant \log _2n +1$ is not $e$-positive, that is, not a positive linear combination of elementary symmetric functions. Generalizing this, we also prove that the chromatic symmetric function of any $n$-vertex connected graph containing a cut vertex whose deletion disconnects the graph into $d\geqslant\log _2n +1$ connected components is not $e$-positive. Furthermore we prove that any $n$-vertex bipartite graph, including all trees, containing a vertex of degree greater than $\lceil \frac{n}{2}\rceil$ is not Schur-positive, namely not a positive linear combination of Schur functions. In complete generality, we prove that if an $n$-vertex connected graph has no perfect matching (if $n$ is even) or no almost perfect matching (if $n$ is odd), then it is not $e$-positive. We hence deduce that many graphs containing the claw are not $e$-positive.

Détail

DOI : 10.37236/8930

Classification : 05C05, 05C15, 05C70, 05E05, 16T30, 20C30
Mots-clés : Schur functions, chromatic symmetric function