# Set theory and relation

Let $$\mathcal{C}$$ be a collection of subsets of $$[n]$$ with the property that if $$A, B \in \mathcal{C},$$ then $$A \cap B \neq \varnothing .$$ (For example, $$\mathcal{C}=\{\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$$ has this property.) What is the largest that $$\mathcal{C}$$ can be? Hint: You will have to prove both that the number you get is possible and that no larger number is possible.

• So what is the largest number you have managed to show is possible? Can you always do $2^{n-1}$ for example? What is your conjecture for the largest number possible? – almagest Jan 21 at 10:59
• @almagest I am not able to prove that $2^{n-1}$ is upper bound for cardinality? I do this for $n=4$. – maths student Jan 21 at 11:05
• Can you clarify what you mean by '[n]'? – Doug Spoonwood Jan 21 at 11:11
• n is number of element original set can have? Say for given example we have 3 elements {1,2,3} then we have total $2^3$ possible subset out of which $2^{3-1}$ satisfy given condition. – maths student Jan 21 at 11:13

Hint1:

If a collection $$\mathcal D\subseteq\wp([n])$$ contains more than $$2^{n-1}$$ elements then for some $$A\in\mathcal D$$ we have $$A^{\complement}\in\mathcal D$$.

So such a collection is not a proper candidate for $$\mathcal C$$.

Then finding a collection $$\mathcal C$$ (as described) that contains $$2^{n-1}$$ elements is enough to prove that such a collection has $$2^{n-1}$$ elements.

Hint2.

In the case where $$n=2k+1$$ is odd have a look at the subsets that have a cardinality $$\geq k+1$$.

Can two of them have disjoint intersection? And how many are there?

The power-set of $$[n]$$, denoted $$\wp(n)$$ has cardinality $$2^n$$, and for each $$k \in [n]$$, the subset of $$\wp(n)$$ $$\uparrow\{k\} = \{A\subseteq[n]:k\in A\}$$ is such that $$\mid\uparrow\{k\}\mid=2^{n-1}$$ (can you tell why?).
It is also the case that $$k \in A$$, for all $$A \in \uparrow\{k\}$$, and so can always have $$\mid\mathcal C\mid=2^{n-1}$$.

Now, suppose you have $$\mid\mathcal C\mid>2^{n-1}$$. Can you see that there are always $$A,B \in \mathcal C$$ with $$A \cap B = \varnothing$$?
Notice that there will be $$A \in \wp(n)$$ such that both $$A$$ and $$[n]\setminus A$$ belong to $$\mathcal C$$.