Hypergraphs Reveal a Solution to a 50-Year-Old Problem


The goal here is to draw triangles on top of these lines so 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 nodes.

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

Say instead of making triangles with edges, you’re building houses out of Lego bricks. The first buildings you make are extravagant, with structural reinforcements and elaborate ornamentation. Once you’re done with these, reserve them. They will serve as an “absorber”, a kind of structured storage.

Now start making buildings with your remaining bricks, proceeding without much planning. When your supply of Legos dwindles, you may find yourself with some missing bricks or houses that aren’t structural. But since the absorbing buildings are so over-the-top and reinforced, you can take out a few bricks here and there and use them without disaster.

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

Absorption doesn’t always work. But mathematicians have played with the process, finding new ways to get around the obstacles. For example, a powerful variant called iterative absorption splits the edges into a nested sequence of sets, so that each one acts as an absorber for the next larger one.

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

The Erdős problem was complicated even with iterative absorption. “It became pretty clear very quickly why this problem hadn’t been solved,” said Mehtaab Sawhney, one of four researchers who solved it, along with Ashwin Sah, who like Sawhney is a graduate student at the Institute of Technology of Massachusetts; Michael Simkin, a postdoctoral fellow at Harvard University’s Center for Mathematical Sciences and Applications; and Matthew Kwan, a mathematician at the Austrian Institute of Science and Technology. “There were quite interesting and difficult technical tasks.”

For example, in other applications of iterative absorption, once you’ve finished covering a set, either with triangles for Steiner triple systems, or with other structures for other problems, you can consider it done and forget it. Erdős’ conditions, however, prevented the four mathematicians from doing so. A problematic cluster of triangles could easily involve nodes from multiple absorbing sets.

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

What the four eventually discovered was that if they chose their triangles carefully, they could avoid the need to keep track of every little thing. “The best thing to do is think about any small set of 100 triangles and ensure that that set of triangles is chosen with the right probability,” Sawhney said.

The authors of the new paper are optimistic that their technique can be extended beyond this problem. They have already applied their strategy to a problem about Latin squares, which are like a simplification of a sudoku.

Beyond that, there are several questions that absorption methods may eventually give rise to, Kwan said. “There are many problems in combinatorics, especially in design theory, where random processes are a very powerful tool.” One such problem, the Ryser-Brualdi-Stein conjecture, also deals with Latin squares and has awaited a solution since the 1960s.

Although absorption may need further development before it can eliminate this problem, it has come a long way since its inception, said Maya Stein, assistant director of the Center for Mathematical Modeling at the University of Chile. “This is really cool to see how these methods evolve.”

original story reprinted with permission from Quanta Magazine, an independent editorial publication of the Simons Foundation whose mission is to improve public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.



Source link

Leave a Comment