MATH Seminar

Title: Large girth approximate Steiner triple systems
Seminar: Combinatorics
Speaker: Lutz Warnke of The Georgia Institute of Technology
Contact: Dwight Duffus, dwightduffus@emory.edu
Date: 2019-04-24 at 4:00PM
Venue: MSC W301
Download Flyer
Abstract: One can define the girth of a graph to be the minimum g such that there is a set of g vertices that spans at least g edges. This definition can be extended to the setting of Steiner triple systems by defining the girth to be the smallest g at least 4 for which there is a set of g vertices that spans at least g - 2 triples. In this talk we discuss a natural randomized algorithm that produces an approximate Steiner triple system of arbitrarily large girth, i.e., with (1/6-o(1)) n^2 triples, answering a question of Erdos from 1973 (that was independently also asked by Lefmann, Phelps, and Rodl in 1993, and Ellis and Linial in 2013). Joint work with Tom Bohman: https://arxiv.org/abs/1808.01065