<p>Let <span class="math-container">$\mathcal{G}$</span> be a family of <span class="math-container">$t=2^{\Omega(n)}$</span> subsets of <span class="math-container">$N=\{1,2,...,n\}$</span>, each of cardinality <span class="math-container">$n / 4$</span> so that any two distinct members of <span class="math-container">$\mathcal{G}$</span> have at most <span class="math-container">$n / 8$</span> elements in common.</p>
<p>In the paper &quot;The space complexity of approximating the frequency moments&quot; by Alon et al. they say that the existence of such a familty <span class="math-container">$\mathcal{G}$</span> follows from basic results in coding theory.</p>
<p>Can anyone give a proof of the existence or provide any pointers to the relevant results in coding theory that this follows from?</p>

CC BY-SA 4.0
2022-11-24T15:06:54.990Z
A proof sketch is given in Nisan & Wigderson, Hardness vs. randomness, Lemma 2.6.
Emil Jeřábek
CC BY-SA 4.0
2022-11-25T03:47:24.707Z
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...
Neal Young
CC BY-SA 4.0
2022-11-25T22:08:59.850Z
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
<coding-theory><set-theory>
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
C. Mürtz
# 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

(Asked by: username_0 on 2022-11-24)

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?

**Tags:** coding-theory, set-theory
> **Comments:**
> **username_1**: A proof sketch is given in Nisan & Wigderson, Hardness vs. randomness, Lemma 2.6.  
> **username_2**: 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...  
> **username_3**: 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$.  

---

## 0 answers

