Month: January 2017

Ultrafilters VIII: Chromatic compactness

Today, we return to the world of ultrafilters and look at a really nice application to a theorem of De Bruijn and Erdős. If you need to refresh your memory about ultrafilters, check out the first post of the series.

The application we have in mind is in the area of graph theory, so our first item of business is to introduce the basic ideas of graphs and their chromatic numbers.

Graphs are some of the simplest structures in mathematics. A graph is simply a set of vertices (often depicted visually as dots or circles) and a set of edges (often depicted visually as lines or arcs connecting two vertices). For example:

graph1
A graph.

We will make the standard assumptions that, in a graph, each edge connects exactly two vertices (in particular, there are no edges between a vertex and itself) and each pair of vertices has at most one edge connecting them. Recall that, for a set X, [X]^2 denotes the collection of subsets of X of size 2. A graph G will often be represented by a pair (V,E), where V is the set of vertices and E \subseteq [V]^2 is the set of edges, i.e. for all u,v \in V, we have \{u,v\} \in E if and only if there is an edge connecting u and v.

If G = (V,E) is a graph, then a subgraph of G is simply a subset V' of V together with a subset E' of E consisting only of edges that meet vertices in V' (i.e., E' \subseteq [V']^2). A subgraph is easily seen to be a graph itself.

One of the central notions in graph theory is that of a chromatic vertex coloring. Suppose that G = (V,E) is a graph and C is a set. Then a function f:V \rightarrow C is a chromatic coloring of G into C if, for all edges \{u,v\} \in E, we have f(u) \neq f(v). The elements of C are often literally thought of as colors, so a chromatic coloring can be thought of as a way of coloring the vertices of a graph in such a way that any two vertices connected by an edge receive different colors. Here is a chromatic coloring of our example graph into the color set C = \{\mathrm{red}, \mathrm{blue}, \mathrm{green}\}:

graph2
A chromatic coloring

If G is a graph, then the chromatic number of G, denoted \chi(G), is the size of the smallest set C for which there exists a chromatic coloring of G into C. Suppose now that G is our example graph from above. We exhibited a chromatic coloring of G using 3 colors, so we certainly know that \chi(G) \leq 3. It is not hard to show (Exercise: check this!) that it is impossible to construct a chromatic coloring of G using only 2 colors. Therefore, we obtain the equality \chi(G) = 3.

The example graph we have considered is finite, but the definitions we have given apply just as well to graphs with infinitely many vertices. One infinite graph of particular interest is the unit distance graph on the plane. The vertices in this graph are points on the real plane (i.e. ordered pairs (x,y) of real numbers), and two vertices are connected by an edge if and only if their distance in the plane is exactly one.

The question of the chromatic number of the unit distance graph on the plane is particularly interesting. The cover image to this post illustrates a chromatic coloring of the graph using 7 colors. Moreover, one can show (Challenge Exercise: do this!) that it is impossible to have a chromatic coloring of this graph using 3 colors. Therefore, we know that the chromatic number of the unit distance graph on the plane is between 4 and 7. As of today, though, nothing more is known!

A beautiful theorem about chromatic numbers of infinite graphs was proven by De Bruijn and Erdős in 1951. It is a sort of compactness theorem which states that, if the chromatic number of every finite subgraph of a given graph is bounded by a single natural number, then the chromatic number of the entire graph is bounded by the same natural number. This allows one to reduce questions about possibly very large graphs, such as the unit distance graph on the plane, to questions about finite graphs, which are often more tractable. The De Bruijn-Erdős theorem has many proofs; we give here one making nice use of an ultrafilter.

Theorem (De Bruijn-Erdős): Suppose G = (V,E) is a graph, d is a natural number, and, for every finite subgraph H of G, \chi(H) \leq d. Then \chi(G) \leq d.

Proof: Let X = \{W \subseteq V \mid W \mbox{ is finite}\} (i.e., X is the collection of all finite subsets of V). For each W \in X, let X_W = \{U \in X \mid W \subseteq U\}, and let \mathcal{F} be the set of all Y \subseteq X such that, for some W \in X, X_W \subseteq Y.

Claim: \mathcal{F} is a filter on X.

Proof: The only slightly non-trivial condition to verify is that \mathcal{F} is closed under intersections. To check this, fix Y, Z \in \mathcal{F}. By the definition of \mathcal{F}, there are W_Y, W_Z \in X such that X_{W_Y} \subseteq Y and X_{W_Z} \subseteq Z. But X_{W_Y} \cap X_{W_Z} = X_{W_Y \cup W_Z} (Exercise: check this!), so we have:

X_{W_Y \cup W_Z} = X_{W_Y} \cap X_{W_Z} \subseteq Y \cap Z,

so, again by the definition of \mathcal{F}, we have Y \cap Z \in \mathcal{F}, as desired. This finishes the proof of the claim.

Since \mathcal{F} is a filter, an application of the axiom of choice (or its equivalent alternative formulation, Zorn’s Lemma) allows us to find an ultrafilter \mathcal{G} on X such that \mathcal{F} \subseteq \mathcal{G}.

By our assumptions about our graph G, we know that, for every W \in X, we can find a chromatic coloring f_W:W \rightarrow \{0, 1, \ldots, d-1\}, i.e. a function f_W:W \rightarrow d such that, for all v,w \in W, if \{v,w\} \in E, then f_W(v) \neq f_W(w). For w \in V and i < d, let

X_{w,i} = \{W \in X \mid w \in W \mbox{ and } f_W(w) = i\}.

Notice that X_{w,0} \cup X_{w,1} \cup \ldots \cup X_{w, d-1} = X_{\{w\}} \in \mathcal{G}. Therefore, as \mathcal{G} is an ultrafilter, there is a unique i_w < d such that X_{w,i_w} \in \mathcal{G}. Define a function f:V \rightarrow d by letting f(w) = i_w for all w \in V. We will be done if we can prove the following claim.

Claim: f is a chromatic coloring, i.e., for all \{u,v\} \in E, we have f(u) \neq f(v).

Proof of Claim: Fix \{u,v\} \in E. Since \mathcal{G} is an ultrafilter and X_{u,i_u}, X_{v,i_v} \in \mathcal{G}, we can find a set W in X_{u,i_u} \cap X_{v,i_v}. Now we must have u,v \in W, f_W(u) = i_u, and f_W(v) = i_v. Since f_W is a chromatic coloring and \{u,v\} \in E, it follows that i_u \neq i_v and hence f(u) \neq f(v). This finishes the proof of the Claim and hence the proof of the Theorem.

A natural question is whether a similar theorem is true when the finite number d in the statement of the De Bruijn-Erdős theorem is replaced by an infinite cardinal. Some recent work in set theory (in which I have been lucky enough to have played a very small role) indicates that, in general, the answer is a resounding no. In particular, under some relatively minor assumptions which I won’t go into here (including the non-existence of some moderately large cardinals, such as weakly compact cardinals), there are arbitrarily large cardinals \kappa for which there is a graph G of size \kappa satisfying the following two properties, which, in tandem, yield a striking instance of incompactness:

  • for every subgraph H of G of size less than \kappa, \chi(H) \leq \aleph_0, i.e. there is a chromatic coloring of H into the natural numbers;
  • \chi(G) = \kappa.

On the other hand, the existence of large cardinals does yield infinitary versions of the De Bruijn-Erdős theorem, such as the following:

Theorem: Suppose \kappa is a strongly compact cardinal, G is a graph, \mu < \kappa, and, for all subgraphs H of G of size less than \kappa, we have \chi(H) \leq \mu. Then \chi(G) \leq \mu.

Posted on by Chris Lambie-Hanson 3