Upper bounds on the minimum size of Hamilton saturated hypergraphs (Q727183)

Summary: For \(1\leqslant \ell< k\),~ an \(\ell\)-overlapping \(k\)-cycle is a \(k\)-uniform hypergraph in which, for some cyclic vertex ordering, every edge consists of \(k\) consecutive vertices and every two consecutive edges share exactly \(\ell\) vertices. A \(k\)-uniform hypergraph \(H\) is \(\ell\)-Hamiltonian saturated if \(H\) does not contain an \(\ell\)-overlapping Hamiltonian \(k\)-cycle but every hypergraph obtained from \(H\) by adding one edge does contain such a cycle. Let \(\mathrm{sat}(n,k,\ell)\) be the smallest number of edges in an \(\ell\)-Hamiltonian saturated \(k\)-uniform hypergraph on \(n\) vertices. In the case of graphs \textit{L. Clark} and \textit{R. Entringer} [Period. Math. Hung. 14, 57--68 (1983; Zbl 0489.05038)] showed that \(\mathrm{sat}(n,2,1)=\lceil\frac{3n}{2}\rceil\). The present authors proved that for \(k\geqslant 3\) and \(\ell=1\), as well as for all \(0.8k\leqslant \ell\leq k-1\), \(\mathrm{sat}(n,k,\ell)=\Theta(n^{\ell})\). In this paper we prove two upper bounds which cover the remaining range of \(\ell\). The first, quite technical one, restricted to \(\ell\geqslant\frac{k+1}{2}\), implies in particular that for \(\ell=\frac{2}{3}k\) and \(\ell=\frac{3}{4}k\) we have \(\mathrm{sat}(n,k,\ell)=O(n^{\ell+1})\). Our main result provides an upper bound \(\mathrm{sat}(n,k,\ell)=O(n^{\frac{k+\ell}2})\) valid for all \(k\) and \(\ell\). In the smallest open case we improve it further to \(\mathrm{sat}(n,4,2)=O(n^{14/5})\).