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.
翻译：我们考虑允许边缘依赖的随机图形。 在我们的模型中, 边缘依赖性相当一般, 我们称之为 $p$- robust 随机图形。 这意味着每个边缘都存在概率至少为$p$, 不论其它边缘的存在/ 不存在与否。 这比我们用示例来说明的具有概率为$p$的独立边缘更为一般。 我们的主要结果就是, 对于任何单调图形属性, $p$- robust 随机图形拥有该属性的可能性至少和 Erdos- Renyi 随机图一样高, 其边缘概率为$p$。 这非常有用, 因为它允许将古典 Erdos- Renyi 随机图表的许多结果作为较低范围, 用于非独立设置 。
相关内容
微信扫码咨询专知VIP会员