# Smallest $n$ for which, we can have $k$ distinct subsets of $[n]$ such that no two of them have empty intersection

Assume that, we know the number $k$, the number of distinct subsets of $[n]$ ( whose value we want to come up with ). The condition is that, no two subsets from the $k$ above should result in an empty set when we calculate intersection.

We want to find out smallest possible value for such $n$.

P.S. for example, if $k = 2$, then $n$ should be 2. Because for $n = 1$, the possible subsets are $\{1\}, \{\}$ and their intersection is $\varnothing$. With $n = 2$, the $2$ subsets can be $\{1\},\{1,2\}$. If we go like this, for $k=3$, we need $n = 3$ and for $k=4$, $n = 3$ is sufficient. How will this series progress(the value of $n$ for $k$)? Can we find a closed-form formula for $n$ in terms of $k$?

-
I can't remember the name of the theorem at the moment, but there's some result that the best you can do is by picking a single element to be in every set. – Ben Millwood Feb 19 '13 at 12:48
@Ben: You may be referring to Katona's theorem, of which this is a special case. – joriki Feb 19 '13 at 13:18
@joriki: can you please point me to the theorem. – Novice Feb 20 '13 at 6:11
@Novice: It's on page $1422$ of Intersection Theorems for Finite Sets and Geometric Applications, Peter Frankl, Proceedings of the International Congress of Mathematicians $1986$, p. $1419$. – joriki Feb 20 '13 at 6:35

If you have more than $2^{n-1}$ subsets of $[n]$ then you must have both a set $A$ and its complement $A^c$, by the pigeon-hole principle. Conversely, there are $2^{n-1}$ sets containing any given point $x\in[n]$.
:Thank you. I agree that for a given $n$ we can have at max $2^{n-1}$ subsets with one common element. I am curious about why do we need a common element in all the subsets? Can not we do this with out such element? Please explain. – Novice Feb 20 '13 at 6:18
@Novice: That's a double misrepresentation of what Sean wrote. He didn't write that we can have at most $2^{n-1}$ subsets with a common element; rather, he proved that we can't have more than $2^{n-1}$ pairwise intersecting subsets, before mentioning the example of sets containing a common element. Also, he didn't claim that we can't have $2^{n-1}$ pairwise intersecting subsets without a common element, and indeed we can: For instance, when $n$ is odd, the $2^{n-1}$ sets with at least $(n+1)/2$ elements are pairwise intersecting but don't all have a common element. – joriki Feb 20 '13 at 6:29