Number of upward closed subsets

510 Views Asked by At

I am looking for an algorithm of some sorts that can produce the total number of upward closed subsets in a partial ordered set.

Let $\langle P,\leq\rangle$ be a (finite) partial ordered set, then an upward closed subset is a subset $X\subseteq P$ such that for each $x\in X$ if $y> x$ then $y\in X$. Let $\mathbb{P}^*(P)$ denote the set of all possible upward closed subset. Then I need to compute the number of elements of $\mathbb{P}^*(P)$.

For example the set $P=\{a,b,c,d,e\}$ with $a>b$, $a>c$, $b>d$, $c>d$ and $c>e$ has upward closed subsets $\varnothing$, $\{a\}$, $\{a,b\}$, $\{a,c\}$, $\{a,b,c\}$, $\{a,b,c,d\}$, $\{a,c,e\}$, and $\{a,b,c,d,e\}$, so $\#\mathbb{P}^*(P)=8$.

I don't necessarily need to find each subset explicitly, just the number is enough.

1

There are 1 best solutions below

1
On BEST ANSWER

Outline: Every upward closed subset of a finite poset $\langle P,\le \rangle$ is uniquely identifiable with an antichain. Conversly, every antichain generates a upward closed subset of the finite poset. See here for an algorithm to count the number of antichains (and discussion about its complexity) and here for some reasonable bounds.