There’s a lot more to map design than you might think. For a world map to be useful, each country must be easily distinguishable from the next. Ideally, you don’t want two countries that are bordering each other to have the same color representing them – that would make reading the map harder. In 1852, Mathematician Francie Guthrie theorized that you’d only need four colors to create a map without the same colors touching. The theory, called the Four Color Problem, could be proven by coloring a map, but the actual mathematical proof required a computer to solve it.
A very natural question is how many colors do I need for that map of the world — how many pens should I buy? It turns out that the answer is four … They [solved] that with computer assistance. Even to this day, nobody has been able to recreate that proof with pen and paper.
–Bernardo Subercaseaux, CMU
The Packing Chromatic Number Problem is a more complex version of the Four Color Problem. Imagine you have four stacks of sticky notes – each stack a different color. You’re tasked with a simple enough problem: create a four-by-six grid of sticky notes, but no two colors can touch sides. Now, make the grid 64 by 64. Now add some new rules – pink sticky notes need to be two notes away from each other. What you’ll start to notice as you create your grid is that you need more colors to solve the puzzle. How many colors would be needed for an infinite number of sticky notes? How many colors would be needed if the rules became even more complex? Previously, researchers had determined that 15 colors would do the trick, but that 12 wasn’t enough. Carnegie Mellon University (CMU) graduate student Bernardo Subercaseaux wanted to prove what number of colors was the absolute minimum needed to solve the problem.
It may seem like a frivolous experiment, but the Packing Chromatic Number Problem has a lot of everyday uses. Bus schedules, wireless frequency assignments, optical network design and even parallel computing all rely on this magic number to make sure routes, frequencies, wavelengths and execution times all work without confusion. Proving 15 is the lowest number that works means the most efficient number is being used.
Subercaseaux’s research shows how ACCESS resources can be used in all kinds of research projects. In Subercaseaux’s case, he was able to solve the problem and complete his dissertation using ACCESS resource, Bridges-2.
Just having a trusted environment [like Bridges-2] to run many experiments really reliably [was] very important.
Bernardo Subercaseaux, CMU
Visit the allocations page to learn how you can use ACCESS to accelerate your research.
You can read more about this story here: And the Number of the Counting Shall Be 15.
Project Details
Resource Provider Institution: Pittsburgh Supercomputing Center (PSC)
Affiliations: Carnegie Mellon University
Funding Agency: NSF
Grant or Allocation Number(s): CIS230106
The science story featured here was enabled by the ACCESS program, which is supported by National Science Foundation grants #2138259, #2138286, #2138307, #2137603, and #2138296.