Obtaining polynomial invariants for rooted trees from their random destruction

arXiv2302.08394MaRDI QIDQ6426705FDOQ6426705

Authors:

Publication date: 16 February 2023

Abstract: We use random destruction processes such as the random cutting model or site percolation on rooted trees to define several polynomial invariants for rooted trees. Some properties of these invariants are then exhibited, including recursion formulas and relations between them. The main result states that two of these invariants are complete, that is they distinguish rooted trees (in fact, even rooted forests) up to isomorphism. The proof method relies on recursion formulas and on irreducibility of the polynomials in suitable unique factorization domains. For other invariants, we provide counterexamples showing that they are not complete, although that question remains open for a certain trivariate invariant.

This page was built for publication: Obtaining polynomial invariants for rooted trees from their random destruction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426705)