This article by Todorčević and Vidnyánszky answers a long-standing question from descriptive combinatorics. The well-known $\mathbb {G}_0$ dichotomy provides a canonical obstruction to Borel graphs having countable Borel chromatic number. However, the analogous question of whether an obstruction exists to Borel graphs having finite Borel chromatic number remained open for many years. Todorčević and Vidnyánszky resolve this question firmly in the negative. The arguments used in their proof rely on a variety of tools, including complexity arguments and results from effective descriptive set theory.

A Borel graph on a Polish space X is a symmetric, irreflexive subset of $X^2$ . Many properties from finite graph theory have been studied in a Borel or descriptive context in recent years. One such property is the Borel chromatic number, first introduced by Kechris, Solecki, and Todorčević in Borel chromatic numbers, ${\boldsymbol {Advances \ in \ Mathematics}}$ , vol. 141, no. 1 (1999), pp. 1–44. Given a Borel graph G on a Polish space X, as well as a Polish space Y, a Borel Y-coloring is a Borel map $c: X \to Y$ such that $(x, x') \in G$ implies $c(x) \neq c(x')$ . The Borel chromatic number $\chi _B(G)$ is the least cardinality of a Polish space Y for which a Borel Y-coloring exists. Given Borel graphs $G, H$ on Polish spaces $X, Y$ , respectively, a Borel homomorphism from G to H is a Borel function $\varphi : X \to Y$ such that $(x, x') \in G$ implies $(\varphi (x), \varphi (x')) \in H$ . We say that $\varphi $ is a Borel isomorphism from G to H if $\varphi : X \to Y$ is a Borel bijection and $(x, x') \in G$ iff $(\varphi (x), \varphi (x')) \in H$ . In their foundational article, Kechris, Solecki, and Todorčević proved the $\mathbb {G}_0$ dichotomy: there is a Borel graph $\mathbb {G}_0$ such that a Borel graph G has uncountable Borel chromatic number iff there is a Borel homomorphism from $\mathbb {G}_0$ to G. This result is significant not only in descriptive combinatorics but also in descriptive set theory in general. For example, in The graph-theoretic approach to descriptive set theory, ${\boldsymbol {Bulletin \ of \ Symbolic \ Logic}}$ , vol. 18, no. 4 (2012), pp. 554–575, Miller used the $\mathbb {G}_0$ dichotomy to provide alternate proofs of several well-known dichotomy theorems.

In contrast to the $\mathbb {G}_0$ dichotomy, for many years it was unknown whether an analogous dichotomy result holds for Borel graphs of infinite Borel chromatic number. The $\mathbb {G}_0$ dichotomy identifies a single obstruction to a Borel graph having a countable Borel chromatic number. We can instead ask for an obstruction to a Borel graph having a finite Borel chromatic number. Kechris and Marks asked the following question in Descriptive graph combinatorics, preprint (2020): is there a countable sequence of Borel graphs $G_n$ with finite but unbounded Borel chromatic numbers such that any Borel graph with infinite Borel chromatic number admits a Borel homomorphism from every $G_n$ ? Such a sequence is called a countable basis. We can also ask the weaker question of whether there is a countable basis for some interesting smaller class of Borel graphs: given some collection $\mathcal {B}$ of Borel graphs, is there a countable sequence of Borel graphs $G_n$ as above such that every $G \in \mathcal {B}$ has infinite Borel chromatic number iff it admits a Borel homomorphism from every $G_n$ ?

One important graph with chromatic number $\aleph _0$ is the shift graph $\mathcal {G}_S$ . On the space $[{\mathbb {N}}]^{\mathbb {N}}$ of infinite subsets of natural numbers, the shift function S is defined by $S(x) := x \setminus \{{\min (x)}\}$ . The graph $\mathcal {G}_S$ is defined by $(x, y) \in \mathcal {G}_S$ iff $S(x) = y$ or $S(y) = x$ . For a subset C of $[{\mathbb {N}}]^{\mathbb {N}}$ , the restriction of $\mathcal {G}_S$ to C is the Borel graph $\mathcal {G}_S {\mathord {\upharpoonright }} C$ on C given by $\mathcal {G}_S {\mathord {\upharpoonright }} C := \mathcal {G}_S \cap (C \times C)$ . The shift graph was a prominent candidate for analogs to the $\mathbb {G}_0$ dichotomy, first for the class of all Borel graphs and later for smaller classes of graphs, such as graphs induced by Borel functions. However, these hopes were thwarted by several antibasis results due to Conley and Miller, An antibasis result for graphs of infinite Borel chromatic number, ${\boldsymbol {Proceedings \ of \ the \ American \ Mathematical \ Society}}$ , vol. 142, no. 6 (2014), pp. 2123–2133; Di Prisco and Todorčević, Basis problems for Borel graphs, ${\boldsymbol {Zbornik \ Radova}}$ , vol. 17, no. 25 (2015), pp. 33–51; and Pequignot, Finite versus infinite: an insufficient shift, ${\boldsymbol {Advances \ in \ Mathematics}}$ , vol. 320 (2017), pp. 244–249.

