Is there a Degenerate Dependency Local Lemma?

Question

The Lovasz Local Lemma has several generalizations, with names usually starting with L, such as Lopsided or Lefthanded. Here I ask whether another possible generalization (for which I could not yet find a name starting with L) holds or not.

Suppose that for some events $\mathbf A$ we have a dependency graph and an assignment $x$ that is degenerate in the sense that $\exists A \in \mathbf A$ such that $\Pr[A] \;\leqslant\; x(A) \prod_{B \in \Gamma(A)} (1-x(B))$ and after deleting $A$ we again have another such event from $\mathbf A\setminus \{A\}$ etc. In other words, I want that the events can be ordered such that $$\Pr[A] \;\leqslant\; x(A) \prod_{\substack{B \in \Gamma(A)\\ B<A}} (1-x(B)).$$

Is this sufficient to guarantee that we can avoid all events?

ps. I don't care about the exact formula, it might hold only with some weaker inequality, that is also OK.

Answer 1

Here is my intuition that it may not be possible.

I am guessing that as in the case of the original LLL, such an inequality would in turn imply a simpler inequality of the following form:

"If the dependency graph is $d$-degenerate and every event has probability at most $p$ and $4pd<1$, then we can avoid all events".

But this latter statement appears to be false, even if the inequality is changed to $4pf(d)<1$ for some large function $f$ of the degeneracy.

For example, consider $n$ events $E_1,\ldots,E_n$, which are independent, each having probability $p$. Consider an event $A$ which is simply the complement of the union of the $E_is$. $Prob[A]=(1-p)^n$.

It is not possible to avoid the $n+1$ events ($E_is$ and $A$). The dependency graph is a star with $A$ being the central node. We have $d=1$, $p$ can be made small enough to satisfy the inequality for any choice of $f$, function of degeneracy. The value of $n$ can be made large enough so that $Prob[A]$ also satisfies the inequality.