Solutions to Homework 2, #6

7a. Take any $s$ sets in ${ℱ}_{s,t,\ell }$. By definition, each misses at most $\ell$ elements from $[t+s\ell ]$. Thus their intersection misses at most $s\ell$ elements from $[t+s\ell ]$ and thus has size at least $t$.

7b. Extend the definition of $S_{ij}$ to sets in the natural way. It's obvious that if $A$ is in ${ℱ}_{s,t,\ell }$ then $S_{ij}\left(A\right)$ is too. Hence shifting has no effect on ${ℱ}_{s,t,\ell }$.

7c. This one definitely takes much more explanation, but I don't think it's actually tricky -- you just have to follow your nose all the way through. However, you do have to avoid the following two extremely common mistakes:

"$S_{ij}ℱ$ is given by taking $S_{ij}\left(A\right)$ for all $A\in ℱ$." -- Not true.

"For any $Aʹ\in S_{ij}ℱ$, there is an $A\in ℱ$ such that $S_{ij}\left(A\right)=Aʹ$." -- False false false! Consider $i=1$, $j=2$, $n=2$, $ℱ=\left\{\right\{1\},\{2\left\}\right\}$. Then $S_{12}ℱ=ℱ$, and yet for $\left\{2\right\}\in S_{ij}ℱ$, there is no set $A\in ℱ$ such that $S_{12}\left(A\right)=\left\{2\right\}$!

Here is my two-part proof:

Part 1.
Suppose by way of contradiction that there are $s$ sets $B_1,...,B_s$ in $S_{ij}ℱ$ whose intersection is of size less than $t$. Let $A_1,...,A_s\in ℱ$ be the sets they "came from". So for each $k$, either $B_k=S_{ij}\left(A_k\right)$ or $B_k=A_k$, the latter occurring when $S_{ij}\left(A_k\right)$ is also in $ℱ$. Clearly, the $A_k$'s are all be distinct, and so the intersection of the $A_k$'s has size at least $t$.

How could the $A_k$'s have intersection at least $t$ and yet the $B_k$'s have intersection less than $t$? Certainly nothing changes on coordinates other than $i$ or $j$. It's also clear $S_{ij}$ can't cause coordinate $i$ to leave the intersection. This means that it must be the case that coordinate $j$ left the intersection. In particular, $j$ is in the intersection of the $A_k$'s and not in the intersection of the $B_k$'s.

Further, since we know that $j$ is in the intersection of the $A_k$'s, it follows that $i$ is not in the intersection of the $A_k$'s. Otherwise, we have both $i$ and $j$ in each $A_k$, which surely means that $i$ and $j$ are both in each $B_k$. But we've already established that $j$ is not in the intersection of the $B_k$'s.

Finally, since $i$ is not in the intersection of the $A_k$'s, and since shifting caused the intersection size to go down, $i$ had better not be in the intersection of the $B_k$'s.

To summarize, $j$ but not $i$ is in the intersection of the $A_k$'s, and neither $i$ nor $j$ is in the intersection of the $B_k$'s. Further, it must be the case that the $A_k$'s have intersection size exactly $t$.

Part 2.
Focus on the coordinates $i$ and $j$ in the $A_k$'s now. For each $A_k$ with a $0$ in the $i$ coordinate and a $1$ in the $j$ coordinate (and there is at least one such $A_k$), how come all those $1$'s didn't shift over into the $i$th coordinate, causing all the $B_k$'s to have $1$'s in their $i$th coordinate?

It must be because there is at least one $A_k$ -- say $A_1$ WOLOG -- such that $S_{ij}\left(A_1\right)$ was already in $ℱ$. So let's look at the intersection of the following $s$ distinct sets in $ℱ$: $S_{ij}\left(A_1\right),A_2,...,A_s$. These $s$ sets must also have intersection size at least $t$. Now the intersection of these is very similar to the intersection of $A_1,...,A_s$; however, $S_{ij}\left(A_j\right)$ does not have a $0$ in the $j$th coordinate. This means $j$ is not in the intersection of $S_{ij}\left(A_1\right),A_2,...,A_s$.

But this is a risky situation, because we concluded in Part 1 that $A_1,...,A_s$ had intersection size only $t$, and this included the fact that $j$ was in the intersection. The only way $S_{ij}\left(A_1\right),A_2,...,A_s$ could still have intersection size $t$ is if miraculously, putting in $S_{ij}\left(A_1\right)$ causes $i$ to be in the intersection, where it wasn't before.

But the only way for this to happen is if $A_1$ was the only set among $A_1,...,A_s$ with the pattern $0,1$ in coordinates $i,j$. In this case, every other $A_k$ has the pattern $1,1$, which certainly implies $B_k=A_k$. Further, we have $B_1=A_1$ by assumption (since $S_{ij}\left(A_1\right)$ was already in $ℱ$). So in fact all $B_k$'s equal their $A_k$'s. This is a contradiction because in Part 1 we concluded that $j$ was in the intersection of the $A_k$'s but not in the intersection of the $B_k$'s.