Consider the sets $A_i \subset \{1,2, \cdots, n \}, 1 \leq i \leq k$ such that $A_i \cap A_j \neq \emptyset$ for $i \neq j$. Give an upper bound of $k$.
I have found sets $A_i = \{j : 1 \leq j \leq i \}$. Then clearly $A_i \cap A_j \neq \emptyset$. In fact for $i \neq j$ with $i<j$ we have $A_i \subset A_j$ $\implies A_i \cap A_j = A_i \neq \emptyset$. Since $A_i$'s are $n$ in numbers. So we have $k \geq n$. Can we do much better than that? Please help me in this regard.
Thank you very much.