Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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$?

share|improve this question
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 at 12:48
@Ben: You may be referring to Katona's theorem, of which this is a special case. – joriki Feb 19 at 13:18
@joriki: can you please point me to the theorem. – Novice Feb 20 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 at 6:35

1 Answer

up vote 5 down vote

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]$.

share|improve this answer
: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 at 6:18
2  
@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 at 6:29
@joriki: That is my bad. Thank you. – Novice Feb 20 at 10:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.