论文标题
在高斯情况下的不均匀随机图的指数界限
Exponential bounds for inhomogeneous random graphs in a Gaussian case
论文作者
论文摘要
等级1不均匀的随机图是ErdősRényi随机图的自然概括。在此概括中，每个节点都有一个重量。然后，存在边缘的概率取决于它连接的节点的权重的乘积。在本文中，我们对等级1不均匀的随机图的大小，重量和盈余给出了精确而均匀的指数界限，其中节点的权重表现得像有限的第四刻的随机变量。我们专注于随机节点的平均程度略大于1的情况，我们将这种情况称为几乎没有超临界状态。这些界限将用于后续文章中，以研究一类随机最小跨越树的一般类别。它们也具有独立的兴趣，因为它们表明这些不均匀的随机图即使在几乎没有超临界状态下也像ErdősRényi随机图一样行为。证据依靠新的浓度界限来进行采样，而无需替换和仔细研究勘探过程。
Rank 1 inhomogeneous random graphs are a natural generalization of Erdős Rényi random graphs. In this generalization each node is given a weight. Then the probability that an edge is present depends on the product of the weights of the nodes it is connecting. In this article, we give precise and uniform exponential bounds on the size, weight and surplus of rank 1 inhomogeneous random graphs where the weights of the nodes behave like a random variable with finite fourth moment. We focus on the case where the mean degree of a random node is slightly larger than 1, we call that case the barely supercritical regime. These bounds will be used in follow up articles to study a general class of random minimum spanning trees. They are also of independent interest since they show that these inhomogeneous random graphs behave like Erdős Rényi random graphs even in a barely supercritical regime. The proof relies on novel concentration bounds for sampling without replacement and a careful study of the exploration process.
