Soon, you’ll have made it almost completely around the circle — meaning that you’ve assigned a color to all the nodes in your graph except for the ones that fall in a small, leftover segment. Say the last arc you colored was yellow. How do you color this final, smaller segment? You can’t use blue, because these nodes will connect to nodes in the original arc you colored blue. But you also can’t use yellow, because these nodes connect back to yellow ones from the previous arc.
You have to use a third color — say, green — to complete your coloring.
Still, the sets of blue, yellow and green nodes you end up with are all just pieces of the circle’s circumference, rather than the scatterings of points you ended up with when you used the axiom of choice. You can calculate the lengths of these sets. They’re measurable.
Descriptive set theorists therefore place the two-color version of the problem on the lowest shelf in their hierarchy (for unmeasurable sets), while the three-color problem goes on a much higher shelf of problems — ones where lots of notions of measure can be applied.
Bernshteyn spent his years in graduate school studying such coloring problems, shelving them one by one. Then, shortly after he finished his degree, he stumbled on a potential way to shelve them all at once — and to show that these problems have a much deeper and more mathematically relevant structure than anyone had realized.
Round by Round
From time to time, Bernshteyn enjoys going to computer science talks, where graphs are finite and represent networks of computers.
In 2019, one of those talks changed the course of his career. It was about “distributed algorithms” — sets of instructions that run simultaneously on multiple computers in a network to accomplish a task without a central coordinator.
Say you have a bunch of Wi-Fi routers in a building. Nearby routers can interfere with each other if they use the same communication frequency channel. So each router needs to choose a different channel from the ones used by its immediate neighbors.
Computer scientists can reframe this as a coloring problem on a graph: Represent each router as a node, and connect nearby ones with edges. Using just two colors (representing two different frequency channels), find a way to color each node so that no two connected nodes are the same color.
But there’s a catch: Nodes can only communicate with their immediate neighbors, using so-called local algorithms. First, each node runs the same algorithm and assigns itself a color. It then communicates with its neighbors to learn how other nodes are colored in a small region around it. Then it runs the algorithm again to decide whether to keep its color or switch it. It repeats this step until the whole network has a proper coloring.
Computer scientists want to know how many steps a given algorithm requires. For example, any local algorithm that can solve the router problem with only two colors must be incredibly inefficient, but it’s possible to find a very efficient local algorithm if you’re allowed to use three.
At the talk Bernshteyn was attending, the speaker discussed these thresholds for different kinds of problems. One of the thresholds, he realized, sounded a lot like a threshold that existed in the world of descriptive set theory — about the number of colors required to color certain infinite graphs in a measurable way.
To Bernshteyn, it felt like more than a coincidence. It wasn’t just that computer scientists are like librarians too, shelving problems based on how efficiently their algorithms work. It wasn’t just that these problems could also be written in terms of graphs and colorings.
Perhaps, he thought, the two bookshelves had more in common than that. Perhaps the connection between these two fields went much, much deeper.
Perhaps all the books, and their shelves, were identical, just written in different languages — and in need of a translator.
Opening the Door
Bernshteyn set out to make this connection explicit. He wanted to show that every efficient local algorithm can be turned into a Lebesgue-measurable way of coloring an infinite graph (that satisfies some additional important properties). That is, one of computer science’s most important shelves is equivalent to one of set theory’s most important shelves (high up in the hierarchy).
He began with the class of network problems from the computer science lecture, focusing on their overarching rule — that any given node’s algorithm uses information about just its local neighborhood, whether the graph has a thousand nodes or a billion.
To run properly, all the algorithm has to do is label each node in a given neighborhood with a unique number, so that it can log information about nearby nodes and give instructions about them. That’s easy enough to do in a finite graph: Just give every node in the graph a different number.