Two stability theorems for ${\mathcal{K}}_{\ell +1}^r$-saturated hypergraphs

Abstract

An $\mathcal{F}$-saturated $r$-graph is a maximal $r$-graph not containing any member of $\mathcal{F}$ as a subgraph. Let ${\mathcal{K}}_{\ell +1}^r$ be the collection of all $r$-graphs $F$ with at most $\left(\genfrac{}{}{0ex}{}{\ell +1}{2}\right)$ edges such that for some $\left(\ell +1\right)$-set $S$ every pair $\{u,v\}\subset S$ is covered by an edge in $F$. Our first result shows that for each $\ell \ge r\ge 2$ every ${\mathcal{K}}_{\ell +1}^r$-saturated $r$-graph on $n$ vertices with $t_r(n,\ell )-o(n^{r-1+1/\ell })$ edges contains a complete $\ell$-partite subgraph on $(1-o(1))n$ vertices, which extends a stability theorem for $K_{\ell +1}$-saturated graphs given by Popielarz, Sahasrabudhe and Snyder. We also show that the bound is best possible. Our second result is motivated by a celebrated theorem of Andrásfai, Erdős and Sós which states that for $\ell \ge 2$ every $K_{\ell +1}$-free graph $G$ on $n$ vertices with minimum degree $\delta (G)>\frac{3\ell -4}{3\ell -1}n$ is $\ell$-partite. We give a hypergraph version of it. The \emph{minimum positive co-degree} of an $r$-graph $\mathcal{H}$, denoted by ${\delta }_{r-1}^{+}(\mathcal{H})$, is the maximum $k$ such that if $S$ is an $(r-1)$-set contained in a edge of $\mathcal{H}$, then $S$ is contained in at least $k$ distinct edges of $\mathcal{H}$. Let $\ell \ge 3$ be an integer and $\mathcal{H}$ be a ${\mathcal{K}}_{\ell +1}^3$-saturated $3$-graph on $n$ vertices. We prove that if either $\ell \ge 4$ and ${\delta }_2^{+}(\mathcal{H})>\frac{3\ell -7}{3\ell -1}n$; or $\ell =3$ and ${\delta }_2^{+}(\mathcal{H})>2n/7$, then $\mathcal{H}$ is $\ell$-partite; and the bound is best possible. This is the first stability result on minimum positive co-degree for hypergraphs.