A General Dependency Structure for Random Graphs and Its Effect on Monotone Properties

Abstract

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.

7 pages