# A notion of thinness for subsets of $\omega$, using chromatic number

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?

• Thin in the first sense is usually called asymptotic density zero. – Joel David Hamkins Feb 15 at 8:46
• 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. – Joel David Hamkins Feb 15 at 10:21
• @JoelDavidHamkins: Sorry, I missed. I deleted my comment. – GH from MO Feb 15 at 14:48
• @JoelDavidHamkins - for the only reason that $n+1 \neq 0$, for all $n\in\omega$. But yes, it is not elegant – Dominic van der Zypen Feb 15 at 17:23

## 1 Answer

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.