You’ll need to use a third color – say, green – to complete your color.
Still, the sets of blue, yellow, and green nodes you get are all just fragments of the circle’s circumference, not the scatter of points you got when you used the axiom of choice. You can calculate the length of these sets. They are 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 moves to a much higher shelf of problems—where many of the notions of measurement can be applied.
Bernshtein spent his years in graduate school studying such color problems and solving them one by one. Then, shortly after completing his degree, he stumbled upon a possible way to eliminate them all at once – and to show that these problems had a far deeper and mathematically relevant structure than anyone had thought.
round after round
From time to time, Bernshtein likes to go to computer science talks, where graphs are limited and represent networks of computers.
In 2019, one of those conversations changed the direction 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.
Let’s say you have a group of Wi-Fi routers in a building. Nearby routers may interfere with each other if they use the same communication frequency channel. Therefore each router needs to choose a different channel from that used by its nearest neighbors.
Computer scientists can reframe this as a coloring problem on a graph: represent each router as a node, and connect nearby routers with edges. Using only 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 nearest 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 in a small area around it are colored. It then runs the algorithm again to decide whether to keep its color or change it. It repeats this step until the entire network has the appropriate color.
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 if you are allowed to use three colors it is possible to find a very efficient local algorithm.
At a talk Bernshtein was attending, the speaker discussed these limits for a variety of problems. A limit, he realized, sounds like a limit that exists in the world of descriptive set theory – about the number of colors needed to color some infinite graph in a measurable way.
To Bernshtein this seemed more than a coincidence. It’s not just that computer scientists are like librarians, they solve problems based on how efficiently their algorithms work. It was not as if these problems could even be written in terms of graphs and colors.
Perhaps, he thought, the two bookshelves had more in common than that. Perhaps the relationship between these two areas has become much deeper.
Perhaps all the books and their shelves were the same, just written in different languages – and needed a translator.
open the door
Bernshtein attempted to clarify this relationship. He wanted to show that every efficient local algorithm can be transformed into a Lebesgue-measurable way of coloring an infinite graph (which satisfies some additional important properties). That is, one of the most important shelves of computer science is equivalent to one of the most important shelves (higher in the hierarchy) of set theory.
He started with a class on network problems from computer science lectures, focusing on his overarching rule – that any algorithm for any node uses only information about its local neighborhood, whether the graph has a thousand nodes or a billion.
To run properly, the algorithm simply needs to 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. This is quite easy to do in a finite graph: simply give each node in the graph a different number.
<a href