Permutation Tutte polynomial
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916237981777920 |
|---|---|
| author | Beke, Csongor Csáji, Gergely Kál Csikvári, Péter Pituk, Sára |
| author_facet | Beke, Csongor Csáji, Gergely Kál Csikvári, Péter Pituk, Sára |
| contents | The classical Tutte polynomial is a two-variate polynomial $T_G(x,y)$ associated to graphs or more generally, matroids. In this paper, we introduce a polynomial $\widetilde{T}_H(x,y)$ associated to a bipartite graph $H$ that we call the permutation Tutte polynomial of the graph $H$. It turns out that $T_G(x,y)$ and $\widetilde{T}_H(x,y)$ share many properties, and the permutation Tutte polynomial serves as a tool to study the classical Tutte polynomial. We discuss the analogs of Brylawsi's identities and Conde--Merino--Welsh type inequalities. In particular, we will show that if $H$ does not contain isolated vertices, then $$\widetilde{T}_H(3,0)\widetilde{T}_H(0,3)\geq \widetilde{T}_H(1,1)^2,$$ which gives a short proof to the analogous result of Jackson: $$T_G(3,0)T_G(0,3)\geq T_G(1,1)^2$$ for graphs without loops and bridges. We also improve on the constant $3$ in this statement by showing that one can replace it with $2.9243$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_01936 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Permutation Tutte polynomial Beke, Csongor Csáji, Gergely Kál Csikvári, Péter Pituk, Sára Combinatorics The classical Tutte polynomial is a two-variate polynomial $T_G(x,y)$ associated to graphs or more generally, matroids. In this paper, we introduce a polynomial $\widetilde{T}_H(x,y)$ associated to a bipartite graph $H$ that we call the permutation Tutte polynomial of the graph $H$. It turns out that $T_G(x,y)$ and $\widetilde{T}_H(x,y)$ share many properties, and the permutation Tutte polynomial serves as a tool to study the classical Tutte polynomial. We discuss the analogs of Brylawsi's identities and Conde--Merino--Welsh type inequalities. In particular, we will show that if $H$ does not contain isolated vertices, then $$\widetilde{T}_H(3,0)\widetilde{T}_H(0,3)\geq \widetilde{T}_H(1,1)^2,$$ which gives a short proof to the analogous result of Jackson: $$T_G(3,0)T_G(0,3)\geq T_G(1,1)^2$$ for graphs without loops and bridges. We also improve on the constant $3$ in this statement by showing that one can replace it with $2.9243$. |
| title | Permutation Tutte polynomial |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2311.01936 |