Every Steiner triple system contains almost spanning \(d\)-ary hypertree (Q2161203): Difference between revisions

A Steiner triple system (STS) is a 3-uniform hypergraph in which every pair of vertices is contained in exactly one edge. A perfect \(d\)-ary hypertree \(T\) of height \(h\) is a hypertree \(T\) with \(V(T)=\bigcup_{i=0}^h V_i\), where \(|V_i|=(2d)^i\) for all \(i\in [0, h]\), such that for every \(i \in [0, h-1]\) and \(v\in V_i\) there are \(2d\) vertices \(\{u_1, \dots, u_{2d}\} \subseteq V_{i+1}\) such that \(\{v, u_{2j-1}, u_{2j}\}\) is a hyperedge of \(T\) for all \(j\in [d]\). \textit{B. Elliott} and \textit{V. Rödl} [J. Comb. Des. 27, No. 2, 82--105 (2019; Zbl 1407.05034)] raised a conjecture: given \(\mu > 0\) there is an \(n_0\), such that for any \(n> n_0\), any hypertree \(T\) on \(n\) vertices and any Steiner triple system \(S\) on at least \((1+\mu)n\) vertices, \(S\) contains \(T\) as a subhypergraph. Relying on the application of an existence of an almost perfect matching in an almost regular 3-uniform simple hypergraph, the authors proves that the conjecture holds if \(T\) is a perfect \(d\)-ary hypertree.