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.
... continue reading