Details
| Original language | English |
|---|---|
| Pages (from-to) | 125-156 |
| Number of pages | 32 |
| Journal | Journal of Combinatorial Mathematics and Combinatorial Computing |
| Volume | 110 |
| Publication status | Published - Aug 2019 |
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
- antichain, downset, extension, poset, topology, upset
ASJC Scopus subject areas
- Mathematics(all)
- General Mathematics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 110, 08.2019, p. 125-156.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Exponential functions of finite posets and the number of extensions with a fixed set of minimal points
AU - Campo, Frank A.
AU - Erne, Marcel
PY - 2019/8
Y1 - 2019/8
N2 - 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.
AB - 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.
KW - antichain
KW - downset
KW - extension
KW - poset
KW - topology
KW - upset
UR - http://www.scopus.com/inward/record.url?scp=85096221152&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:85096221152
VL - 110
SP - 125
EP - 156
JO - Journal of Combinatorial Mathematics and Combinatorial Computing
JF - Journal of Combinatorial Mathematics and Combinatorial Computing
SN - 0835-3026
ER -