Blog

There is an impressive new preprint titled High-Girth Steiner Triple Systems by Matthew Kwan, Ashwin Sah, Mehtaab Sawhney, and Michael Simkin. They prove a 1973 Erdős conjecture showing the existence of Steiner triple systems with arbitrarily high girth.

An order n triple system is defined to be a set of unordered triples of ${1, \dots, n}$. Furthermore, it is a Steiner triple system if every pair of vertices is contained in exactly one triple.

An example of a Steiner triple system is the Fano plane, illustrated below.

Here each line or circle represents a triple containing its elements. Note that every pair of vertices lies in exactly one line/circle (this is what makes it Steiner).

Steiner triple systems are old and fascinating objects that occupy a central place in combinatorics. For example, see this Quanta Magazine article for a popular account on Steiner triple systems and recent breakthroughs in design theory.

In the past decade, since Peter Keevash’s 2014 breakthrough proving the existence of designs, there has been a flurry of exciting developments by many researchers settling longstanding open problems related to designs and packings. Several related results were also featured in Quanta magazine: Ringel’s conjecture, Erdős–Faber–Lovász conjecture, n-queens problem.

The new work proves the existence of Steiner triple systems with a desirable additional property: high girth.

In a graph, the girth is defined to be the length of a shortest cycle. The girth of a triple system is defined as follows (see the first page of the paper for some motivation behind this definition).

Definition. The girth of a triple system is the smallest positive integer g so that there exist g triples occupying no more than $g+2$ vertices. (If no such g exists, then we say that the girth is infinite.)

Here is the main result of the new paper, which settles the Erdős conjecture.

Theorem (Kwan–Sah–Sawhney–Simkin). For all $n \equiv 1,3 \pmod{6}$, there exists a Steiner triple system whose girth tends to infinity as $n \to \infty$.

They build on previous works by Glock, Kühn, Lo, and Osthus and Bohman and Warnke proving the existence of “approximate” Steiner triple systems (meaning having $1-o(1)$ fraction of the maximum possible number of triples).

Before this work, it was not even known if there existed infinitely many Steiner triple systems with girth ≥ 10.

The proof uses a stunning array of techniques at the frontier of extremal and probabilistic combinatorics, including recently developed tools for random greedy algorithms, as well as the iterative absorption method.

• Mehtaab Sawhney wins Clay Research Fellowship 1/25/2024
• Papers by MIT combinatorialists—Fall 2023 12/22/2023
• Schildkraut: Equiangular lines and large multiplicity of fixed second eigenvalue 3/6/2023
• Nearly all k-SAT functions are unate 9/19/2022
• Kwan–Sah–Sawhney–Simkin: High-girth Steiner triple systems 1/13/2022
• Graphs with high second eigenvalue multiplicity 9/28/2021
• Enumerating k-SAT functions 7/21/2021
• Mathematical tools for large graphs 7/12/2021
• How I manage my BibTeX references, and why I prefer not initializing first names 7/4/2021
• The cylindrical width of transitive sets 1/28/2021
• Ashwin Sah and Mehtaab Sawhney win the Morgan Prize 10/29/2020
• Jain–Sah–Sawhney: Singularity of discrete random matrices 10/13/2020
• Gunby: Upper tails for random regular graphs 10/5/2020
• Joints of varieties 9/12/2020
• Ashwin Sah's new diagonal Ramsey number upper bound 5/20/2020
• Joints tightened 11/21/2019
• Equiangular lines with a fixed angle 7/30/2019
• Impartial digraphs 6/27/2019
• A reverse Sidorenko inequality 9/26/2018
• The number of independent sets in an irregular graph 5/12/2018