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

MaRDI QIDQ6416232zbMATH OpenFDO

Authors Jianfeng Hou, Heng Li, Caihong Yang, Qinghou Zeng, Yixiao Zhang

Publication date 5 November 2022

Abstract: An $mathcalF$-saturated $r$-graph is a maximal $r$-graph not containing any member of $mathcalF$ as a subgraph. Let $mathcal{K}_{ell+1}^r$ be the collection of all $r$-graphs $F$ with at most $$ edges such that for some $left(ell+1ight)$-set $S$ every pair $u,vsubsetS$ is covered by an edge in $F$. Our first result shows that for each $ellgeqrgeq2$ 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'{a}sfai, ErdH{o}s and S'{o}s which states that for $ellgeq2$ every $K_{ell+1}$-free graph $G$ on $n$ vertices with minimum degree $delta(G)>frac3ell-43ell-1n$ is $ell$-partite. We give a hypergraph version of it. The emph{minimum positive co-degree} of an $r$-graph $mathcalH$, denoted by $delt{a}_{r-1}^{+}(mathcalH)$, is the maximum $k$ such that if $S$ is an $(r-1)$-set contained in a edge of $mathcalH$, then $S$ is contained in at least $k$ distinct edges of $mathcalH$. Let $ellge3$ be an integer and $mathcalH$ be a $mathcal{K}_{ell+1}^3$-saturated $3$-graph on $n$ vertices. We prove that if either $ellge4$ and $delt{a}_2^{+}(mathcalH)>frac3ell-73ell-1n$; or $ell=3$ and $delt{a}_2^{+}(mathcalH)>2n/7$, then $mathcalH$ is $ell$-partite; and the bound is best possible. This is the first stability result on minimum positive co-degree for hypergraphs.

This page was built for publication: Two stability theorems for $\mathcal{K}_{\ell + 1}^{r}$-saturated hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6416232)