1
$\begingroup$

Let $[n]$ denote the set of integers $\{1,2,\ldots,n\}$. A subset of $2^{[n]}$ is partition-free if it does not contain a partition of $[n]$.

What is the maximum size of a partition-free subset of $2^{[n]}$?

Note that it is easy to get such a subset of size $2^{n-1}$: for some choice $x\in[n]$, we have a partition-free subset $\{S : S\in 2^{[n]},\ x\notin S\}$.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

Given a set $S$ and its complement, you can use at most one, so you can't do better than $2^{n-1}$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ So the next question is to characterize the examples of maximal size. $\endgroup$
    – Andrés E. Caicedo
    Commented Jan 12, 2014 at 8:04
  • $\begingroup$ Well, they have to contain $\emptyset$. I just asked a question mathoverflow.net/questions/154321 which might be relevant. $\endgroup$
    – Aaron Meyerowitz
    Commented Jan 12, 2014 at 9:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .