1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Think anttichains. Gerhard "Ask Me About System Design" Paseman, 2013.01.04 $\endgroup$ Jan 4, 2013 at 8:58

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you; this indeed solves my problem. Is there any standard terminology for my "upwards convex" sets? "Convex join-semilattice"? $\endgroup$ Jan 4, 2013 at 14:30
  • 1
    $\begingroup$ Directed convex set? $\endgroup$ Jan 4, 2013 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.