0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.