For a fixed positive integer $n$, choose $2K$ subsets $A_1,A_2,\cdots,A_K$ and $B_1,B_2,\cdots,B_K$ from $[n]$ in the following way:

(1) $2K$ subsets are all distinct

(2) For any $i$ and $j$, $A_i\bigcap B_j\neq\emptyset$

I want to find $M$, which is the maximum of $K$. Clearly, $M\leq2^{n-1}$ since there are $2^n$ subsets of $[n]$ and hence $2M\leq2^n$.

One the other hand, one can easily find that $M\geq2^{n-2}$. Indeed, one can think of $2^{n-1}$ distinct subsets of $[2,n]=\{2,3,\cdots,n\}$, and adding $1$ to each subset would give us a desired collection of subsets of $[n]$ satisfying the conditions. Thus $2M\geq2^{n-1}$.

Now I have a rough bound $2^{n-2}\leq M\leq2^{n-1}$, but cannot go any further. Any suggestions would be helpful. Thanks.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.