A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems

2022/08/22 by Im, Seonghyuk, Kim, Jaehoon, Lee, Joonkyung +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2208.10370

Abstract

Hypertrees are linear hypergraphs where every two vertices are connected by a unique path. Elliott and Rödl conjectured that for any given μ>0, there exists n₀ such that the following holds. Every n-vertex Steiner triple system contains all hypertrees with at most (1-μ)n vertices whenever n≥ n₀. We prove this conjecture.

Related

• Every Steiner triple system contains an almost spanning d-ary hypertree
• A construction of almost Steiner systems
• Towards a high-dimensional Dirac's theorem
• On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices
• Spreading linear triple systems and expander triple systems