The goal here is to find triangles lying on these lines such that the triangles satisfy two requirements: First, no two triangles have a common side. (Systems that meet this requirement are called Steiner triple systems.) And second, ensure that every small triangular subset uses 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 from the sides, you’re building a house out of Lego bricks. Some of the first buildings you make are lavish, with reinforced textures and intricate decorations. Once you’re done with these, set them aside. They will act as an “absorber”—a kind of structured storehouse.
Now start creating buildings from your remaining bricks, continuing without much planning. When your supply of Legos runs out, you may find yourself with some misplaced bricks, or structurally uncertain houses. But since the absorption buildings are so old and reinforced, you can uproot some bricks here and there and use them without a disaster.
In the case of the Steiner triple system, you are trying to create triangles. In this case, your absorber is a carefully selected collection of edges. If you find yourself unable to arrange the rest of the system into a triangle, you can use some leading edge into the absorber. Then, when you’re done with that, you subdivide the absorber into triangles.
Absorption doesn’t always work. But mathematicians have tinkered with the process, finding new ways to get around obstacles. For example, a powerful variant called iterative absorption divides edges into a series of nested sets, so that each edge acts as an absorber for the next largest.
“Over the past decade or so, there have been major improvements,” says Conlon. “It’s something of an art form, but they’ve really elevated it to high art at this point.”
Erdős’ problem is complex even with repeated absorption. “It very quickly became clear why this issue remained unresolved,” says Mehtaab Sawhneyone in four researchers solved it, along with Ashwin Sahwho like Sawhney is a PhD student at the Massachusetts Institute of Technology; Michael Simkin, a postdoctoral fellow at the Center for Applied and Mathematical Sciences at Harvard University; and Matthew Kwan, a mathematician at the Austrian Institute of Science and Technology. “There are quite interesting technical tasks, quite difficult.”
For example, in other applications of iterative absorption, when you finish covering a set — either with triangles for Steiner triples or with other structures for other problems — you maybe consider it processed and forget about it. However, Erdős’ conditions prevented the four mathematicians from doing so. A problematic triangular cluster can easily involve nodes from multiple absorbers.
“A triangle you picked 500 feet away, you need to remember how to think about it,” says Sawhney.
What all four eventually figured out was that if they chose their triangles carefully, they could avoid having to keep track of every little thing. “The better thing to do is to think of any small set of 100 triangles and make sure that set of triangles is chosen with the correct probability,” says Sawhney.
The authors of the new paper are optimistic that their technique can be extended beyond this problem. They have adopted their strategy a problem about Latin squarelike a simplification of a sudoku puzzle.
In addition, there are some final questions that may arise for absorption methods, Kwan said. “There are a lot of problems in combinatorics, especially in design theory, where stochastic processes are a really powerful tool.” One such problem, the Ryser-Brualdi-Stein conjecture, is also about Latin squares and has been waiting for a solution since the 1960s.
While absorption may need further development before it can solve that problem, it has come a long way since its inception, Maya Stein, Deputy Director of the Center for Mathematical Modeling at the University of Chile. “It’s really amazing to see how these methods evolve.”
Original story Reprinted with permission of Quanta magazine, an editorially independent publication of The Simons Organization whose mission is to advance public understanding of science by including research developments and trends in mathematics as well as the physical and life sciences.
