# Uniquely $K_r^{(k)}$-Saturated Hypergraphs

### Abstract

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\leqslant k <r<n$, a $k$-uniform hypergraph $H$ with $n$ vertices is *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 *exactly one* copy of $K_r^{(k)}$. Among uniquely $K_r^{(k)}$-saturated hypergraphs, the interesting ones are the *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 *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\leqslant k<r\leqslant 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\ge 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\leqslant n \leqslant {(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.