5
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

Yes. Suppose $\mathcal{F}$ is partition-free of smaller size. Then there is some $A$ for which $\mathcal{F}$ contains neither $A$ nor its complement. It must be possible to add either $A$ or its complement to $\mathcal{F}$ to get a larger partition-free family, as otherwise $\mathcal{F}$ would already have to contain partitions of both $A$ and its complement, and therefore a partition of $[n]$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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