Existence of disjoint subsets of a family of subsets such that each element appears the same number of times in each

53 Views Asked by At

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

1

There are 1 best solutions below

0
On

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