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

In 1850, Thomas Penyngton Kirkman , a mathematician when he wasn’t fulfilling his main responsibility as a vicar in the Church of England, described his “schoolgirl problem”: “Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily, so that no two shall walk twice abreast. ” 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 develop­ments and trends in mathe­matics and the physical and life sciences. To a modern mathematician, this kind of problem is best imagined as a hypergraph—a set of nodes collected in groups of three or more.

The 15 schoolgirls are nodes, and each group of “three abreast” can be thought of as a triangle, with three lines, or edges, connecting three nodes. Kirkman’s problem essentially asks whether there’s an arrangement of these triangles that connects all the schoolgirls to one another, but with the added restriction that no two triangles share an edge. Edge-sharing would imply that two schoolgirls have to walk together more than once.

This restriction means each girl walks with two new friends every day for a week, so that every possible pair gets together exactly once. This problem and others like it have beguiled mathematicians for the nearly two centuries since Kirkman posed his question. In 1973, the legendary mathematician Paul Erdős posed a similar one.

He asked whether it’s possible to build a hypergraph with two seemingly incompatible properties. First, every pair of nodes must be connected by exactly one triangle, as with the schoolgirls. This property makes the graph dense with triangles.

The second requirement forces the triangles to be spread out in a very precise way. (Specifically, it requires that for any small group of triangles, there are at least three more nodes than there are triangles. ) “You have this slightly contradictory behavior where you have a dense overall object that has no dense parts,” said David Conlon , a mathematician at the California Institute of Technology.

This January, in an intricate 50-page proof , four mathematicians proved that it’s always possible to build such a hypergraph as long as you have enough nodes. “The amount of technicality that they went through just to get this was amazing,” said Allan Lo , a mathematician at the University of Birmingham. Conlon concurred: “It’s a really impressive piece of work.

” The research team built a system that satisfied Erdős’ devilish requirements by starting with a random process for choosing triangles and engineering it with extreme care to suit their needs. “The number of difficult modifications that go into the proof is actually kind of staggering,” said Conlon. Their strategy was to carefully build the hypergraph out of individual triangles.

For example, imagine our 15 schoolgirls. Draw a line between each pair. 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.

.