Logo: to the web site of Uppsala University

uu.sePublications from Uppsala University
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A POLYNOMIAL ASSOCIATED WITH ROOTED TREES AND SPECIFIC POSETS
Stellenbosch Univ, Dept Logist, Private Bag X1, Stellenbosch, South Africa..
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Probability Theory and Combinatorics. Stellenbosch Univ, Dept Math Sci, Private Bag X1, Stellenbosch, South Africa..ORCID iD: 0000-0001-5533-2764
2022 (English)In: TRANSACTIONS ON COMBINATORICS, ISSN 2251-8657, Vol. 11, no 3, p. 255-279Article in journal (Refereed) Published
Abstract [en]

We investigate a trivariate polynomial associated with rooted trees. It generalises a bivariate polynomial for rooted trees that was recently introduced by Liu. We show that this polynomial satisfies a deletion-contraction recursion and can be expressed as a sum over maximal antichains. Several combinatorial quantities can be obtained as special values, in particular the number of antichains, maximal antichains and cutsets. We prove that two of the three possible bivariate specialisations characterise trees uniquely up to isomorphism. One of these has already been established by Liu, the other is new. For the third specialisation, we construct non-isomorphic trees with the same associated polynomial. We finally find that our polynomial can be generalised in a natural way to a family of posets that we call V-posets. These posets are obtained recursively by either disjoint unions or adding a greatest/least element to existing V-posets.

Place, publisher, year, edition, pages
UNIV ISFAHAN, VICE PRESIDENT RESEARCH & TECHNOLOGY , 2022. Vol. 11, no 3, p. 255-279
Keywords [en]
Rooted trees, polynomials, antichains, cutsets, posets
National Category
Geometry Computer Sciences
Identifiers
URN: urn:nbn:se:uu:diva-480269DOI: 10.22108/toc.2022.130043.1895ISI: 000817263600007OAI: oai:DiVA.org:uu-480269DiVA, id: diva2:1682195
Funder
Knut and Alice Wallenberg FoundationAvailable from: 2022-07-08 Created: 2022-07-08 Last updated: 2022-07-08Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Wagner, Stephan

Search in DiVA

By author/editor
Wagner, Stephan
By organisation
Probability Theory and Combinatorics
GeometryComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 51 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf