Uniquely \(K_r^{(k)}\)-saturated hypergraphs (Q1627212): Difference between revisions

Summary: In this paper we generalize the concept of uniquely \(K_r\)-saturated graphs to hypergraphs. Let \(K_r^{(k)}\) denote the complete \(k\)-uniform hypergraph on \(r\) vertices. For integers \(k,r,n\) such that \(2\leq k <r<n\), a \(k\)-uniform hypergraph \(H\) with \(n\) vertices is \textit{uniquely \(K_r^{(k)}\)-saturated}~if \(H\) does not contain \(K_r^{(k)}\) but adding to \(H\) any \(k\)-set that is not a hyperedge of \(H\) results in \textit{exactly one} copy of \(K_r^{(k)}\). Among uniquely \(K_r^{(k)}\)-saturated hypergraphs, the interesting ones are the \textit{primitive} ones that do not have a dominating vertex -- a vertex belonging to all possible \({n-1\choose k-1}\) edges. Translating the concept to the complements of these hypergraphs, we obtain a natural restriction of \(\tau\)-critical hypergraphs: a hypergraph \(H\) is \textit{uniquely \(\tau\)-critical} if for every edge \(e\), \(\tau(H-e)=\tau(H)-1\) and \(H-e\) has a unique transversal of size \(\tau(H)-1\). We have two constructions for primitive uniquely \(K_r^{(k)}\)-saturated hypergraphs. One shows that for \(k\) and \(r\) where \(4\leq k<r\leq 2k-3\), there exists such a hypergraph for every \(n>r\). This is in contrast to the case \(k=2\) and \(r=3\) where only the Moore graphs of diameter two have this property. Our other construction keeps \(n-r\) fixed; in this case we show that for any fixed \(k\geq 2\) there can only be finitely many examples. We give a range for \(n\) where these hypergraphs exist. For \(n-r=1\) the range is completely determined: \(k+1\leq n \leq {(k+2)^2\over 4}\). For larger values of \(n-r\) the upper end of our range reaches approximately half of its upper bound. The lower end depends on the chromatic number of certain Johnson graphs.