0
$\begingroup$

Let $A$ be a set with $n$ elements. Consider a family $B$ of subsets of $A$ i.e. $B\subseteq\mathcal{P}(A)$.

How large must $B$ be to guarantee the existence of two nonempty disjoint subsets $X,Y\subseteq B$ (i.e. $X\cap Y=\emptyset$) such that $\forall a\in A$, the number of elements of $X$ that contain $a$ is equal to the number of elements of $Y$ that contain $a$?

$\endgroup$

1 Answer 1

0
$\begingroup$

Notice that your question is equivalent to asking: for a given $n$, what is the smallest $m$ such that any matrix $M\in\{0,1\}^{n\times m}$ has two disjoint subsets of the columns which have the same sum. The answer to your question is $m=\Theta(n\log n)$, which was found by Erdos and Renyi (they actually consider fixing $m$ and maximizing $n$, but this yields the same answer asyptotically). You can find their proof in the paper ``On two problems of information theory'' https://users.renyi.hu/~p_erdos/1963-12.pdf

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .