3
$\begingroup$

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.

$\endgroup$

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.