Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Think anttichains. Gerhard "Ask Me About System Design" Paseman, 2013.01.04 –  Gerhard Paseman Jan 4 '13 at 8:58

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you; this indeed solves my problem. Is there any standard terminology for my "upwards convex" sets? "Convex join-semilattice"? –  Uli Fahrenberg Jan 4 '13 at 14:30
1  
Directed convex set? –  Emil Jeřábek Jan 4 '13 at 16:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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