10. χ(G_D) countable?

problem

Let $D⊆(0,∞)$ and define a graph $G_D$ with vertex set $ℝ$ and edge set $\{\{x,y\}:\lvert x-y\rvert∈D\}$. Show that $χ_B(G_D)≤ℵ₀$ if and only if $0$ is not in the closure of $D$.

• [⟸] Suppose $0∉\bar D$. We wish to show that $χ_B(G_D)≤ℵ₀$.

  proof

  $0∉\bar D$ means that $ϵ≔\inf D>0$. Then define the coloring $c\colon ℝ→ℤ$ by $c(x)=⌊x/ϵ⌋$.

  Suppose $x,y$ are joined by an edge in $G_D$; that is, $\lvert x-y\rvert∈D$. Then $\lvert x-y\rvert>ϵ$, so $x/ϵ$ and $y/ϵ$ are at least distance $1$ apart, so $c(x)≠c(y)$.

• [⟸] Suppose $χ_B(G_D)≤ℵ₀$. We wish to show that $0∉\bar D$.

  lemma

  If $0∈\bar D$, then in any Borel proper coloring of $G_D$ the set of points assigned any given color is meager.

  proof

  Fix $S$ any set of points with the same coloring. Suppose $S$ is not meager. Since it is Borel and therefore trivially Baire-measurable, so by the Baire alternative there exists an open interval $U=(x-ϵ,x+ϵ)$ so that $U∖S$ is meager. By the assumption that $0∈\bar D$, there exists $δ∈D$ satisfying $0<δ<ϵ$.

  Consider $S'=S∩(S+δ)$, and observe that

  $$(x,x+ϵ) ∖ S' = \underbrace{[(x,x+ϵ) ∖ S]}_{⊆U∖S} ∪ \underbrace{[(x,x+ϵ) ∖ (S+δ)]}_{⊆(U+δ)∖(S+δ)}.$$

  Both sets in the union above are contained in translates of $U∖S$, so $(x,x+ϵ)∖S'$ is meager. Then $S'$ is comeager in $(x,x+ϵ)$ and therefore nonempty. That is, there exists $x∈S'=S∩(S+δ)$. Then $x,x-δ∈S$, so they have the same color.

  At the same time $δ∈D$ implies $\{x,x-δ\}$ is an edge in $G_D$, so $x$ and $x-d$ must have different colors, a contradiction.

  claim

  $0∉\bar D$.

  proof

  Fix a countable Borel proper coloring $c\colon ℝ→ℕ$. Suppose towards a contradiction that $0∈\bar D$. Then by the lemma, for each $n∈ℕ$ the set $S_n≔c⁻¹(\{n\})$ of points with color $n$ is meager.

  Then

  $$ℝ = ⋃_{n∈ℕ} c⁻¹(\{n\})$$

  is a countable union of meager sets and therefore also meager, a contradiction.