论文标题
均匀超图的狄拉克型定理
A Dirac-type theorem for uniform hypergraphs
论文作者
论文摘要
Dirac（1952）证明，每条连接的订单$ n> 2k+1 $，最低度超过$ k $的图形包含一条长度至少$ 2K+1 $。 ErdőS和Gallai（1959）表明，每$ n $ vertex Graph $ g $具有平均度超过$ k-1 $的$ g $包含一条长度$ k $的路径。 Erdős-Gallai定理的超图扩展由Győri，Katona，Lemons〜（2016）和Davoodi等人（2018）给出。 Füredi，Kostochka和Luo（2019）给出了Erdős-Gallai Shilem for HyperGraphs的连接版本。在本文中，我们给出了Dirac定理的超图扩展：鉴于正整数$ n，k $和$ r $，让$ h $为连接的$ n $ n $ -vertex $ r $ r $ - 没有长度$ 2K+1 $的berge路径。我们表明（1）如果$ k> r \ ge 4 $和$ n> 2k+1 $，则$δ_1（h）\ le \ binom {k} {r-1} $。此外，当且仅当$ s'_r（n，k）\ subseteq h \ subseteq s_r（n，k）$或$ h \ cong s（sk_ {k+1}^{（r）}，1），1），1）$; （2）如果$ k \ ge r \ ge 2 $和$ n> 2k（r-1）$，则$δ_1（h）\ le \ binom {k} {r-1} $。结果也是Füredi，Kostochka和Luo的结果的Dirac型版本。作为（1）的应用，我们给出了比Berge Hamilton循环的Dirac-type结果中最低度的更低度，由Bermond等人（1976）和Clemens等人提供。 （2016年）。
Dirac (1952) proved that every connected graph of order $n>2k+1$ with minimum degree more than $k$ contains a path of length at least $2k+1$. Erdős and Gallai (1959) showed that every $n$-vertex graph $G$ with average degree more than $k-1$ contains a path of length $k$. The hypergraph extension of the Erdős-Gallai Theorem have been given by Győri, Katona, Lemons~(2016) and Davoodi et al.~(2018). Füredi, Kostochka, and Luo (2019) gave a connected version of the Erdős-Gallai Theorem for hypergraphs. In this paper, we give a hypergraph extension of the Dirac's Theorem: Given positive integers $n,k$ and $r$, let $H$ be a connected $n$-vertex $r$-graph with no Berge path of length $2k+1$. We show that (1) If $k> r\ge 4$ and $n>2k+1$, then $δ_1(H)\le\binom{k}{r-1}$. Furthermore, the equality holds if and only if $S'_r(n,k)\subseteq H\subseteq S_r(n,k)$ or $H\cong S(sK_{k+1}^{(r)},1)$; (2) If $k\ge r\ge 2$ and $n>2k(r-1)$, then $δ_1(H)\le \binom{k}{r-1}$. The result is also a Dirac-type version of the result of Füredi, Kostochka, and Luo. As an application of (1), we give a better lower bound of the minimum degree than the ones in the Dirac-type results for Berge Hamiltonian cycle given by Bermond et al.~(1976) and Clemens et al. (2016), respectively.
