Borel chromatic numbers and a result of Palamourdas

Let’s say you have a graph $G=(V,E)$.  Here we don’t want loops or multiple edges.  You may or may not want the edges to be directed.  It doesn’t really matter for this post, which will be about the chromatic number of $G$.  Recall that a coloring of $G$ is a map $c:V\rightarrow X$ such that if $(v_0,v_1)\in E$ then $c(v_0)\neq c(v_1)$.  The minimum cardinality of a space $X$ such that $c:V\rightarrow X$ is a coloring is called the chromatic number of $G$ and generally denoted $\chi(G)$.  It’s a well-studied notion.

You could put restrictions on the sort of colorings you’ll allow.  In descriptive set theory, we like to talk about colorings with some sort of “niceness” restrictions, like measurability, Baire measurability (meaning the inverse image of every open set has the property of Baire), or just Borelness.  Of course this sort of thing only makes sense if $V$ and $X$ have the appropriate structure (i.e. are measure spaces, Baire topological spaces, or standard Borel spaces).  You’d also want the edge relation to be sufficiently nice (say Borel), since otherwise trivial issues can arise.  So assume these things as necessary.  Then you can define the measurable (Baire measurable, Borel) chromatic number as above.  We’ll be concerned mainly with the Borel chromatic number here, which we write $\chi_B(G)$.

Theorem (Kechris, Solecki, Todorcevic): There is an acyclic graph $G$ (so $\chi(G)=2$) with $\chi_B(G)>\aleph_0$.

A couple of remarks.  First, they actually show that the Baire measurable chromatic number of this $G$ is $>\aleph_0$, and since every Borel map is Baire measurable, you get the above result.  They also mention that Thomas had shown earlier that there is a bipartite (but not acyclic) graph with $\chi_B(G)>\aleph_0$ (this time using measure), so the difference between the two types of chromatic number wasn’t unnoticed before.

Think about how you would 2-color an acyclic graph.  (Let’s say the colors are $R$ and $B$.) You would pick a vertex, color it $R$, color its neighbors $B$, color their neighbors $R$, etc.  (Of course you would have to do this in each connected component of $G$.)  The acyclicity of $G$ ensures that this is a coloring.  But notice that the first thing you have to do is make a choice of vertex, and when there are infinitely many connected components of $G$, this would seem to require the Axiom of Choice.  The above theorem more or less confirms this suspicion: you can’t do this in a Borel way, which to descriptive set theorists means you have to use the Axiom of Choice.  (Technically, this is perhaps a bit strong, but not much.  At the very least, we know it doesn’t increase the consistency strength of ZF+dependent choice to also assume that every set of reals is Baire measurable, so if you can’t do something in a Baire measurable way, you really do need Choice!)

So there’s one reason to care about these restricted colorings: it gives you insight into when the Axiom of Choice is necessary.  Contrary to popular belief, however, logicians aren’t particularly obsessed with the Axiom of Choice.  Instead, we think of “Borel” as a synonym for “explicit” (there are reasons related to definability that provide some justification for this), and everybody is interested when things can be done explicitly, right?  Another reason (which would take me pretty far on a tangent to explain fully) is that these chromatic numbers are an area where we can actually tease apart distinctions between the measurable, Baire measurable, and Borel contexts, and this actually turns out to be somewhat tricky in general.

At this point, it is probably reasonable to ask when one can do things in a Borel way.  Here’s an example.

Theorem (KST): If there is a $k\in\mathbb{N}$ such that every vertex in $G$ has degree $\leq k$, then $\chi_B(G)\leq k+1$.

This is really the best you could do even for $\chi(G)$, since it covers the case of complete graphs on $k+1$ vertices and disjoint unions thereof.  The result is not obvious, but not too hard.  Some basic descriptive set theory results allow one to prove that such a graph has $\chi_B(G)\leq\aleph_0$.  Then you can do the standard algorithm for this sort of thing, by which I mean the following:

We know we have a Borel $\aleph_0$-coloring of $G$, say with colors $c_0,c_1,c_2,\ldots$.  We want to find a Borel $(k+1)$-coloring, say with colors $0,1,\ldots,k$.  We begin by assigning all of the vertices colored $c_0$ the color $0$.  Then we look at the vertices colored $c_1$ and assign them the least color possible, so they will be colored $0$ unless they have a neighbor which was initially colored $c_0$.  And so on and so forth inductively.  Since each vertex has $k$ neighbors, there will always be a color from $0,\ldots,k$ available for any vertex you look at in this process.  Thus after completing the induction, $G$ has been $(k+1)$-colored.

