High-girth Steiner triple systems

Seminar
Speaker
Michael Simkin (Harvard)
Date
10/04/2022 - 15:30 - 14:00Add to Calendar 2022-04-10 14:00:00 2022-04-10 15:30:00 High-girth Steiner triple systems We prove a 1973 conjecture of Erdős on the existence of Steiner triple systems with arbitrarily high girth. (The girth of an STS is the smallest g>3 for which there exist g vertices spanning at least g-2 triangles.) Our construction builds on the methods of iterative absorption (Glock, Kühn, Lo, and Osthus) and the high-girth triangle removal process (Glock, Kühn, Lo, and Osthus and independently Bohman and Warnke). In particular, we extend iterative absorption to handle triangle-decompositions of sparse graphs. We also introduce a moments-based technique, similar to Kim--Vu polynomial concentration for dependent random variables, which allows a unified approach to control statistics of complex random processes. The talk will include an overview of iterative absorption. This is joint work with Matthew Kwan, Ashwin Sah, and Mehtaab Sawhney. Based on arXiv:2201.04554. Room 216/201 and also Zoom אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Room 216/201 and also Zoom
Abstract

We prove a 1973 conjecture of Erdős on the existence of Steiner triple systems with arbitrarily high girth. (The girth of an STS is the smallest g>3 for which there exist g vertices spanning at least g-2 triangles.) Our construction builds on the methods of iterative absorption (Glock, Kühn, Lo, and Osthus) and the high-girth triangle removal process (Glock, Kühn, Lo, and Osthus and independently Bohman and Warnke). In particular, we extend iterative absorption to handle triangle-decompositions of sparse graphs. We also introduce a moments-based technique, similar to Kim--Vu polynomial concentration for dependent random variables, which allows a unified approach to control statistics of complex random processes.

The talk will include an overview of iterative absorption.

This is joint work with Matthew Kwan, Ashwin Sah, and Mehtaab Sawhney.

Based on arXiv:2201.04554.

Last Updated Date : 15/04/2022