Schur and $e$-positivity of trees and cut vertices
| Autor: | Samantha Dahlberg, Adrian She, Stephanie van Willigenburg |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Connected component
Mathematics::Combinatorics Degree (graph theory) Applied Mathematics 0102 computer and information sciences 01 natural sciences Tree (graph theory) Theoretical Computer Science Vertex (geometry) Combinatorics Symmetric function Computational Theory and Mathematics 010201 computation theory & mathematics Computer Science::Discrete Mathematics Bipartite graph FOS: Mathematics Discrete Mathematics and Combinatorics Mathematics - Combinatorics Geometry and Topology Combinatorics (math.CO) Primary 05E05 Secondary 05C05 05C15 05C70 16T30 20C30 Linear combination Connectivity Mathematics |
| DOI: | 10.48550/arxiv.1901.02468 |
| Popis: | We prove that the chromatic symmetric function of any $n$-vertex tree containing a vertex of degree $d\geq \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\geq\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. Comment: 21 pages, final version to appear Electron. J. Combin |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|