2
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ Thin in the first sense is usually called asymptotic density zero. $\endgroup$ Commented Feb 15, 2021 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$ Commented Feb 15, 2021 at 10:21
  • 1
    $\begingroup$ @JoelDavidHamkins: Sorry, I missed. I deleted my comment. $\endgroup$
    – GH from MO
    Commented Feb 15, 2021 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$ Commented Feb 15, 2021 at 17:23

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .