论文标题
随机$ k $均匀超图的同构
Isomorphism for Random $k$-Uniform Hypergraphs
论文作者
论文摘要
我们研究随机超图的同构问题。我们证明，对于二项式$ k $ - 均匀的hypergraph $ h_ {n，p; k} $，对于多项式时间是可解决的，对于$ p $。我们还表明它是可解决的W.H.P.对于随机$ r $ - regular，$ k $ - 均匀的超图$ h_ {n，r; k}，r = o（1）$。
We study the isomorphism problem for random hypergraphs. We show that it is solvable in polynomial time for the binomial random $k$-uniform hypergraph $H_{n,p;k}$, for a wide range of $p$. We also show that it is solvable w.h.p. for random $r$-regular, $k$-uniform hypergraphs $H_{n,r;k},r=O(1)$.
