Minimal Posets with Prescribed Maximal Chain Cardinalities

2023/05/27 by Bichoupan, Todd
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2305.17541

Abstract

Given a nonempty finite multiset S of positive integers, we wish to find a partially ordered set P of minimal cardinality such that the multiset of cardinalities of all maximal chains in P equals S. This paper establishes upper and lower bounds on the size of P: max(S) + \lceil log₂ |S| \rceil <= |P| <= max(S) + |S| - 1, and both bounds are tight.

Related

• Subsets of posets minimising the number of chains
• Supersaturation in Posets and Applications Involving the Container Method
• The Dimension of Divisibility Orders and Multiset Posets
• The chain covering number of a poset with no infinite antichains
• Order and chain polytopes of maximal ranked posets