He li liu wang xia 2017 variable lovasz local lemma

../

theorem_3: He, Li, Liu, Wang and Xia's exact criterion for the variable version of the Lovász local lemma: for a bigraph H and q in (0,1)^n, lambda q lies on the boundary of H exactly when lambda is the optimum of a program over cylinder sets in which variable j takes d_j values, d_j its degree in H.

theorem_4: He, Li, Liu, Wang and Xia's boundary for cyclic bigraphs: for p in (0,1)^n, the least lambda solving one of n explicit recursive equation systems puts lambda p on the boundary of every n-cyclic bigraph.

theorem_5: He, Li, Liu, Wang and Xia's gap criterion: a bigraph H is gapless in the direction of p, so that Shearer's bound for its base graph is tight along p, exactly when an exclusive event system with event-variable graph H realizes each interior multiple of p, or equivalently the boundary multiple.

theorem_6: He, Li, Liu, Wang and Xia's result that when the base graph of an event-variable bigraph is a tree, the variable local lemma region equals Shearer's region for that tree, so variable information gains nothing.

theorem_7: He, Li, Liu, Wang and Xia's result that every n-cyclic event-variable bigraph has a gap: its variable local lemma region is strictly larger than Shearer's region for its base cycle.

theorem_8: He, Li, Liu, Wang and Xia's characterization of the dependency graphs on which every event-variable bigraph is gapless: a graph is a-gapless, no bigraph with it as base graph having a gap, exactly when it is a tree.

theorem_9: He, Li, Liu, Wang and Xia's characterization, presented as settling a question of Kolipaka and Szegedy, of the dependency graphs on which every event-variable bigraph has a gap; the theorem is printed as strongly a-gapful if and only if chordal, while its proof shows that the non-chordal graphs are strongly a-gapful and the chordal ones strongly a-gapless.

---

Kun He, Liang Li, Xingwu Liu, Yuyi Wang, and Mingji Xia, “Variable Version Lovász Local Lemma: Beyond Shearer's Bound,” arXiv:1709.05143v1 (2017), whose first page says that part of the work was published at FOCS 2017 (FOCS 2017, 451–462, DOI 10.1109/FOCS.2017.48). The arXiv record names arXiv's non-exclusive distribution license (arXiv:1709.05143), every other right reserved.

Labels and pages on this card and its result pages are those of arXiv v1 (15 September 2017, 43 pages).

The paper recalls two abstract local lemmas. For a graph $G=([n],E)$ and $p\in(0,1)^n$, Theorem 1 (p. 2), which the paper cites from Spencer (1977), says that $p$ lies in the abstract interior $I_a(G)$ whenever there are $x_1,\ldots,x_n\in(0,1)$ with

$$p_i\leq x_i\prod_{j\in N(i)}(1-x_j) \qquad(i\in[n]).$$

Theorem 2 (p. 2), cited from Shearer (1985), gives the exact criterion: $p\in I_a(G)$ if and only if, for every independent set $S\in\operatorname{Ind}(G)$,

$$\sum_{\substack{T\supseteq S\\T\in\operatorname{Ind}(G)}} (-1)^{|T|-|S|}\prod_{i\in T}p_i>0.$$

The paper's own results concern the variable version, in which the events are generated by independent variables and the dependency structure is a bigraph $H$ of events and variables; its interior $I(H)$ always contains Shearer's region $I_a(G_H)$ for the base graph $G_H$, two events being adjacent there when they share a variable, and $H$ has a gap when the containment is strict. Theorem 3 (pp. 5–6) characterizes the boundary of $I(H)$ by a discretized program, Theorem 4 (p. 6) computes the boundary of every cyclic bigraph, and Theorem 5 (pp. 6–7) gives the gap criterion: for a bigraph $H$ and a vector $p$ of positive reals, $H$ is gapless in the direction of $p$ exactly when, for every $\lambda$ with $\lambda p\in I(H)$, some exclusive variable-generated event system with event-variable graph $H$ has probability vector $\lambda p$, and equivalently when this holds for the one $\lambda$ with $\lambda p\in\partial(H)$. An event system is exclusive when the base graph is a dependency graph of it and adjacent events meet in measure zero (Definition 6, pp. 20–21); gapless in the direction of $p$ means that no $\lambda>0$ has $\lambda p\in I(H)\setminus I_a(G_H)$ (Definition 9, p. 21). Theorems 6 and 7 (p. 7) show that treelike bigraphs are gapless and cyclic bigraphs gapful, and Theorem 8 (p. 7) that a graph is a-gapless exactly when it is a tree. Theorem 9 (p. 7) is printed as "A graph is strongly a-gapful if and only if it is chordal." [sic]; its proof (p. 38) shows that non-chordal graphs are strongly a-gapful and chordal graphs strongly a-gapless. Section 5.2 (pp. 26–28) gives reduction rules that preserve gaps, applied to combinatorial bigraphs in Section 6.1, and Section 7 (pp. 38–39) shows that computing the largest union measure (Theorem 47) and deciding membership in the interior (Theorem 48) are #P-hard.

Read status: claims checked for the results linked below, statements read clause by clause on the printed pages of arXiv v1; no proof is checked step by step.

Results.

• Theorem 3 (pp. 5–6): $\lambda q\in\partial(H)$ exactly when $\lambda$ is the optimum of a program over cylinder sets in which variable $j$ takes $d_j$ values.
• Theorem 4 (p. 6): the boundary of every $n$-cyclic bigraph, as the least root of explicit recursive equation systems.
• Theorem 5 (pp. 6–7): gapless in the direction of $p$ if and only if exclusive systems realize the interior, or the boundary, multiples of $p$.
• Theorem 6 (p. 7): treelike bigraphs are gapless.
• Theorem 7 (p. 7): cyclic bigraphs are gapful.
• Theorem 8 (p. 7): a graph is a-gapless if and only if it is a tree.
• Theorem 9 (p. 7): strong a-gapfulness and chordality, printed with the two classes exchanged relative to its proof.

Bears on. No numbered Erdős problem: the paper names none, and these results are method material for local-lemma analyses.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.