Samenvatting
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.
| Originele taal-2 | Engels |
|---|---|
| Artikelnummer | P4.37 |
| Aantal pagina's | 19 |
| Tijdschrift | The Electronic Journal of Combinatorics |
| Volume | 31 |
| Nummer van het tijdschrift | 4 |
| DOI's | |
| Status | Gepubliceerd - 15 nov. 2024 |
Financiering
The author wishes to thank his former academic advisors at Uppsala University, Cecilia Holmgren and Svante Janson, for their generous support throughout. The gratitude is extended to Stephan Wagner for the many insightful comments and discussions, and to the anonymous referees for their helpful comments. This work was partially supported by grants from the Knut and Alice Wallenberg Foundation, the Ragnar S\u00F6derberg Foundation, and the Swedish Research Council. The author has received funding from the European Union\u2019s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement Grant Agreement No 101034253.