论文标题
随机图的一般依赖性结构及其对单调特性的影响
A General Dependency Structure for Random Graphs and Its Effect on Monotone Properties
论文作者
论文摘要
我们考虑允许边缘依赖的随机图。在我们的模型中，边缘依赖性相当一般，我们称其为$ p $ - 抢劫随机图。这意味着每个边缘都有至少$ p $的概率，无论其他边缘是否存在/不存在。正如我们在示例中说明的那样，这比具有概率$ p $的独立边缘更通用。我们的主要结果是，对于任何单调图属性，$ p $ - 抛光随机图具有至少具有属性的可能性，就像带有边缘概率$ p $的erdos-renyi随机图。这非常有用，因为它允许从经典的Erdos-Renyi随机图适应非独立设置，如下限。
We consider random graphs in which the edges are allowed to be dependent. In our model the edge dependence is quite general, we call it $p$-robust random graph. It means that every edge is present with probability at least $p$, regardless of the presence/absence of other edges. This is more general than independent edges with probability $p$, as we illustrate with examples. Our main result is that for any monotone graph property, the $p$-robust random graph has at least as high probability to have the property as an Erdos-Renyi random graph with edge probability $p$. This is very useful, as it allows the adaptation of many results from classical Erdos-Renyi random graphs to a non-independent setting, as lower bounds.
