Exponential functions of finite posets and the number of extensions with a fixed set of minimal points
Preprint
Abstract
We establish formulas for the number of all downsets (or equivalently, of all antichains) of a finite poset P. Then, using these numbers, we determine recursively and explicitly the number of all posets having a fixed set of minimal points and inducing the poset P on the non- minimal points. It turns out that these counting functions are closely related to a collection of downset numbers of certain subposets. Since any function of that kind is an exponential sum (with the number of minimal points as exponent), we call it the exponential function of the poset. Some linear equations, divisibility relations, upper and lower bounds, and asymptotical equalities for the counting functions are deduced. A list of all such exponential functions for posets with up to five points concludes the paper.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- On the Cardinality of the -Topologies on a Finite SetInternational Journal of Combinatorics, 2014
- Posets on up to 16 PointsOrder, 2002
- The Number of Unlabeled Orders on Fourteen ElementsOrder, 2000
- The number of partially ordered sets with more points than incomparable pairsDiscrete Mathematics, 1992
- Counting finite posets and topologiesOrder, 1991
- Clique numbers of graphsDiscrete Mathematics, 1986
- On the cardinalities of finite topologies and the number of antichains in partially ordered setsDiscrete Mathematics, 1981
- Struktur- und anzahlformeln f r topologien auf endlichen mengenmanuscripta mathematica, 1974
- On the number of open sets of finite topologiesJournal of Combinatorial Theory, Series A, 1971