In the article under review, Todorčević and Vidnyánszky use complexity arguments to prove their antibasis theorem. This is not the first such approach to this problem—Pequignot used complexities to deduce antibasis results in the article mentioned above—but is quite interesting. Todorčević and Vidnyánszky begin by proving a general theorem that determines the complexity of a relevant set of graphs. A subset A of a Polish space X is $\boldsymbol {\Sigma }^1_2$ -hard if there is a Borel reduction from every $\boldsymbol {\Sigma }^1_2$ set to A. We say that A is $\boldsymbol {\Sigma }^1_2$ -complete if A is both $\boldsymbol {\Sigma }^1_2$ and $\boldsymbol {\Sigma }^1_2$ -hard. Todorčević and Vidnyánszky show that the collection of closed sets $C \subseteq [{\mathbb {N}}]^{\mathbb {N}}$ such that $\chi _B(\mathcal {G}_S {\mathord {\upharpoonright }} C) < \aleph _0$ is $\boldsymbol {\Sigma }^1_2$ -complete. As a consequence, they conclude that there is no countable basis for graphs of infinite Borel chromatic number, or even for the collection of restrictions of the shift graph to closed subsets of $[{\mathbb {N}}]^{\mathbb {N}}$ . Todorčević and Vidnyánszky’s theorem is a strong antibasis result, definitively answering Kechris–Marks’ question and occluding the possibility of finding a single Borel graph that obstructs finite Borel chromatic numbers. In fact, their theorem implies that a more general type of basis cannot exist. A set $\mathcal {A}$ of Borel graphs is $\boldsymbol {\Sigma }^1_1$ -parametrizable if there are Polish spaces X and Y and a $\boldsymbol {\Sigma }^1_1$ set $H \subseteq X \times Y^2$ such that

1. 1. every $G \in \mathcal {A}$ is Borel isomorphic to $H_x = \{{(y, y') \in Y^2 \mid (x, y, y') \in H}\}$ for some $x \in X$ ; and

2. 2. the set $\{{x \in X \mid H_x \text { is Borel isomorphic to an element of } \mathcal {A}}\}$ is $\boldsymbol {\Sigma }^1_1$ .

Todorčević and Vidnyánszky’s theorem implies that there is no countable sequence of $\boldsymbol {\Sigma }^1_1$ -parametrizable sets $\mathcal {A}_n$ such that for every closed set $C \subseteq [{\mathbb {N}}]^{\mathbb {N}}$ , $\chi _B(\mathcal {G}_S {\mathord {\upharpoonright }} C) \geq \aleph _0$ iff there is an increasing sequence of $n_i$ and graphs $A_{n_i} \in \mathcal {A}_{n_i}$ such that $\mathcal {G}_S {\mathord {\upharpoonright }} C$ admits a Borel homomorphism from every $A_{n_i}$ . Along the way to their antibasis result, Todorčević and Vidnyánszky find a (uncountable) basis for restrictions of $\mathcal {G}_S$ to Borel subsets of $[{\mathbb {N}}]^{\mathbb {N}}$ : for any Borel $B \subseteq [{\mathbb {N}}]^{\mathbb {N}}$ , there exist a closed $C \subseteq [{\mathbb {N}}]^{\mathbb {N}}$ and a continuous injection $\psi : C \to B$ such that $\psi , \psi ^{-1}$ are shift-equivariant and $\chi _B(\mathcal {G}_S {\mathord {\upharpoonright }} B) = \chi _B(\mathcal {G}_S {\mathord {\upharpoonright }} C)$ .

