0
$\begingroup$

Let $V$ be the set of all functions $f:\mathbb{N}\to\mathbb{N}$. Let two distinct functions $f,g:\mathbb{N}\to\mathbb{N}$ form an edge if and only if they differ in exactly one input $n\in\mathbb{N}$.

Let $G=(V,E)$. Clearly, $G$ has cliques of cardinality $\aleph_0$. Is $\chi(G) = \aleph_0$?

$\endgroup$
6
  • $\begingroup$ This graph is Borel, and it would be interesting to ask whether there can be a Borel $\mathbb{N}$-coloring. If your edge relation connected points that differed finitely, then I believe there can be no Borel coloring, since it would give rise to a Borel selector on $E_0$, which is impossible. (For example, there can be no Borel coloring of the type that Chris describes.) But your relation is finer than $E_0$ and so a coloring needn't color the entire $E_0$ equivalence class differently. $\endgroup$ May 21, 2015 at 12:04
  • $\begingroup$ Joel, I think this question is worthwhile to put it as a MO question! $\endgroup$ May 21, 2015 at 12:06
  • $\begingroup$ Please go ahead! $\endgroup$ May 21, 2015 at 12:09
  • $\begingroup$ It may be just me, but your non-reflexive unordered graph would be much easier to grasp if it were defined as: vertices functions N->N, and there is an edge between f and g if they differ for exactly one input. Of course, you may be trying to emphasise the logical form of the set of edges in the language of some fragment of set theory... $\endgroup$
    – David Roberts
    May 26, 2015 at 7:29
  • $\begingroup$ Good point, have modified the post accordingly. $\endgroup$ May 26, 2015 at 8:31

1 Answer 1

9
$\begingroup$

Yes, $\chi(G) = \aleph_0$. To see this, define $f \sim g$ if $\{n : f(n) \not= g(n) \}$ is finite. $\sim$ is an equivalence relation, all equivalence classes of $\sim$ are countable, and $\{f,g\} \in E \Rightarrow f \sim g$. (In fact, the equivalence classes of $\sim$ are precisely the connected components of $G$.) Thus, we can color $G$ with countably many colors simply by ensuring that, if $f$ and $g$ are in the same equivalence class, they are given different colors.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.