A Combinatorial Problem on Extremal Set Theory

Question

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

As mentioned below by Aryeh, 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.

Answer 1

This is arguably trivial, but maybe good enough for you: For any $a,b,c$ with $b \le a \le c$ (in particular $a=b=c$), if $\mathcal{F}$ is maximal subject to (i) and (ii), then it satisfies (iii) for free. So if you're okay with the $b \le a \le c$ condition, then you can otherwise pick the parameters however you want, and then greedily build $\mathcal{F}$.

The argument is very easy: In light of (i), (ii) can be equivalently restated as requiring $|S_1 \cap S_2| \le a - b/2$. (In general: $|S_1 \triangle S_2| = |S_1| + |S_2| - 2|S_1 \cap S_2|$.) Then, when $b \le a \le c$, if (iii) fails for some set, then you can add any size-$a$ subset of it to $\mathcal{F}$ while preserving (i) and (ii).

Semi-related note: I'm reminded of the combinatorial designs used in the Nisan-Wigderson generator. There, they want the sets in $\mathcal{F}$ to have only $O(\log(n))$ overlap (so $b = 2a - O(\log(n)$), but, instead of (iii), they only want that $\mathcal{F}$ is large. So if you want a larger range of parameters than $b \le a \le c$, or have some flexibility in the properties required of your objects, then you might try looking at the related literature for more ideas.

Answer 2

Did you want some condition to make $\mathcal{F}$ a large collection? Because the current definition allows for the following, presumably trivial, case. Consider $\mathcal{F}=\{S_1,S_2\}$, where $S_1=[n/2]$ and $S_2=[n]\setminus S_1$. Then we can take $a=n/2$, $b=n$, $c=n/2$.