Given $S\subseteq \mathbb{N}$, we associate to $S$ the sum-graph $G_S = (\mathbb{N}, E)$ where $$E = \big\{\{m,n\}: m,n \in \mathbb{N} \text{ and } m+n\in S\big\}.$$ Is there an infinite subset $S\subseteq\mathbb{N}$ such that $G_S$ has infinitely many connected components?
$\begingroup$
$\endgroup$
asked Apr 8, 2015 at 11:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Write $S=\{s_1, s_2, \ldots\}$ with $s_i<s_{i+1}$ for all $i$. Then $G_S$ has infinitely many connected components as soon as $s_{i+1}>2s_i$ for all $i$. (In particular, $S=\{3^k: k\in \mathbf{N}\}$ will do.)
To see this, consider the induced subgraph $\Gamma_{n+1}$ on the vertices $\{1,\ldots,s_{n+1}\}$. It is obtained from the induced subgraph $\Gamma_n$ on the vertices $\{1,\ldots,s_n\}$ by "mirroring" at $s_{n+1}/2$. The connected components of $\Gamma_n$ now get twice as big and stay disjoint, while there is at least one new connected component due to the condition $s_{i+1}>2s_i+1$. The claim now follows by induction.
