7
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! Very nice argument on greedily building of $\mathcal{F}$. $\endgroup$ – Zihan Tan Jan 5 '17 at 1:30
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yes, this combination of parameters works! Basically the problem asks under what condition we can get $c=o(n)$, and in that case I suppose $\mathcal{F}$ will be automatically a very large collection due to the universal property (iii). $\endgroup$ – Zihan Tan Jan 2 '17 at 5:05
  • $\begingroup$ I suggest you edit the question to include that condition. $\endgroup$ – Aryeh Jan 2 '17 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.