Families of Subsets

Try this

Tap “All subsets containing 1”. How many members does $F$ have? Now add any subset that does not contain $1$ . What happens?
Tap “Number complement pairs”: each subset gets a small number, the same as its complement's. Why can't two subsets with the same number both be in $F$ ?
Clear, and pick differently: first ${1, 2}, {1, 3}, {2, 3}$ , then add every three-element subset and the whole set. How many members does $F$ have? Do every two of them intersect?
Into how many pairs are the $16$ subsets split?

A set whose elements are sets is called a family of subsets. The family of all subsets of $M$ is called the power set of $M$ (in the Chinese book, the “C-family”); when $∣ M ∣ = n$ it has $2^{n}$ members. Olympiad problems about families of subsets usually impose a rule on the family and ask how large it can be.

Predict first

In a family $F$ of subsets of ${1, 2, 3, 4, 5}$ , every two members share an element. At most how many members can $F$ have?

5

10

16

31

Choose an answer first; then you can see the result.

Why: pair them up

An intersecting family has at most 2^(n−1) members

Step 1 / 4

Build one first
Every two subsets containing $1$ intersect, and there are $2^{3} = 8$ of them. So the maximum is at least $8$ .

$∣ F ∣ \geq 8$
Pair up the subsets
Not both from one pair
The upper bound

“Construction + upper bound” is the standard two-step plan for problems like this: build an example to show the value can be reached, then use pairing (or boxes) to show you cannot do better. Pairing is really the pigeonhole principle: with $8$ boxes and $9$ subsets chosen, two must land in the same box, and they are complements, so they are disjoint.

Another rule: no containment

Change the rule: no member of $F$ contains another (such a family is called an antichain). Subsets in the same layer have the same number of elements, so none contains another; the widest is the middle layer, with $C_{4}^{2} = 6$ subsets. Can you pick more by mixing layers?

Sperner's theorem: an antichain has at most C(n,[n/2]) members

Step 1 / 4

The middle layer
The $6$ two-element subsets: none of them contains another.

$∣ F ∣ \geq C_{4}^{2} = 6$
Mixing layers causes trouble
String the subsets into chains
At most one per chain

Here the chains play the role that the complementary pairs played in the previous section: split all the objects into groups, and take at most one from each group. The number of groups is the upper bound.

Try

n = 3

yourself: how many members does the largest antichain have? Draw the symmetric chains and count them.

Practice

Exercise 1Basic

In a family of subsets of ${1, 2, \dots, 6}$ , every two members share an element. At most how many members can the family have?

Exercise 2Basic

Choose a family of subsets of ${1, 2, 3, 4, 5}$ in which no subset contains another. At most how many can you choose?

Exercise 3Advanced

Choose a family of subsets of ${1, 2, 3, 4, 5}$ in which the union of any two is never ${1, 2, 3, 4, 5}$ . At most how many can you choose?

Exercise 4Challenge

Choose a family of subsets of ${1, 2, \dots, 10}$ , each with at most $3$ elements, in which no subset contains another. At most how many can you choose?

Try this

Why: pair them up

An intersecting family has at most 2^(n−1) members

Another rule: no containment

Sperner's theorem: an antichain has at most C(n,[n/2]) members

Practice

Mistake Museum · Exhibits from this stop

Thinking a largest intersecting family must all share one element

Thinking any layer is a largest antichain