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.

Improve this question
$\endgroup$
7
  • $\begingroup$ the last sentence in the paragraph is interesting, can you point me to a lecture/something that explains how to do it? I know this post was 7 years ago, so maybe someone else can also point me towards the right direction.. $\endgroup$
    – AyamGorengPedes
    Commented Dec 19, 2021 at 15:48
  • $\begingroup$ If you have a minimal member A, every other member B has some element in B but not in A. So what f we discard A and replace it with its complement, you have a new intersecting family of size $2^{n-1}$ $\endgroup$
    – Aaron Meyerowitz
    Commented Dec 19, 2021 at 21:15
  • $\begingroup$ Uhmm, that is not my confusion, but rather "any maximal intersecting family can be changed into any other". For example given the base set [1,...,n], and we take all of the sets that contain 1, how can we turn this into the family where all of it's sets contain 2? How to do it in general, is there an "algorithm" for it? $\endgroup$
    – AyamGorengPedes
    Commented Dec 19, 2021 at 21:30
  • $\begingroup$ @AyamGorengPedes Suppose $n=5$ and write 12 for $\{1,2\}$. First replace 1 with 2345 then 13,14,15 with 245,235,234 (one at at time) then 134,135,145 with 25,24,23 finally 1345 with 2. The start and end families had an overlap of $8$ out of $16$. Each move increases the overlap with the end by $1$. $\endgroup$
    – Aaron Meyerowitz
    Commented Dec 21, 2021 at 7:07
  • $\begingroup$ And after we swap 134 with 25, how do we swap 135? I couldn't find a workaround $\endgroup$
    – AyamGorengPedes
    Commented Dec 22, 2021 at 0:44

1 Answer 1

Reset to default
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]$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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