论文标题
在随机超图上种植的匹配问题
Planted matching problems on random hypergraphs
论文作者
论文摘要
我们考虑了推断隐藏在加权随机$ k $ hypergraph中的匹配的问题。我们假设Hyperedges的权重是随机的，并且根据两个不同的密度调节，以下事实，即是否属于隐藏的匹配。我们表明，对于$ k> 2 $，在较大的图形尺寸限制中，信号强度中的算法一阶转换将一个制度分开，在该制度中，隐藏匹配的完全恢复与可能的部分恢复的策略可行。这与已知过渡是连续的$ k = 2 $情况相反。最后，我们考虑了呈现边缘和$ 3 $的流离失所的图形的情况，在$ k = 2 $和$ k = 3 $的情况下进行了插值，我们研究了通过调整相对边缘和超果的相对量的过渡到第一阶的变化。
We consider the problem of inferring a matching hidden in a weighted random $k$-hypergraph. We assume that the hyperedges' weights are random and distributed according to two different densities conditioning on the fact that they belong to the hidden matching, or not. We show that, for $k>2$ and in the large graph size limit, an algorithmic first order transition in the signal strength separates a regime in which a complete recovery of the hidden matching is feasible from a regime in which partial recovery is possible. This is in contrast to the $k=2$ case where the transition is known to be continuous. Finally, we consider the case of graphs presenting a mixture of edges and $3$-hyperedges, interpolating between the $k=2$ and the $k=3$ cases, and we study how the transition changes from continuous to first order by tuning the relative amount of edges and hyperedges.
