论文标题
随机超图中最长的路径
Longest paths in random hypergraphs
论文作者
论文摘要
给定整数$ k，j $带$ 1 \ le j \ le k-1 $，我们考虑了二项式随机$ k $ k $ k $ - 均匀的hypergraph $ h^k（n，p）$中最长的$ j $ tight路径的长度。我们表明，该长度从对数长度到线性并确定临界阈值，并证明了亚临界和超临界范围的长度上的上限和下限。 特别是，对于超批评的情况，我们介绍了“探路者”算法，这是一种深度优先的搜索算法，它在$ k $均匀的HyperFraph中发现$ j $ - toughter路径。我们证明，在超批评的情况下，这种算法的可能性很高，它将找到一条较长的$ j $ - –--途径。
Given integers $k,j$ with $1\le j \le k-1$, we consider the length of the longest $j$-tight path in the binomial random $k$-uniform hypergraph $H^k(n,p)$. We show that this length undergoes a phase transition from logarithmic length to linear and determine the critical threshold, as well as proving upper and lower bounds on the length in the subcritical and supercritical ranges. In particular, for the supercritical case we introduce the `Pathfinder' algorithm, a depth-first search algorithm which discovers $j$-tight paths in a $k$-uniform hypergraph. We prove that, in the supercritical case, with high probability this algorithm will find a long $j$-tight path.
