Tag Archives: Borel chromatic number

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).

Why bother?  Maybe it’s best to start with a striking fact.

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 vs), 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.

Leave a comment

Filed under Uncategorized