6
$\begingroup$

In order to successfully apply the Lovasz local lemma, one needs the events to be relatively independent. This (sometimes) works well in the $G(n,p)$ model of random graphs, where the presence or absence of edges doesn't affect the events they are not involved in.

However, in the $G(n,m)$ model (where we choose a graph with $n$ vertices and $m$ edges uniformly at random), it seems that nearly every event one could possibly define is dependent (albeit very weakly) on every other event.

My question is, roughly, this: are there any examples of successful applications of the local lemma in the $G(n,m)$ model? I would also be quite happy to learn about generalizations/analogues of the local lemma that might apply to that or any similar context.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ As you probably aware, many results for $G(n,m)$ follow from the results on $G(n,p)$. There are not many results specific to $G(n,m)$ to start with; given that, and the lack of independence, I would be surprised to see direct applications of LLL to $G(n,m)$. $\endgroup$
    – Boris Bukh
    Commented Nov 7, 2019 at 13:45
  • 1
    $\begingroup$ You may already know this, but if the dependencies you're annoyed with are negative, then you may be able to use the "lopsided local lemma." $\endgroup$
    – Timothy Chow
    Commented Nov 8, 2019 at 15:56

2 Answers 2

Reset to default
5
$\begingroup$

This is not a full answer by any means, by likely a bit longer than a comment. The local lemma as it is usually stated doesn't apply nicely to $G(n,m)$ (as you note) due to the fact that the dependency graph has a lot of edges; depending on the situation at hand, it may be the case that these dependencies are extremely weak. The local lemma can still be used, but it has to be a souped-up version that allows for soft dependencies. Scott and Sokal wrote a (massive) paper about the connection between a general family of lattice gas models, the zero-free region of an associated (multivariate) generating function, and the local lemma

https://arxiv.org/abs/cond-mat/0309352

that allows for these sort of soft dependencies. It is likely that many (or even most) local lemma cases that work for $G(n,p)$ can be translated (possibly with lots of work) to a corresponding $G(n,m)$ using concentration arguments and a similarly souped-up local lemma.

Improve this answer
$\endgroup$
0
$\begingroup$

In general, one would prove results for Gnp and then show that those apply to Gnm, for appropriately chosen p. For example, often you can use the poisson approximation for balls and bins as in the book probability and computing chapter 5.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .