The goal here is to trace out triangles on top of these lines such that the triangles satisfy two requirements: First, no two triangles share an edge. (Systems that fulfill this requirement are called Steiner triple systems.) And second, ensure that every small subset of triangles utilizes a sufficiently large number of nodes.
The way the researchers did this is perhaps best understood with an analogy.
Say that instead of making triangles out of edges, you’re building houses out of Lego bricks. The first few buildings you make are extravagant, with structural reinforcements and elaborate ornamentation. Once you’re done with these, set them aside. They’ll serve as an “absorber”—a kind of structured stockpile.
Now start making buildings out of your remaining bricks, proceeding without much planning. When your supply of Legos dwindles, you may find yourself with some stray bricks, or homes that are structurally unsound. But since the absorber buildings are so overdone and reinforced, you can pluck some bricks out here and there and use them without courting catastrophe.
In the case of the Steiner triple system, you’re trying to create triangles. Your absorber, in this case, is a carefully chosen collection of edges. If you find yourself unable to sort the rest of the system into triangles, you can use some of the edges that lead into the absorber. Then, when you’re done doing that, you break down the absorber itself into triangles.
Absorption doesn’t always work. But mathematicians have tinkered with the process, finding new ways to weasel around obstacles. For example, a powerful variant called iterative absorption divides the edges into a nested sequence of sets, so that each one acts as an absorber for the next biggest.
“Over the last decade or so there’s been massive improvements,” said Conlon. “It’s something of an art form, but they’ve really carried it up to the level of high art at this point.”
Erdős’ problem was tricky even with iterative absorption. “It became pretty clear pretty quickly why this problem had not been solved,” said Mehtaab Sawhney, one of the four researchers who solved it, along with Ashwin Sah, who like Sawhney is a graduate student at the Massachusetts Institute of Technology; Michael Simkin, a postdoctoral fellow at the Center of Mathematical Sciences and Applications at Harvard University; and Matthew Kwan, a mathematician at the Institute of Science and Technology Austria. “There were pretty interesting, pretty difficult technical tasks.”
For example, in other applications of iterative absorption, once you finish covering a set—either with triangles for Steiner triple systems, or with other structures for other problems—you can consider it dealt with and forget about it. Erdős’ conditions, however, prevented the four mathematicians from doing that. A problematic cluster of triangles could easily involve nodes from multiple absorber sets.
“A triangle you chose 500 steps ago, you need to somehow remember how to think about that,” said Sawhney.
What the four eventually figured out was that if they chose their triangles carefully, they could circumvent the need to keep track of every little thing. “What it’s better to do is to think about any small set of 100 triangles and guarantee that set of triangles is chosen with the correct probability,” said Sawhney.
The authors of the new paper are optimistic that their technique can be extended beyond this one problem. They have already applied their strategy to a problem about Latin squares, which are like a simplification of a sudoku puzzle.
Beyond that, there are several questions that may eventually yield to absorption methods, said Kwan. “There’s so many problems in combinatorics, especially in design theory, where random processes are a really powerful tool.” One such problem, the Ryser-Brualdi-Stein conjecture, is also about Latin squares and has awaited a solution since the 1960s.
Though absorption may need further development before it can fell that problem, it has come a long way since its inception, said Maya Stein, the deputy director of the Center for Mathematical Modeling at the University of Chile. “That’s something that’s really great to see, how these methods evolve.”
Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.