Thread: Subsets (2)

We want to select as many subsets of [n] as possible so that any two selected subsets have at least one element in common. What is the largest number of subsets we can select?

I may commit a mistake in my working so please check it.

Claim: There are at least ways of doing this.
Proof: Consider the set . There are possible sunsets of this set.
plug in the element in each of the subsets of and we will have subsets of any two of which have as a common element.

Claim2: There are no more than ways of doing this.
Proof: Suppose subsets are found out which satisfy the question's demand. If is a subset then the complement of cant appear in our list of subsets. So for each subset of chosen there is one subset you can't choose namely its complement. Since we had chosen subsets, there are precisely subsets(complements of the chosen subsets) we can't chose. Since we see that we can't choose any more subsets as there were only possible subsets of .