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.

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

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

  • $\begingroup$ If I'm not mistaken that is basicly method used also in a proof of Caro-Wei Theorem? web.evanchen.cc/handouts/ProbabilisticMethod/… $\endgroup$ – Aqua May 4 at 21:14
  • $\begingroup$ 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.) $\endgroup$ – Misha Lavrov May 4 at 21:19

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.