First off: I'm not an expert in order theory, so some of my terms might be off; correct them if you wish.


Let me call a subset $A$ of a lattice $(S,\le)$ *upwards convex* (not sure if that's actually good terminology) if it holds that for all $a,b\in A$ and all $x\in S$ with $a\le x\le a\vee b$ (where $\vee$ is join), also $x\in A$.


Now let $M$ be a finite set with $n$ elements and $P\subseteq 2^M$ any subset of its power set. $P$ is (of course) not necessarily upwards convex, but it can be *covered* by upwards convex sets: there exist subsets $P\_1,\dots,P\_k\subseteq P$ such that all $P\_i$ are upwards convex and $P=P\_1\cup\dots\cup P\_k$. (One such covering is given by $P\_1,\dots,P\_k$ being the single-element subsets of $P$, proving the above existence claim.)


Say that $P$ is *$k$-coverable* if there exists a covering $P\_1,\dots,P\_k$ by upwards convex sets. Two questions:


1. What is the minimum $k$, as a function of $n$, such that any $P\subseteq 2^M$ is $k$-coverable?
2. What is the computational complexity of determining, given $P\subseteq 2^M$ and $k$, whether $P$ is $k$-coverable?


As a partial answer to (1), I can show that $k\ge n(n+1)/2 + 1$ using a recursive argument.



Covering of a partial order by upwards convex sets
The answer to (1) is $2^{n-1}$. If $P$ is the collection of all subsets of even cardinality, then each convex subset of $P$ is a singleton. Hence $k\geq 2^{n-1}$.


On the other hand, one can fix $a\in M$ divide all the subsets into pairs differing only in $a$. Then $P$ is the union of its intersections with the pairs, and each intersection is clearly convex.


