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

12/03/2020
by   Zohre Ranjbar-Mojaveri, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset