# Diameter of sum-graph over a meager set

We say that $S\subseteq \mathbb{N}$ is meager if $$\text{lim sup}\frac{S\cap\{1,\ldots, n\}}{n} = 0.$$

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 a set $S\subseteq \mathbb{N}$ such that

• $S$ is meager;
• $G_S$ is connected;
• $\text{diam}(G_S)$ is infinite?

Let $S=\{2^k-1: k \in \mathbf{N}\}=\{1_2,(11)_2,(111)_2,...\}$.
Clearly $S$ is sparse.
Writing $m,n \in \mathbf{N}$ in their binary expansion, $m$ is connected to $n$ in $G_S$ if $m>n$ and $n$ is obtained by bitwise inverting $m$. For example, $(11001)_2$ is connected to $(00110)_2=(110)_2$. This shows that $G_S$ is connected by repeatedly applying this procedure to an arbitrary element to find a path to 1.
To show that there is no bound on the diameter of $G_S$, consider the sequence $(a_k)$ given by $1,(101)_2, (10101)_2, (1010101)_2,...=\{(2^{2k}-1)/3: k \in \mathbf{N}\}.$ Consider a path from $a_n$ to 1. Whenever a digit of a number on this path is flipped, all digits to the right are flipped too. This means that if the left-most digit of $a_n$, which is initially 1, is flipped $r$ times, then the second digit, which is initially 0, must be flipped at least $r+1$ times. By induction, $a_n$ has distance precisely $2n-2$ from 1.