This is inspired by an older (as yet unanswered) question.

Let us call a set $S\subseteq\omega$ thin in the 1st sense if $$\lim\sup_{n\to\infty}\frac{|S\cap n|}{n+1}=0$$ where $\omega$ is the first infinite cardinal, and $n=\{0,\ldots,n-1\}$ for all $n\in\omega$ with $n>0$.

Moreover, to $S\subseteq \omega$ we associate a simple, undirected graph $G_S=(\omega, E_S)$ where $$E_S = \big\{\{a,b\}:a\neq b\in \omega \textrm{ and }a+b\in S\big\}.$$

Let us call $S\subseteq \omega$ thin in the 2nd sense if the chromatic number $\chi(G_S)$ is finite.

Question. Are there any implications between these two notions of thinness?

  • 2
    $\begingroup$ Thin in the first sense is usually called asymptotic density zero. $\endgroup$ – Joel David Hamkins Feb 15 at 8:46
  • 1
    $\begingroup$ But also, why not divide by $n$ instead of $n+1$? It doesn't affect the limit, but since there are $n$ numbers below $n$, that ratio would be the proportion of numbers below $n$ in $S$, which might seem more natural. $\endgroup$ – Joel David Hamkins Feb 15 at 10:21
  • 1
    $\begingroup$ @JoelDavidHamkins: Sorry, I missed. I deleted my comment. $\endgroup$ – GH from MO Feb 15 at 14:48
  • $\begingroup$ @JoelDavidHamkins - for the only reason that $n+1 \neq 0$, for all $n\in\omega$. But yes, it is not elegant $\endgroup$ – Dominic van der Zypen Feb 15 at 17:23

The two notions are incomparable.

To see that the first notion does not imply the second, let's construct a set $S$ with asymptotic density $0$, but with infinite chromatic number. We place infinitely many increasingly large intervals into $S$, but spaced very far apart, so that the density is zero. If $S$ has an interval centered at $n$ of size $k$, then all numbers within $k/2$ of $n/2$ will be connected to the others in your graph. This will cause a complete subgraph in $G_S$ of size $k$. Since $k$ becomes as large as desired, the chromatic number of $G_S$ will be infinite.

Conversely, to see that the second notion does not imply the first, consider the set $S$ of odd numbers, which has density $1/2$. If $a+b$ is odd, then the parities of $a$ and $b$ must differ. So every edge in $G_S$ connects an odd number with an even number, and never two even numbers or two odd numbers. So the graph is $2$-colorable.


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.