On the minimum size of Hamilton saturated hypergraphs (Q2213813): Difference between revisions

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} showed [Period. Math. Hung. 14, 57--68 (1983; Zbl 0489.05038)] 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\leqslant k-1\), \(\mathrm{sat}(N,k,\ell)=\Theta(N^{\ell})\). Here we prove that \(\mathrm{sat}(N,2\ell,\ell)=\Theta\left(N^\ell\right)\).