Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2501.04245 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912179813351424 |
|---|---|
| author | Li, Ethan Y. H. Li, Grace M. X. Yang, Arthur L. B. Zhang, Zhong-Xue |
| author_facet | Li, Ethan Y. H. Li, Grace M. X. Yang, Arthur L. B. Zhang, Zhong-Xue |
| contents | As introduced by Gutman and Harary, the independence polynomial of a graph serves as the generating polynomial of its independent sets. In 1987, Alavi, Malde, Schwenk and Erdős conjectured that the independence polynomials of all trees are unimodal. In this paper we come up with a new way for proving log-concavity of independence polynomials of graphs by means of their chromatic symmetric functions, which is inspired by a result of Stanley connecting properties of polynomials to positivity of symmetric functions. This method turns out to be more suitable for treating trees with irregular structures, and as a simple application we show that all spiders have log-concave independence polynomials, which provides more evidence for the above conjecture. Moreover, we present two symmetric function analogues of a basic recurrence formula for independence polynomials, and show that all pineapple graphs also have log-concave independence polynomials. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_04245 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A symmetric function approach to log-concavity of independence polynomials Li, Ethan Y. H. Li, Grace M. X. Yang, Arthur L. B. Zhang, Zhong-Xue Combinatorics 05C69, 05E05, 05C05, 05C15 As introduced by Gutman and Harary, the independence polynomial of a graph serves as the generating polynomial of its independent sets. In 1987, Alavi, Malde, Schwenk and Erdős conjectured that the independence polynomials of all trees are unimodal. In this paper we come up with a new way for proving log-concavity of independence polynomials of graphs by means of their chromatic symmetric functions, which is inspired by a result of Stanley connecting properties of polynomials to positivity of symmetric functions. This method turns out to be more suitable for treating trees with irregular structures, and as a simple application we show that all spiders have log-concave independence polynomials, which provides more evidence for the above conjecture. Moreover, we present two symmetric function analogues of a basic recurrence formula for independence polynomials, and show that all pineapple graphs also have log-concave independence polynomials. |
| title | A symmetric function approach to log-concavity of independence polynomials |
| topic | Combinatorics 05C69, 05E05, 05C05, 05C15 |
| url | https://arxiv.org/abs/2501.04245 |