<p>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 <em>maximal</em> 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}$.</p>

<p>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).</p>

<p>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.</p>

CC BY-SA 3.0
2017-01-05T01:30:53.627Z
Thanks! Very nice argument on greedily building of $\mathcal{F}$.
Zihan Tan
CC BY-SA 3.0
2017-01-04T19:02:00.937Z
2017-01-04T19:02:00.937Z
Andrew Morgan
<p>Did you want some condition to make $\mathcal{F}$ a <em>large</em> 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$.</p>

CC BY-SA 3.0
2017-01-02T05:05:59.700Z
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).
Zihan Tan
CC BY-SA 3.0
2017-01-02T08:03:29.893Z
I suggest you edit the question to include that condition.
Aryeh
CC BY-SA 3.0
2017-01-01T21:48:06.953Z
2017-01-01T21:48:06.953Z
Aryeh
<p>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?</p>

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

<p>(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.</p>

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

<p>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 <strong>under what condition of $a,b$ we can get $c=o(n)$.</strong></p>

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

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

<cc.complexity-theory><set-theory><extremal-combinatorics>
A Combinatorial Problem on Extremal Set Theory
Zihan Tan
# A Combinatorial Problem on Extremal Set Theory

(Asked by: username_0 on 2016-12-30)

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.

**Tags:** cc.complexity-theory, set-theory, extremal-combinatorics

---

## 2 answers

### Answer by username_1 on 2017-01-04. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks! Very nice argument on greedily building of $\mathcal{F}$.  

---

### Answer by username_2 on 2017-01-01. Score: 1

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

> **Comments:**
> **username_0**: 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).  
> **username_2**: I suggest you edit the question to include that condition.  

---

