1
$\begingroup$

Let $\mathcal{S}$ be the set of all $n$-element subsets of $[2n]:=\{1,\dots,2n\}$. Consider a partition $\mathcal{P}$ of $\mathcal{S}$ into $m$ blocks $P_1,\dots,P_m$, where all except at most one of the $P_i$ are of equal size.

Definition: For a block $P_i$, we say that a subset $A \subseteq [2n]$ is an intersection of $P_i$, if there are distinct sets $X_1,X_2 \in P_i$ such that $A = X_1 \cap X_2$. (Clearly, any intersection has a size at most $n-1$, i.e., there are $\sum_{k=0}^{n-1}{2n \choose k}$ subsets that can be intersections.) We say that an intersection $A$ occurs in partition $\mathcal{P}$, if $A$ is an intersection of some block of $\mathcal{P}$.

Question:

  1. For a given $m$, let ${I}(m)$ be the minimum number of intersections that must occur in any partition $\mathcal{P}$ of $\mathcal{S}$ into $m$ blocks (i.e. no matter how we choose $\mathcal{P}$). Is there a known (asymptotic) lower bound on the minimum number of intersections $I(m)$? (It is clear that $I(m)$ is a decreasing function in $m$, since $I(1) = \sum_{k=0}^{n-1}{2n \choose k} \ge 4^n$, whereas $I(|\mathcal{S}|) = 0$.)
  2. If there isn't anything known about this problem, I would be happy to be directed to similar combinatorial questions that have been studied.
$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.