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

：侯建锋（福州大学）
：2023-02-16 16:20
：厦大海韵园实验楼105报告厅

报告人：侯建锋（福州大学）

时  间：2023年2月16日下午16:20-17:00

地  点：厦大海韵园实验楼105报告厅

内容摘要:

Let $\mathcal{F}$ be a family of  $r$-uniform hypergraph. An $\mathcal{F}$-saturated hypergraph is a maximal $r$-uniform hypergraph not containing any member of $\mathcal{F}$ as a subgraph. For $\ell \geq r \geq 2$  be integers, let $\mathcal{K}_{\ell + 1}^{r}$ be the collection of all $r$-uniform hypergraphs $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$, and let $T_r (n, \ell)$ be the complete $\ell$-partite $r$-uniform graph on $n$ vertices with no two part sizes differing by more than one. Let $t_{r}(n, \ell)$ be the number of edges in $T_r (n, \ell)$. Popielarz, Sahasrabudhe and Snyder gave a stability theorem for $K_{\ell+1}$-saturated graphs by showing that such a graph  on $n$ vertices with $t_{2}(n, \ell)-o(n^{1+1/\ell})$ edges contains a complete $\ell$-partite subgraph on $(1-o(1))n$ vertices. In this paper, we extend it to  $\mathcal{K}_{\ell + 1}^{r}$-saturated hypergraphs by showing that for all $\ell \geq r \geq 2$ every $\mathcal{K}_{\ell+1}^{r}$-saturated $r$-uniform hypergraph on $n$ vertices with $t_{r}(n, \ell) - o(n^{r-1+1/\ell})$ edges contains a complete $\ell$-partite subhypergraph on $(1-o(1))n$ vertices. We also show that the bound is best possible.

A celebrated theorem of Andr\'{a}sfai, Erd\H{o}s and S\'{o}s 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. Motivated by recent work on minimum positive co-degree, we give a hypergraph version of it in this paper.   The \emph{minimum positive co-degree} of an $r$-uniform hypergraph $\mathcal{H}$, denoted by $\delta_{r-1}^{+}(\mathcal{H})$, is the maximum $k$ such that such that if $S$ is an $(r-1)$-set contained in a hyperedge of $\mathcal{H}$, then $S$ is contained in at least $k$ distinct hyperedges of $\mathcal{H}$. Let $\ell\ge 3$ be an integer and $\mathcal{H}$ be a maximal $\mathcal{K}_{\ell+1}^3$-free $3$-uniform hypergraph on $n$ vertices. In this paper, we show $\mathcal{H}$ is $\ell$-partite 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$. We also show that the bound is best possible. This is the first stability result on minimum positive co-degree for hypergraphs.

个人简介：

侯建锋，福州大学教授，博士生导师。2009年7月毕业于山东大学数学学院，获理学博士学位。2011年度全国优秀博士学位论文提名奖，2011年度福建省自然科学基金杰出青年项目获得者，2020年入选福建省“雏鹰计划”青年拔尖人次，2021年入选国家高层次人才计划，主持国家自然科学基金4项，参与重点项目一项。目前为中国数学会组合数学与图论专业委员会委员，中国工业与应用数学学会图论组合及应用专业委员会委员，福建省数学会常务理事，Frontiers of Computer Science青年AE。主要从事图划分理论、极值组合和图染色领域研究，解决了英国皇家学会会员Bollobas、图论学者Mubayi等人提出的多个猜想和公开问题，在JCTA(B)、RSA、CPC、JGT等领域杂志发表学术论文多篇。