Skip to main content
Became Hot Network Question
added 82 characters in body
Source Link
Capublanca
  • 943
  • 6
  • 14

Let $D\subseteq\mathbb{N}^+$, and consider the graph $G_D$ with vertices set $\mathbb{N}$ and edges set $\{(x,y)\in\mathbb{N}\times\mathbb{N}\;s.t.\;|x-y|\in D\}$. I expect that if $D$ is dense enough in $\mathbb{N}^+$, then the chromatic number of $G_D$ is large. More precisely, I'm interestedAs Wojowu pointed out in the comments, positive density does not guarantee infinite chromatic number. Hence, one can ask the following question:

if $D$ has positive density (say, e.g., lower asymptotic density) one in $\mathbb{N}^+$, is it true that the chromatic number of $G_D$ is infinite?

Thank you for any suggestion.

Let $D\subseteq\mathbb{N}^+$, and consider the graph $G_D$ with vertices set $\mathbb{N}$ and edges set $\{(x,y)\in\mathbb{N}\times\mathbb{N}\;s.t.\;|x-y|\in D\}$. I expect that if $D$ is dense enough in $\mathbb{N}^+$, then the chromatic number of $G_D$ is large. More precisely, I'm interested in the following question:

if $D$ has positive density (say, e.g., lower asymptotic density) in $\mathbb{N}^+$, is it true that the chromatic number of $G_D$ is infinite?

Thank you for any suggestion.

Let $D\subseteq\mathbb{N}^+$, and consider the graph $G_D$ with vertices set $\mathbb{N}$ and edges set $\{(x,y)\in\mathbb{N}\times\mathbb{N}\;s.t.\;|x-y|\in D\}$. I expect that if $D$ is dense enough in $\mathbb{N}^+$, then the chromatic number of $G_D$ is large. As Wojowu pointed out in the comments, positive density does not guarantee infinite chromatic number. Hence, one can ask the following question:

if $D$ has density (say, e.g., lower asymptotic density) one in $\mathbb{N}^+$, is it true that the chromatic number of $G_D$ is infinite?

Thank you for any suggestion.

Source Link
Capublanca
  • 943
  • 6
  • 14

Chromatic number of distance graphs over the integers

Let $D\subseteq\mathbb{N}^+$, and consider the graph $G_D$ with vertices set $\mathbb{N}$ and edges set $\{(x,y)\in\mathbb{N}\times\mathbb{N}\;s.t.\;|x-y|\in D\}$. I expect that if $D$ is dense enough in $\mathbb{N}^+$, then the chromatic number of $G_D$ is large. More precisely, I'm interested in the following question:

if $D$ has positive density (say, e.g., lower asymptotic density) in $\mathbb{N}^+$, is it true that the chromatic number of $G_D$ is infinite?

Thank you for any suggestion.