Seonghyuk Im (임성혁), A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems

A linear $3$-graph is called a (3-)hypertree if there exists exactly one path between each pair of two distinct vertices.  A linear $3$-graph is called a Steiner triple system if each pair of two distinct vertices belong to a unique edge.

A simple greedy algorithm shows that every $n$-vertex Steiner triple system $G$ contains all hypertrees $T$ of order at most $\frac{n+3}{2}$. On the other hand, it is not immediately clear whether one can always find larger hypertrees in $G$. In 2011, Goodall and de Mier proved that a Steiner triple system $G$ contains at least one spanning tree. However, one cannot expect the Steiner triple system to contain all possible spanning trees, as there are many Steiner triple systems that avoid numerous spanning trees as subgraphs. Hence it is natural to wonder how much one can improve the bound from the greedy algorithm.

Indeed, Elliott and Rödl conjectured that an $n$-vertex Steiner triple system $G$ contains all hypertrees of order at most $(1-o(1))n$. We prove the conjecture by Elliott and Rödl.

This is joint work with Jaehoon Kim, Joonkyung Lee, and Abhishek Methuku.