论文标题
浓密的Erdös-Rényi图的密集子图。渐近学，景观和普遍性
Densest Subgraphs of a Dense Erdös-Rényi Graph. Asymptotics, Landscape and Universality
论文作者
论文摘要
我们考虑了估计Erdös-rényi图$ \ Mathbb {g}（n，1/2）$的浓密$ k $节点子图的边缘密度的问题。该问题在制度$ k =θ（\ log n）$和制度$ k =θ（n）$中得到了很好的理解。在前一种情况下，它可以简化为估计最大集团大小及其扩展的问题。在后一种情况下，使用旋转玻璃理论中复杂的方法，已知全部答案符合$ n^{3 \ over 2} $的顺序。中间情况$ k = n^α，α\ in（0,1）$，但是研究并不是很好，这是我们的重点。我们确定，在这种状态下，密度（这是任何$ k $ -node子图支持的最大边数）为$ {1 \ of 4} k^2+{1+o（1）\ over 2} k^{3 \ over 2} k^{3 \ over 2} \ sqrt {\ sqrt {\ sqrt {\ log log（n/k）$，w.h.p.p。作为$ n \ to \ infty $，并在$ o（\ cdot）$下提供了更精致的渐近学，对于$α$的各种范围。这扩展了早期的类似结果，仅当$α$是一个小常数时，才确认这种渐近性。 当权重带有高斯或任意的下高斯分布时，我们将结果扩展到“加权”图的情况。证明基于第二刻的方法结合了浓度界限，高斯案例的borell-tis不平等以及带有有限支持的分布情况的talagrand的不平等（包括$ \ mathbb {g}（n，1/2）$ case）。使用新颖的lindeberg参数对对称版本对一般分布的情况进行处理，该版本将一般案例降低到高斯案例。最后，使用上面的结果，我们对相关的隐藏集团问题进行了景观分析，并确定当集团的大小为$ O（N^{2 \ over 3}）$时，它表现出重叠的间隙属性，证实了先前相关工作中所述的假设。
We consider the problem of estimating the edge density of densest $K$-node subgraphs of an Erdös-Rényi graph $\mathbb{G}(n,1/2)$. The problem is well-understood in the regime $K=Θ(\log n)$ and in the regime $K=Θ(n)$. In the former case it can be reduced to the problem of estimating the size of largest cliques, and its extensions. In the latter case the full answer is known up to the order $n^{3\over 2}$ using sophisticated methods from the theory of spin glasses. The intermediate case $K=n^α, α\in (0,1)$ however is not well studied and this is our focus. We establish that that in this regime the density (that is the maximum number of edges supported by any $K$-node subgraph) is ${1\over 4}K^2+{1+o(1)\over 2}K^{3\over 2}\sqrt{\log (n/K)}$, w.h.p. as $n\to\infty$, and provide more refined asymptotics under the $o(\cdot)$, for various ranges of $α$. This extends earlier similar results where this asymptotics was confirmed only when $α$ is a small constant. We extend our results to the case of ''weighted'' graphs, when the weights have either Gaussian or arbitrary sub-Gaussian distributions. The proofs are based on the second moment method combined with concentration bounds, the Borell-TIS inequality for the Gaussian case and the Talagrand's inequality for the case of distributions with bounded support (including the $\mathbb{G}(n,1/2)$ case). The case of general distribution is treated using a novel symmetrized version of the Lindeberg argument, which reduces the general case to the Gaussian case. Finally, using the results above we conduct the landscape analysis of the related Hidden Clique Problem, and establish that it exhibits an overlap gap property when the size of the clique is $O(n^{2\over 3})$, confirming a hypothesis stated in a previous related work.
