Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs
Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs
复制标题
超图中非线性哈密顿循环的尖锐阈值
DOI：
10.1002/rsa.20919
复制
发表时间：
2019
影响因子：
1
通讯作者：
M. Schacht
中科院分区：
文献类型：
--
作者：
Bhargav P. Narayanan;M. Schacht
对于正整数r>；ℓ，如果一个r-一致超图存在其顶点的循环排序，使得它的每条边都由r个连续的顶点组成，并且使得每一对连续的边(以边的自然顺序)正好在ℓ点中相交，则称r-一致超图为ℓ-圈；当ℓ=1时，这样的圈称为线性，当ℓ&>1时称为非线性。我们确定了非线性哈密顿圈的尖锐阈值，并证明了对所有r&>；ℓ>；1，在n个顶点的随机r-一致超图中出现哈密顿ℓ圈的门限Pr，ℓ∗(N)是尖锐的，并由Pr，λ(N)=ł(r，−ℓ)(En)rλ给出。这解决了Dudek和Frieze在2011.10中提出的几个问题
For positive integers r>ℓ, an r‐uniform hypergraph is called an ℓ‐cycle if there exists a cyclic ordering of its vertices such that each of its edges consists of r consecutive vertices, and such that every pair of consecutive edges (in the natural ordering of the edges) intersect in precisely ℓ vertices; such cycles are said to be linear when ℓ=1, and nonlinear when ℓ>1. We determine the sharp threshold for nonlinear Hamiltonian cycles and show that for all r>ℓ>1, the threshold pr,ℓ∗(n) for the appearance of a Hamiltonian ℓ‐cycle in the random r‐uniform hypergraph on n vertices is sharp and given by pr,ℓ∗(n)=λ(r,ł)(en)r−ℓ for an explicitly specified function λ. This resolves several questions raised by Dudek and Frieze in 2011.10