# Existence of a family of size 2^Ω(n) of subsets of {1,...,n} each of cardinality n/4 where two subsets have at most n/8 elements in common

Let $$\mathcal{G}$$ be a family of $$t=2^{\Omega(n)}$$ subsets of $$N=\{1,2,...,n\}$$, each of cardinality $$n / 4$$ so that any two distinct members of $$\mathcal{G}$$ have at most $$n / 8$$ elements in common.

In the paper "The space complexity of approximating the frequency moments" by Alon et al. they say that the existence of such a familty $$\mathcal{G}$$ follows from basic results in coding theory.

Can anyone give a proof of the existence or provide any pointers to the relevant results in coding theory that this follows from?

• A proof sketch is given in Nisan & Wigderson, Hardness vs. randomness, Lemma 2.6. Nov 24 at 15:06
• Doesn't this follow by a standard kind of probabilistic construction? Just choose an appropriate number of random subsets of size $n/4$.. Then show that the expected number of pairs that have more than $n/8$ elements in common is less than 1... Nov 25 at 3:47
• Not a full answer, but the reduction is to represent each subset as a binary string of length $n$, with a one in the $i$th position iff the $i$th element is in the subset. The family $\mathcal{G}$ is an error-correcting code. With $x$ elements in common, the Hamming distance is $n/2-2x$.
– usul
Nov 25 at 22:08