The rough framework of their argument is as follows. Todorčević and Vidnyánszy first prove a general complexity theorem, which we state here in the specific setting of their antibasis result. Given a function $\Phi $ from $\boldsymbol {\Pi }^0_2$ subsets of $[{\mathbb {N}}]^{\mathbb {N}}$ to $\boldsymbol {\Pi }^1_1$ subsets of $[{\mathbb {N}}]^{\mathbb {N}}$ , they define a set $\mathcal {U}^\Phi $ of $\boldsymbol {\Pi }^0_2$ subsets of ${\mathbb {N}}^{\mathbb {N}} \times [{\mathbb {N}}]^{\mathbb {N}}$ . Their complexity result states that given certain conditions on $\Phi $ , $\mathcal {U}^\Phi $ is $\boldsymbol {\Sigma }^1_2$ -hard on $\boldsymbol {\Pi }^0_2$ , that is, there is a $\boldsymbol {\Pi }^0_2$ set $B \subseteq {\mathbb {N}}^{\mathbb {N}} \times {\mathbb {N}}^{\mathbb {N}} \times [{\mathbb {N}}]^{\mathbb {N}}$ such that $\{{x \in {\mathbb {N}}^{\mathbb {N}} \mid B_x \in \mathcal {U}^\Phi }\}$ is $\boldsymbol {\Sigma }^1_2$ -hard. Todorčević and Vidnyánszky apply this theorem to a function $\Phi $ that sends a $\boldsymbol {\Pi }^0_2$ set $A \subseteq [{\mathbb {N}}]^{\mathbb {N}}$ to a set of codes for the Borel 3-colorings of $\mathcal {G}_S {\mathord {\upharpoonright }} A$ . They then use the fact that $\mathcal {U}^\Phi $ is $\boldsymbol {\Sigma }^1_2$ -hard on $\boldsymbol {\Pi }^0_2$ to find a closed set $D \subseteq {\mathbb {N}}^{\mathbb {N}} \times [{\mathbb {N}}]^{\mathbb {N}}$ such that $\{{x \in {\mathbb {N}}^{\mathbb {N}} \mid \chi _B(\mathcal {G}_S {\mathord {\upharpoonright }} D_x) < \aleph _0}\}$ is $\boldsymbol {\Sigma }^1_2$ -hard. From here, a lemma inspired by work of Sabok, Complexity of Ramsey null sets, ${\boldsymbol {Advances \ in \ Mathematics}}$ , vol. 230, no. 3 (2012), pp. 1184–1195, implies that the collection of closed sets $C \subseteq [{\mathbb {N}}]^{\mathbb {N}}$ with $\chi _B(\mathcal {G}_S {\mathord {\upharpoonright }} C) < \aleph _0$ is $\boldsymbol {\Sigma }^1_2$ -hard, and a calculation shows that this set is in fact $\boldsymbol {\Sigma }^1_2$ -complete. To conclude the antibasis result, Todorčević and Vidnyánszky show that the existence of a countable basis, or of a sequence of $\boldsymbol {\Sigma }^1_1$ -parametrizable sets with the conditions described earlier, would imply that $\{{x \in {\mathbb {N}}^{\mathbb {N}} \mid \chi _B(\mathcal {G}_S {\mathord {\upharpoonright }} D_x) < \aleph _0}\}$ is $\boldsymbol {\Pi }^1_2$ , which is impossible since this set is $\boldsymbol {\Sigma }^1_2$ -hard.

The proofs in this article are technical. Several theorems from effective descriptive set theory are used, and the details of the codings and translations between sets are complicated. Helpfully, Todorčević and Vidnyánszky explicitly list the relevant effective descriptive set theory theorems in their preliminaries and provide general road maps before their most difficult proofs. The complexity arguments used to prove the antibasis result are worth reading, and some of the theorems could be read as a black box if necessary to aid understanding without losing the essentials.

Todorčević and Vidnyánszky’s article closes with several open problems of interest. Although the authors answer Kechris–Marks’ question in the negative, they point out that we might hope for other types of basis results: for example, is there a coanalytic graph H such that a Borel graph has infinite chromatic number iff it admits a Borel homomorphism from H? Todorčević and Vidnyánszky also connect their results to the Borel version of Hedetniemi’s conjecture, which asks whether $\chi _B(G \times G') = \min \{{\chi _B(G), \chi _B(G')}\}$ for all Borel graphs G and $G'$ . They provide a counterexample in the setting of $\Delta ^1_1$ -measurable colorings using a similar approach as their antibasis theorem and ask whether other ideas from antibasis results could be used to provide a counterexample to Hedetniemi’s conjecture in the Borel setting.