Mathematics Computer Science Seminar
Tom Bohman
Carnegie Mellon
Large girth approximate Steiner triple systems
Abstract: One can define the girth of a graph to be the minimum $a$ such that
there is a set of $a$ vertices that spans at least $a$ edges.
This definition can be extended to the setting of 3-uniform
hypergraphs by defining the girth to be the smallest $a\ge 4$ for which there is a set of $a$ vertices that spans at least $a-2$ edges. A Steiner system is a collection of triples on $n$ vertices with the property that every pair of vertices is in exactly one triple. In the 1970s Erd\H{o}s conjectured the existence of Steiner systems with arbitrarily large girth. In this talk we discuss a randomized algorithm that produces an approximate Steiner system of arbitrarily large girth.
Monday March 5, 2018 at 3:00 PM in SEO 427