Home Math Teaching About Me

≪ Seminars and Talks

Introduction to Descriptive Combinatorics

Speaker: Anton Bernshteyn
Date of Talk: November 25, 2024

For the purposes of this talk, “combinatorics” really means “graph theory”, and the “descriptive” is taken in the sense of “descriptive set theory”.

1. Borel Graphs

A (countable) boolean circuit is a directed connected acyclic graph whose roots (vertices with no predecessors) are binary “inputs” \(x_0, x_1,\\ldots, \in \left\lbrace 0,1 \right\rbrace\), whose other vertices are \(\land,\lor,\lnot\), and which contains no infinite chain of vertices.

Given an input \(\left\lbrace x_n \right\rbrace\in \left\lbrace 0,1 \right\rbrace ^{\mathbb{N}}\), one can “evaluate” a countable boolean circuit by following the graph and evaluating the inner vertices as you go.

What an unhinged definition…and this is just descriptive set theory.

For some reason these are the primary objects of study in descriptive combinatorics. I have learned something today!

2. The Hypercube

Define the Borel graph \(\mathbb{H}\) by having \(V = \left\lbrace 0,1 \right\rbrace ^{\mathbb{N}}\). Two vertices are joined by an edge if they differ at exactly one coordinate. Since \(E\) can be computed by a countable boolean circuit (very, very efficiently), it’s also Borel.

\(\mathbb{H}\) is very far from connected: two vertices are connected by a path if and only if they differ at finitely many coordinates, so in fact there are uncountably many connected components. But there are also no odd cycles in \(\mathbb{H}\). If we think of a path as a sequence of bit-flips, any cycle must perform an even number of flips if it starts and ends at the same point. So \(\mathbb{H}\) is a bipartite graph, and its vertices can be coloured into two colours so that no two vertices of the same colour are joined by an edge.

However, no such colouring is a Borel subset of \(V\)! In fact, there is no countable “Borel colouring” of the vertices of \(\mathbb{H} \). This is kind of weird to think about…but there’s a measure-theoretic proof! It’s a lot like the proof that the Vitali set is unmeasurable — each of the countably many pieces of the partition would have to have measure zero (with the right measure, etc.).

I think it’s fun to see how this field of math interprets the idea of “Borel sets”, “measurable sets”, “Lebesgue density theorem”, etc.

Actually, one can identify \(\mathbb{H} \) with the interval \(\left[ 0,1 \right]\) by sending a real number \(a\in \left[ 0,1 \right]\) to its binary decimal expansion. The \(\sigma \)-algebra on the vertices \(V = \left\lbrace 0,1 \right\rbrace ^{\mathbb{N}}\) is that generated by cylindrical sets; on the \(\left[ 0,1 \right]\)-side, it’s the \(\sigma \)-algebra generated by intervals of the form \(\left[ k2 ^{-n}, (k+1) 2 ^{-n} \right)\). Borel colourings of \(V\) would correspond to disjoint Borel partitions of the interval wherein no pair of points in the same subset differ by a negative power of \(2\). This is a very Vitali-esque construction after all…

3. A fun open problem

Let \(G\) be a Borel acyclic graph with maximal degree \(d\). The chromatic number \(\chi (G)\) is the smallest natural number such that \(V\) can be coloured by \(\chi (G) \) colours so that no two vertices of the same colour share an edge. Likewise, the Borel chromatic number \(\chi _B(G)\) is the smallest Borel colouring, and \(\chi _M(G)\) is the smallest measurable colouring.

It turns out for all \(d \geq 1\), \(\chi (G) = 2\); for all \(d\), we have \(\chi_B (G) = d + 1\). Seems reasonable.

When \(d = 1\), \(\chi _M (G) = 2\); for \(d = 2\), \(\chi _M (G) = 3\); and for \(d = 3\), \(\chi _M (G) = 3\). What? Nobody knows any of the other measurable chromatic numbers, though we do know that \(\chi _M(G) \sim \frac{d}{\log d }\)! This seems completely unreasonable but that’s a really crazy result.

I have no idea why any of this should be true but that’s a fantastic hook for descriptive combinatorics.