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.


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.