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?

  • 4
    $\begingroup$ A proof sketch is given in Nisan & Wigderson, Hardness vs. randomness, Lemma 2.6. $\endgroup$ Commented Nov 24, 2022 at 15:06
  • 2
    $\begingroup$ 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... $\endgroup$
    – Neal Young
    Commented Nov 25, 2022 at 3:47
  • 1
    $\begingroup$ 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$. $\endgroup$
    – usul
    Commented Nov 25, 2022 at 22:08


Your Answer

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

Browse other questions tagged or ask your own question.