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.
 A: 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?
A: 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$.
