{
  "id": "2211.02838",
  "version": "v1",
  "published": "2022-11-05T07:50:19.000Z",
  "updated": "2022-11-05T07:50:19.000Z",
  "title": "Two stability theorems for $\\mathcal{K}_{\\ell + 1}^{r}$-saturated hypergraphs",
  "authors": [
    "Jianfeng Hou",
    "Heng Li",
    "Caihong Yang",
    "Qinghou Zeng",
    "Yixiao Zhang"
  ],
  "categories": [
    "math.CO"
  ],
  "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 $\\binom{\\ell+1}{2}$ 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 \\geq r \\geq 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\\'{a}sfai, Erd\\H{o}s and S\\'{o}s which states that for $\\ell \\geq 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-11-05T07:50:19.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "stability theorem",
      "saturated hypergraphs",
      "first stability result",
      "minimum positive co-degree",
      "edges contains"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}