English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A tight criterion under which the abstract version Lov\'asz Local Lemma(abstract-LLL) holds was given by Shearer decades ago. However, little is knownabout that of the variable version LLL (variable-LLL) where events aregenerated by independent random variables, though this model of events isapplicable to almost all applications of LLL. We introduce a necessary andsufficient criterion for variable-LLL, in terms of the probabilities of theevents and the event-variable graph specifying the dependency among the events.Based on this new criterion, we obtain boundaries for two families ofevent-variable graphs, namely, cyclic and treelike bigraphs. These are thefirst two non-trivial cases where the variable-LLL boundary is fullydetermined. As a byproduct, we also provide a universal constructive method tofind a set of events whose union has the maximum probability, given theprobability vector and the event-variable graph. Though it is #P-hard ingeneral to determine variable-LLL boundaries, we can to some extent decidewhether a gap exists between a variable-LLL boundary and the correspondingabstract-LLL boundary. In particular, we show that the gap existence can bedecided without solving Shearer's conditions or checking our variable-LLLcriterion. Equipped with this powerful theorem, we show that there is no gap ifthe base graph of the event-variable graph is a tree, while gap appears if thebase graph has an induced cycle of length at least 4. The problem is almostcompletely solved except when the base graph has only 3-cliques, in which casewe also get partial solutions. A set of reduction rules are established thatfacilitate to infer gap existence of an event-variable graph from known ones.As an application, various event-variable graphs, in particular combinatorialones, are shown to be gapful/gapless.

Variable Version Lov\'asz Local Lemma: Beyond Shearer's Bound