Let $A$ be a $101$-element subset of the set $S=\{1,2,\ldots,1000000\}$

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.

• Can you explain the inequality $|B'|\le|C|$? – W-t-P May 4 at 20:06
• Each vertex in B' has degree at least one and ecah in C at most one – Aqua May 4 at 20:08

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

• If I'm not mistaken that is basicly method used also in a proof of Caro-Wei Theorem? web.evanchen.cc/handouts/ProbabilisticMethod/… – Aqua May 4 at 21:14
• Yes, that is exactly what's happening. I've always thought of this as Turán's theorem, though. (I guess Turán is the average-degree statement, while Caro-Wei is the stronger form with $\sum_{v \in V} \frac1{\deg(v)+1}$, which gives us a harmonic mean instead.) – Misha Lavrov May 4 at 21:19