Witness-tree probability conjecture for fully orderable witness trees

A witness tree is built from bad-event labels, with children of a node labeled BB required to have distinct labels B1,,BsB_1,\dots,B_s whose set is orderable to BB. For a tree-structure τ\tau, let P(\text{\tau appears}) denote the probability that it appears, and let w(τ)w(\tau) be the corresponding witness-tree weight. Witness-tree lemma conjecture. If this orderability condition is enforced at every node of τ\tau, then

P(τ appears)w(τ).P(\text{$\tau$ appears})\leq w(\tau).

The paper explains that this would strengthen the analysis of the Swapping Algorithm by controlling witness trees at every node rather than only at the root. Establishing the bound requires fine control over the temporal order of resamplings, which the authors were unable to maintain; the conjecture is presented as an open extension of their witness-tree lemma.

Sources & referencesView supporting material

Primary source

David G. Harris, “New bounds for the Moser-Tardos distribution”, arXiv:1610.09653 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.