By the way, this is Borel.  Technically you want to appeal to the Feldman-Moore theorem to ensure that quantifying over a vertex’s neighbors isn’t causing you problems (there are only finitely many, it shouldn’t, right?), but you should just think, “That’s an explicit algorithm, so it must be Borel.”  Note the difference between this and the “algorithm” for coloring an acyclic graph.  There was something which wasn’t explicit, and that was where to start coloring.  That’s why Choice was necessary, to find a starting point.  But in this case, we have a starting point: using a coloring we already knew existed we had a set of vertices to begin our algorithm on, those that were initially colored $c_0$.  This is a common feature of arguments in Borel combinatorics (especially when the graphs are locally countable and so Feldman-Moore is available): if you can find a way to get started which is Borel, then often old proofs of coloring properties can be carried out in a Borel way.  We’ll see this idea put to use again in a minute.

Graphs generated by functions

Suppose we have a (let’s say finite) set of functions $\{f_1,\ldots,f_n\}$ such that each $f_i$ is a function from $X$ to $X$, where $X$ is a Polish space (or just a standard Borel space).  Then there is a natural way to define a (directed) graph $G_{\{f_1,\ldots ,f_n\}}$ with vertex set $X$:

$(x,y) \in G_{\{f_1,\ldots ,f_n\}}$ iff there is some $f_i$ such that $f_i(x)=y$.

This is something like the Schreier graph (as the term is used in Definition 2 here) associated to the semigroup generated by $\{f_1,\ldots,f_n\}$, acting in the obvious way, though I’ve only seen the term “Schreier graph” used in the context of group actions, so there may be a different term when we’ve just got a semigroup action.  If the $f_i$ are all Borel, then the edge relation of $G_{\{f_1,\ldots ,f_n\}}$ is Borel as well, so we’re in our desired context.  We’ll go ahead and call these graphs “Schreier graphs” (in quotes, just to be safe).

Kechris, Solecki, and Todorcevic proved a number of results about “Schreier graphs”.  The main one of interest here is the following.

Theorem (KST): If $F\colon X\to X$ is Borel, then $\chi_B(G_{\{F\}})\in\{1,2,3,\aleph_0\}$.  Each value is possible.

It’s a nice proof, but I won’t get into it here.  Note that $\chi(G_{\{F\}})\leq 3$ (you can make an odd cycle this way, so $3$ colors may be necessary), so the theorem essentially says that while sure, in the Borel context you may need infinitely many colors to color such a graph, if you only need finitely many, then the bound you get for number of colors possibly needed is the same as in the non-Borel context!

What if you use more functions?  The above result immediately gives that $\chi_B(G_{\{f_1,\ldots,f_n\}})\leq 3^n$ whenever it is finite (just think of $G_{\{f_1,\ldots,f_n\}}$ as $n$ $G_{\{F\}}$s with the same vertex set).  On the other hand, one can show that $\chi(G_{\{f_1,\ldots,f_n\}})\leq 2n+1$.  This raises the question: can this be matched in the Borel case?

A result of Palamourdas

In 2012 at UCLA, Palamourdas wrote a thesis attacking this problem.  As far as I know, his results were not published in any journal, though the thesis is available online.  I’m going to discuss the following result from his thesis (Theorem 3.1, to be precise).

