Skip to main content
1 of 2
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

Can a partition free family in $2^{[n]}$ always be enlarged to one of size $2^{n-1}$?

Let $\left[ n \right]=\{{1,2,\cdots,n\}}$ and call a family $\mathcal{F} \subset 2^{\left[n\right]}$ partition-free if it does not contain any partition of $\left[n\right]$. A recent question asked for the maximal size of such a set. The answer given is $2^{n-1}$ since having more than that allows a two member partition.

Q: can every partition-free family be enlarged to one of this size?

There is an interesting comparison to Intersecting Families (ones which contain no two disjoint members.) Here again the maximal size is $2^{n-1}$ because we never can have both a set and its complement. Any intersecting family can be enlarged to one of this size (a nice exercise). Thus there are many examples built from the lines of projective planes, weighted voting schemes etc. Also, any maximal intersecting family can be changed into any other by repeatedly switching a minimal member with its complement.

It is almost true that an intersecting family $\mathcal{F}$ is partition free. If $\left[n\right] \in \mathcal{F}$ (as will be the case for a maximal intersecting family) then we must replace $\left[n\right]$ with $\emptyset$ and then we will have a partition free-set.

There are certainly many other maximal partition-free families: From $\left[ 9 \right]$ start with all the sets with more than half the elements. Replace the whole set by $\emptyset$ and any set of size $6$ which does contain the element $1$ by its complement.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104