Polynomial invariants for rooted trees related to their random destruction
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917794356920320 |
|---|---|
| author | Burghart, Fabian |
| author_facet | Burghart, Fabian |
| contents | We consider three bivariate polynomial invariants $P$, $A$, and $S$ for rooted trees, as well as a trivariate polynomial invariant $M$. These invariants are motivated by random destruction processes such as the random cutting model or site percolation on rooted trees. We exhibit recursion formulas for the invariants and identities relating $P$, $S$, and $M$. The main result states that the invariants $P$ and $S$ are complete, that is they distinguish rooted trees (in fact, even rooted forests) up to isomorphism. The proof method relies on the obtained recursion formulas and on irreducibility of the polynomials in suitable unique factorization domains. For $A$, we provide counterexamples showing that it is not complete, although that question remains open for the trivariate invariant $M$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_08394 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Polynomial invariants for rooted trees related to their random destruction Burghart, Fabian Combinatorics Probability 05C31 (Primary), 05C05, 60C05 (Secondary) We consider three bivariate polynomial invariants $P$, $A$, and $S$ for rooted trees, as well as a trivariate polynomial invariant $M$. These invariants are motivated by random destruction processes such as the random cutting model or site percolation on rooted trees. We exhibit recursion formulas for the invariants and identities relating $P$, $S$, and $M$. The main result states that the invariants $P$ and $S$ are complete, that is they distinguish rooted trees (in fact, even rooted forests) up to isomorphism. The proof method relies on the obtained recursion formulas and on irreducibility of the polynomials in suitable unique factorization domains. For $A$, we provide counterexamples showing that it is not complete, although that question remains open for the trivariate invariant $M$. |
| title | Polynomial invariants for rooted trees related to their random destruction |
| topic | Combinatorics Probability 05C31 (Primary), 05C05, 60C05 (Secondary) |
| url | https://arxiv.org/abs/2302.08394 |