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

The goal here is to trace triangles on top of these lines such that the triangles satisfy two requirements: First, no two triangles share an edge. (Systems that satisfy this requirement are called Steiner triple systems.) And second, make sure that each small subset of triangles uses a sufficiently large number of vertices.

The way the researchers did this is perhaps best understood with an analogy.

Say that instead of making triangles out of edges, you build houses out of Lego blocks. The first few buildings you make are extravagant, with structural reinforcements and elaborate ornamentation. When you are done with these, set them aside. They will serve as an “absorber” – a kind of structured storage.

Now start making buildings out of your remaining bricks, proceed 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 overpowered and reinforced, you can pick out some bricks here and there and use them without courting disaster.

In the case of the Steiner triple system, you are trying to create triangles. Your absorber, in this case, is a carefully selected collection of edges. If you are not able to sort the rest of the system into triangles, you can use some of the edges leading into the absorber. Then, when you’re done with that, break down the absorber itself into triangles.

Absorption does not always work. But mathematicians have tinkered with the process and found new ways to wiggle around obstacles. For example, a powerful variant called iterative absorption divides the edges into a nested sequence of sets, each of which acts as an absorber for the next largest.

“Over the last decade or so, there have been massive improvements,” Conlon said. “It’s quite an art form, but they’ve really taken it to the level of high art at this point.”

Erdős’ problem was difficult even with iterative absorption. “It became clear pretty quickly why this issue had not been resolved,” said Mehtaab Sawhneyone of the four researchers who solved it, along with Ashwin Sahwho, 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 quite interesting, quite difficult technical tasks.”

For example, in other applications of iterative absorption, when you finish covering a set—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’ conditions prevented the four mathematicians from doing so. A problematic cluster of triangles could easily involve nodes from multiple absorber sets.

“A triangle you picked 500 steps ago, you have to somehow remember how you think about it,” Sawhney said.

What the four eventually found was that if they chose their triangles carefully, they could bypass the need to keep track of every little thing. “What it’s better to do is think about any small set of 100 triangles and guarantee that set of triangles is chosen with the correct probability,” Sawhney said.

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 regarding latin squareswhich is like a simplification of a sudoku puzzle.

Beyond that, there are several issues that may ultimately give way 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 such problem, the Ryser–Brualdi–Stein conjecture, also deals with Latin squares and has been awaiting a solution since the 1960s.

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

Original story reprinted with permission from Quanta Magazine, an editorially independent publication of Simon’s Foundation whose mission is to increase public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.

Leave a comment