Skip to main content
2 of 2
fix typo
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

A Combinatorial Problem on Extremal Set Theory

Given a ground set $[n]$, under what condition of parameters $a,b,c$ does a family of subsets $\mathcal{F}\subseteq 2^{[n]}$ with the following property exist?

(i) $\forall S\in \mathcal{F}$, $|S|=a$.

(ii) $\forall S_1,S_2\in \mathcal{F}$, $|S_1\triangle S_2|\ge b$, where $S_1\triangle S_2$ means the symmetric difference between two sets.

(iii) $\forall T \subseteq [n], |T|\ge c$, $\exists S\in \mathcal{F}$, such that $|S\cap T|\ge 0.5a$.

A trivial case can be $\mathcal{F}=\{S_1,S_2\}$ with $S_1=[n/2]$ and $S_2=[n]-S_1$, where we have $a=c=n/2$ and $b=n$. Basically the problem asks under what condition of $a,b$ we can get $c=o(n)$.

Any known results or related ideas about nontrivial sufficient (no need to be necessary of course) condition of $a,b,c$ is appreciated.

This combinatorial problem rises from a communication game, and may have concrete connection with error-correcting codes.