0
$\begingroup$

For each non-negative integer $n$, what antichain(s) in $\{0,1\}^n$ with the pointwise partial order:
$\;\;$ 1. $\;$ have the most elements
$\;\;$ 2. $\;$ minimize the maximum of its elements' sum of coordinates, among those satisfying (1)
?



The obvious candidate is the set of elements whose sum of coordinates is $\: \Big\lfloor \frac{n}2 \Big\rfloor \:$.


Where $S$ is such a set and $\: m = \big\lfloor \log_2(|S|) \big\rfloor \:$, $\;$ I would also want an

efficiently computable injection $\: f : \{0,1\}^m \to S \:$ whose inverse is efficiently computable,

although I imagine that part would be straight-forward.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Your "obvious candidate" is right. this is Sperner's Theorem (not to be confused with Sperner's Lemma).

Improve this answer
$\endgroup$
1
  • $\begingroup$ The fifth google result for "Sperner's Theorem uniqueness" proves that to be essentially unique, $\hspace{.8 in}$ and the injection is in fact straight-forward to efficiently compute. $\;$ $\endgroup$
    – user5810
    Dec 29, 2011 at 22:17

Your Answer

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