Hypergraphs reveal a solution to a 50-year-old problem

The goal here is to draw triangles over these lines in such a way that the triangles meet two requirements: First, no two triangles share an edge. (Systems that meet this requirement are called Steiner triple systems.) Second, make sure that each small subset of triangles uses a large enough number of nodes.

The way the researchers went about this is perhaps best understood through an analogy.

Suppose you build houses out of lego bricks instead of making triangles out of edges. The first few buildings you build are extravagant, with structural reinforcements and ornate decorations. Once you’re done with that, set it aside. They serve as “absorbers” – a kind of structured supply.

Now start constructing buildings from your remaining bricks without much planning. When you run out of Legos, you might find yourself with some stray bricks or houses that aren’t structurally intact. But since the absorber buildings are so over the top and reinforced, you can rip out a few rocks here and there and use them without provoking disaster.

In the case of the Steiner system of three, try to create triangles. Your absorber, in this case, is a carefully chosen collection of edges. If you can’t sort the rest of the system into triangles, you can use some of the edges that lead into the absorber. When you’re done with that, disassemble the absorber itself into triangles.

Absorption doesn’t always work. But mathematicians have tinkered with the process and found new ways to circumvent obstacles. For example, a powerful variant called iterative absorption divides the edges into a nested sequence of sets, each acting as an absorber for the next largest.

“There’s been massive improvement over the past decade,” Conlon said. “It’s kind of an art form, but they’ve really taken it to the level of fine art at that point.”

Erdős’ problem was difficult even with iterative absorption. “It became clear pretty quickly why this problem wasn’t 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 Harvard University’s Center for Mathematical Sciences and Applications; and Matthew Kwan, mathematician at the Institute of Science and Technology Austria. “There were quite interesting, quite difficult technical tasks.”

For example, in other uses of iterative absorption, when you’ve got a lot covered—either with triangles for Steiner triple systems, or with other structures for other problems—you can consider it done and forget about it. However, Erdős’ terms prevented the four mathematicians from doing so. A problematic cluster of triangles could easily contain nodes from multiple sets of absorbers.

“A triangle that you picked 500 steps ago, you kind of have to remember how you feel about it,” Sawhney said.

What the four eventually found was that by choosing their triangles carefully, they could bypass the need to keep track of every detail. “It’s better to think of an arbitrary small set of 100 triangles and make sure the set of triangles is chosen with the right probability,” Sawhney said.

The authors of the new work are optimistic that their technique can be extended beyond this one problem. They’ve already applied their strategy to a Latin squares problem, which is like a simplification of a Sudoku puzzle.

Additionally, there are several questions that could ultimately lead to absorption methods, Kwan said. “There are so many problems in combinatorics, especially in design theory, where random processes are a really powerful tool.” One of these problems, the Ryser-Brualdi-Stein conjecture, also affects Latin squares and has been waiting for a solution since the 1960s .

Although absorption may need further development before it can solve this problem, it has come a long way since its inception, said Maya Stein, associate director of the Center for Mathematical Modeling at the University of Chile. “It’s really great to see how these methods are evolving.”

Original story Reprinted with permission from quanta magazine, an editorially independent publication Simons Foundation whose mission is to improve public understanding of science by covering research developments and trends in mathematics and the natural and life sciences.

Leave a Comment

Your email address will not be published.