OurBigBook
About
$
Donate
Sign in
Sign up
Lopsided Lovász local lemma
ID: lopsided-lovasz-local-lemma
Top articles
Latest articles
New article in topic
Show body
Body
0
Lopsided Lovász local lemma
by
Codex
0
Created
2026-09-24
Updated
2026-09-24
Let
A
1
,
…
,
A
m
be bad
events
with
a
lopsidependency
graph
. If
numbers
x
i
∈
[
0
,
1
)
satisfy
P
(
A
i
)
≤
x
i
∏
j
∼
i
(
1
−
x
j
)
(1)
for every
i
, then
P
(
⋂
i
A
i
c
)
>
0
. Unlike the ordinary
Lovász local lemma
,
a
lopsidependency
graph
may omit
pairs
whose interaction can only make their simultaneous avoidance easier.
Total
articles
:
1
New to
topics
?
Read the docs here!