A Dirac-type Theorem for Berge Cycles in Random Hypergraphs
A Dirac-type Theorem for Berge Cycles in Random Hypergraphs
复制标题
随机超图中贝格循环的狄拉克型定理
DOI：
10.37236/8611
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Y. Person
中科院分区：
文献类型：
--
作者：
Dennis Clemens;Julia Ehrenmüller;Y. Person
在$n$顶点上的超图的Hamilton Berge循环是由不同顶点$v_1, \ldots, v_n$和不同超边$e_1, \ldots, e_n$组成的交替序列$(v_1, e_1, v_2, \ldots, v_n, e_n)$，使得每个$i\in [n-1]$对应$\{v_1,v_n\}\subseteq e_n$和$\{v_i, v_{i+1}\} \subseteq e_i$。我们证明了二项随机$r$ -一致超图$H^{(r)}(n,p)$中关于Berge环的dirac型定理：对于每一个整数$r \geq 3$、每一个实数$\gamma>0$和$p \geq \frac{\ln^{17r} n}{n^{r-1}}$，渐近几乎肯定地，每一个顶点度最小的生成子图$H \subseteq H^{(r)}(n,p)$$\delta_1(H) \geq \left(\frac{1}{2^{r-1}} + \gamma\right) p \binom{n}{r-1}$都包含一个Hamilton Berge环。最小度条件是渐近紧密的，并且$p$上的界在某个多对数因子范围内是最优的。
A Hamilton Berge cycle of a hypergraph on $n$ vertices is an alternating sequence $(v_1, e_1, v_2, \ldots, v_n, e_n)$ of distinct vertices $v_1, \ldots, v_n$ and distinct hyperedges $e_1, \ldots, e_n$ such that $\{v_1,v_n\}\subseteq e_n$ and $\{v_i, v_{i+1}\} \subseteq e_i$ for every $i\in [n-1]$. We prove the following Dirac-type theorem about Berge cycles in the binomial random $r$-uniform hypergraph $H^{(r)}(n,p)$: for every integer $r \geq 3$, every real $\gamma>0$ and $p \geq \frac{\ln^{17r} n}{n^{r-1}}$ asymptotically almost surely, every spanning subgraph $H \subseteq H^{(r)}(n,p)$ with minimum vertex degree $\delta_1(H) \geq \left(\frac{1}{2^{r-1}} + \gamma\right) p \binom{n}{r-1}$ contains a Hamilton Berge cycle. The minimum degree condition is asymptotically tight and the bound on $p$ is optimal up to some polylogarithmic factor.
稀疏图中的带宽定理
影响因子：
--
作者：
Allen P
通讯作者：
Allen P
对抗性边缘去除后几乎跨越随机图的子图
DOI：
10.1017/s0963548313000199
发表时间：
2013
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
J. Böttcher;Y. Kohayakawa;A. Taraz
通讯作者：
A. Taraz
随机有向图具有稳健的哈密顿量
影响因子：
1
作者：
Hefetz D
通讯作者：
Hefetz D