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$?

Improve this question
$\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$
    – Joel David Hamkins
    Commented May 21, 2015 at 12:04
  • $\begingroup$ Joel, I think this question is worthwhile to put it as a MO question! $\endgroup$
    – Dominic van der Zypen
    Commented May 21, 2015 at 12:06
  • $\begingroup$ Please go ahead! $\endgroup$
    – Joel David Hamkins
    Commented 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 ♦
    Commented May 26, 2015 at 7:29
  • $\begingroup$ Good point, have modified the post accordingly. $\endgroup$
    – Dominic van der Zypen
    Commented May 26, 2015 at 8:31

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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