The Redei-Berge Hopf algebra of digraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909146032373760 |
|---|---|
| author | Grujić, Vladimir Stojadinović, Tanja |
| author_facet | Grujić, Vladimir Stojadinović, Tanja |
| contents | In a series of recent talks Richard Stanley introduced a symmetric function associated to digraphs called the Redei-Berge symmetric function. This symmetric function enumerates descent sets of permutations corresponding to digraphs. We show that such constructed symmetric function arises from a suitable structure of combinatorial Hopf algebra on digraphs. The induced Redei-Berge polynomial satisfies the deletion-contraction property which makes it similar to the chromatic polynomial. The Berge's classical result on the number of Hamiltonian paths in digraphs is a consequence of the reciprocity formula for the Redei-Berge polynomial. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_07606 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Redei-Berge Hopf algebra of digraphs Grujić, Vladimir Stojadinović, Tanja Combinatorics 05C20, 16T30, 05E05 In a series of recent talks Richard Stanley introduced a symmetric function associated to digraphs called the Redei-Berge symmetric function. This symmetric function enumerates descent sets of permutations corresponding to digraphs. We show that such constructed symmetric function arises from a suitable structure of combinatorial Hopf algebra on digraphs. The induced Redei-Berge polynomial satisfies the deletion-contraction property which makes it similar to the chromatic polynomial. The Berge's classical result on the number of Hamiltonian paths in digraphs is a consequence of the reciprocity formula for the Redei-Berge polynomial. |
| title | The Redei-Berge Hopf algebra of digraphs |
| topic | Combinatorics 05C20, 16T30, 05E05 |
| url | https://arxiv.org/abs/2402.07606 |