Let $A$ be a $101$-element subset of the set $S=\{1,2,\ldots,10^6\}$. For each $s\in S$ let $$A_s = A+s = \{a+s \mid a\in A\}$$
Prove that there exist $B\subset S$ such that $|B|=100$ and the sets in a family $$\{A_b \mid b\in B\}$$ are pairwise disjoint.
Is a following proof corect?
Let $B$ be maximal such set that sets in $\{A_b \mid b\in B\}$ are pairwise disjoint and let $|B|=k$.
Then for each $b'\in B'= S\setminus B$ exists such $b \in B$ that $A_b\cap A_{b'}\ne \emptyset$, i.e. exists $a_1,a_2\in A$ so that $$b' = a_1-a_2+b\;\;\;\;\;\;\;\;\;(*)$$
Now make a bipartite graph with $B'$ on the left side and on right side: $$C:= \{(a_1,a_2,b)\mid a_1,a_2\in A, a_1\ne a_2, b\in B\}$$
Clearly $ |C| = 101\cdot 100\cdot k$ and $|B'| = 10^6-k$.
Connect $b'\in B'$ with $(a_1,a_2,b)\in C$ iff $b' = a_1-a_2+b$. Then clearly each triple has degree at most $1$ and each $b'$ has because of $(*)$ degree at least $1$. By double counting we have:
$$ 10^6-k=|B'|\leq |C| = 101\cdot 100\cdot k$$
so $$k\geq {10^6\over 101\cdot 100+1}>99$$
So $k\geq 100$ and we are done.
Apart from a proof verification, I'm interested in probabilistic solution of this problem.
Best Answer
The proof is fine.
A more general setup for the proof would be to consider the graph $G$ with vertex set $S$ and an edge between $x, y\in S$ whenever $A_x \cap A_y = \varnothing$. (It might be more convenient to put an edge between $x,y$ for every element of $A_x \cap A_y$, making $G$ a multigraph.) Then we are looking for an independent set of $100$ vertices in $G$.
Your bipartite graph between $B'$ and $C$ has a sort of incarnation within $G$. Consider the subgraph of $G$ consisting of all edges between $B$ and $B'$. Every $b \in B$ has degree $101 \cdot 100$ in $G$ ($b$ has an edge to $b + a_1 - a_2$ for every $a_1, a_2 \in A$ with $a_1 \ne a_2$), and these edges must all go to $B'$, since $B$ is independent. Every $b' \in B'$ has at least $1$ edge to $B$, because $B$ is a maximal independent set. So the number of edges between $B$ and $B'$ is $101 \cdot 100 \cdot |B|$, but it's also at least $|B'| = 10^6-|B|$. Therefore $$ 10100 |B| \ge 10^6-|B| \iff |B| \ge \frac{10^6}{10101} > 99. $$ This is essentially a restatement of your argument: rather than have $10100$ elements of $C$ with degree $1$ for every $b \in B$, we combine them into a single vertex $b$ with degree $10100$.
More generally, this shows that in a graph (or multigraph) $G$ with $n$ vertices and maximum degree $\Delta(G)$, there is an independent set of size $\frac{n}{\Delta(G)+1}$.
The probabilistic method can be used here to get a bound that's better in general, but not an improvement in this problem. In general, we can get to $\frac{n}{d+1}$, where $d$ is the average degree in $G$. But here, the average degree is also quite close to $10100$, so this is not much help.
Here is the probabilistic argument. Randomly permute the elements of $S$ as $b_1, b_2, \dots, b_{10^6}$, and go through them one at a time to create an independent set $B$. For each $b_i$, add $b_i$ to $B$ if every element of the form $b_i + a_1 - a_2$ (with $a_1, a_2 \in A$ and $a_1 \ne a_2$) comes after $b_i$ in our random ordering.
This is guaranteed to create an independent set: if $b_i + a_1 - a_2 = b_j$, then either $i<j$ (and so we are guaranteed not to have picked $b_j$) or $i>j$ (and so we are guaranteed not to have picked $b_i$). For any $b \in S$: of $b$ and its at-most-$10100$ adjacent elements, each is equally likely to come first in the random ordering, and it's $b$ itself with probability $\frac{1}{10101}$, in which case we add it to $B$.
So the expected size of $B$ is at least $\frac1{10101}|S| = \frac{10^6}{10101} > 99$, as before, and therefore some random ordering produces a $B$ of size at least $100$.