Uniquely \(K_r^{(k)}\)-saturated hypergraphs

András Gyárfás¹ ; Stephen G. Hartke² ; Charles Viss²

¹Alfréd Rényi Institute of Mathematics
²University of Colorado Denver

The electronic journal of combinatorics, Tome 25 (2018) no. 4

Résumé

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.

Détail

DOI : 10.37236/7534

Classification : 05C65, 05D15, 05D05, 05B05
Mots-clés : hypergraphs, uniquely saturated