Theorem (Palamourdas): Suppose $\{f_1,\ldots,f_n\}$ are Borel and commute (i.e. $f_i(f_j(x))=f_j(f_i(x))$ for all $1\leq i,j\leq n$.  If $\chi_B(G_{\{f_1,\ldots,f_n\}})<\aleph_0$, then $\chi_B(G_{\{f_1,\ldots,f_n\}})\leq 2n+1$.

So in the case that $\{f_1,\ldots,f_n\}$ generate a commutative semigroup, we do get the classical bound for the chromatic number of $G_{\{f_1,\ldots,f_n\}}$ (assuming it’s finite).  What follows is a proof of this.  The main ideas are exactly those from Palamourdas’ thesis, but teased apart a bit differently than he presented them.  It was an interesting exercise doing this, and I thought I might share it on the blog.

Throughout, we’ll refer to the semigroup generated by $\{f_1,\ldots,f_n\}$ as $S$, and think of it as acting on the vertex set $X$ in the obvious way (on the left).  We’ll also just refer to our graph simply as $G$.  We note that given a vertex $x\in X$, its $m$-neighborhood in $G$ can be defined as

$\{ y\in X \mid \exists w\in S (|w|\leq m \wedge (w\cdot y = x \vee w\cdot x = y)) \}$

(here $|w|$ refers to the word length of $w$).

Note that if $S$ is in fact a group (abelian or otherwise), then every vertex in $G$ has degree $\leq 2n$ (the inverses of $\{f_1,\ldots,f_n\}$ may not be included in that set, whence the factor of $2$), so we get our desired upper bound on its Borel chromatic number.  Thus this result is only interesting if $S$ is not a group.

By assumption, we know there is a coloring $c\colon X\to k$ for some $k\in\mathbb{N}$.  As in our last example, we will alter this coloring and eventually come up with a new coloring using $\leq 2n+1$ colors.  I’m going to split this into two lemmas.

Lemma 1: If $w\in S$ is central, then the map $d\colon X\to k$ defined by $d(x)=c(w\cdot x)$ is also a coloring.

Proof: Suppose that $(x,y)\in G$, so there is some $f_i$ such that $f_i\cdot x=y$.  Then

$d(y) = d(f_i\cdot x) \\ = c(w f_i \cdot x) \\ = c(f_i w \cdot x) \\ \neq c(w\cdot x) \\ = d(x). \,\, \Box$

This is notable mainly in light of the next lemma.

Lemma 2: Fix a $w\in S$ (not necessarily central) and define $d$ as in Lemma 1.  Suppose there are $v, w_v\in S$ such that $w_v v = w$, and define $Y_{v,x} = \{ y \mid v \cdot y = x\}$.  Then $d(Y_{v,x})$ is a singleton.

Proof: Suppose $v\cdot y = x$.  Then

$d(y) = c(w\cdot y) \\ =c(w_v v\cdot y) \\ =c(w_v\cdot x). \,\, \Box$

This lets us reason about the colors of the neighbors of a given vertex $x$!  We know that there are at most $n$ colors represented among the vertices $f_i\cdot x$.  If we have a $w$ which can be written as $w_{f_i} f_i$ for each $i$ and we use $d$ to assign colors to the vertices, then we also know that the number of colors used on $\cup_i Y_{f_i,x}$ is at most $n$ as well.  (We couldn’t necessarily say this about $c$.)  But this is true for any vertex $x$, so it seems that if we start with $d$ and go through and recolor the vertices somehow, we should only need to use $2n+1$ colors, since the neighbors of any vertex can only have used up at most $2n$ colors as we go through the process.  Of course we need to be a little more precise to be sure we can do this in a Borel way.

At this point, we’ve basically got it.  We’re in a commutative semigroup, so we can use any $w\in S$ to define $d$ and still get a $k$-coloring of $G$.  Again by commutativity we can rearrange the element $f_1 f_2\ldots f_n$ so that any of the $f_i$ appears at the end, so that seems like a good candidate for our $w$.  We do things like we did with bounded degree graphs and start by keeping the things with color $0$ as color $0$, then move through giving vertices the least available color.  (This is where it’s important that $d$ is actually a coloring; what we get out of this process is only guaranteed to be a coloring if we start with one.)  There is one catch though.

Think about what happens, say, when you look to recolor a vertex $x$ that $d$ has given the color $2$.  If none of its neighbors have color $0$, then you give it color $0$.  But to know if this happened, you need to know if its neighbors had neighbors with color $0$, since they may have been initially assigned color $1$ by $d$ but then changed to color $0$.  So it’s not enough to know the $1$-neighborhood of $x$, you also need to know its $2$-neighborhood.  In general, since we’ll be working our way through $k$ many colors, we need to know the $k$-neighborhood of $x$.  This isn’t an issue in this case though; just let $w=(f_1\ldots f_n)^k$.  Clearly every word in $S$ with length $\leq k$ can be written as the rightmost portion of a word equal to $w$.

A few lingering thoughts

When split into the two lemmas above, it’s easy to see that the argument may apply to some $\{f_1,\ldots,f_n\}$ which generate a non-commutative semigroup $S$ as well.  Given a $k$-coloring of the “Schreier graph”, you would need a central element of the semigroup $S$ which could also be written as $w_v v$ for any $v\in S$ of length $\leq k$.  I don’t think this describes a particularly nice class of semigroups though, so saying “commutative semigroup” probably gets all of the interesting cases.  Still, I might be wrong!  I thought perhaps growth conditions on $S$ might help (since then pigeonhole arguments would give elements of $S$ which can be written as $w_v v$ for many different $v$s), but this doesn’t seem to be enough.  Simply having a nontrivial center also seems to not be enough either.  But maybe I’m overlooking a neat argument.

Also, the similarity to the bounded-degree case also strikes me as worth looking at a little more.  I tried for a little bit to cast the argument above as finding some sort of auxiliary graph which had degree $\leq 2n$ at each vertex whose coloring would tell us how to color the initial graph, but I couldn’t figure out how and so I set that aside.  If that approach did work it might give the result for some other non-abelian “Schreier graphs”.

Finally, I should mention that Palamourdas was able to lower the upper bound on $\chi_B(G_{\{f_1,\ldots,f_n\}})$ (assuming it’s finite) to something $O(n^2)$ in the general case through a different argument.  I won’t go through it here, but it’s very nice.  Maybe in another post?  We’ll see.