most recent 30 from http://mathoverflow.net 2013-05-19T05:44:26Z http://mathoverflow.net/feeds/question/58014 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/58014/minimum-set-cardinality-for-a-given-partially-ordered-set Vincent Blondel 2011-03-09T23:43:50Z 2011-03-10T02:18:35Z

<p>Let S be a finite set of cardinality k. I consider subsets of S that I order by set inclusion. For any given k, this defines the partially ordered set S_k.</p> <p>To a given partially ordered set P, I associate the smallest k such that P can be embedded in S_k (every element of P is paired with an element of S_k and the order is preserved). </p> <p>What is this smallest k equal to? How efficiently can it be computed?</p>

http://mathoverflow.net/questions/58014/minimum-set-cardinality-for-a-given-partially-ordered-set/58028#58028 Joel David Hamkins 2011-03-10T02:18:35Z 2011-03-10T02:18:35Z

<p>To get things started, there are a number of easy observations. </p> <ul> <li><p>First, $k$ is bounded above by $|P|$, since you can map every $p$ in $P$ to the lower cone $\{q\in P\mid q\leq p\}$. </p></li> <li><p>Second, $k$ is bounded below by the size of the longest chain in $P$ (minus one), since as you move up the chain, you must add at least one new element. This bound is clearly realized in any linear order, as well as in many nearly linear orders.</p></li> <li><p>It is not true in general that $k$ need be bounded below by the size of the largest antichain in $P$, since $S_k$ can have antichains (families of pairwise incomparable subsets) larger than $k$. For example, in $S_4$, there are six subsets of size $2$, forming an antichain. </p></li> <li><p>If $P$ is separative, then the optimal $k$ is bounded above by the number of minimal elements of $P$. The reason is that every node in a separative $P$ is determined the set of minimal elements below it. (Note, a partial order is <em>separative</em>, if whenever $q\not\leq p$, then there is $q'\leq p$ with $q$ and $q'$ incompatible, meaning that their lower cones are disjoint.) This case includes any Boolean algebra (with 0 removed), which amounts essentially to the $S_k$ themselves. </p></li> </ul> <p>But I expect a much better answer is possible...</p>