Commutativity in the Algorithmic Lovász Local Lemma
Vladimir Kolmogorov

arXiv:1506.08547v7 [cs.DS] 13 Aug 2016

Institute of Science and Technology Austria
vnk@ist.ac.at

Abstract
We consider the recent formulation of the Algorithmic Lovász Local Lemma [9, 2] for finding
objects that avoid “bad features”, or “flaws”. It extends the Moser-Tardos resampling algorithm [16] to more general discrete spaces. At each step the method picks a flaw present in the
current state and “resamples” it using a “resampling oracle” provided by the user. However, it
is less flexible than the Moser-Tardos method since [9, 2] require a specific flaw selection rule,
whereas [16] allows an arbitrary rule (and thus can potentially be implemented more efficiently).
We formulate a new “commutativity” condition, and prove that it is sufficient for an arbitrary
rule to work. It also enables an efficient parallelization under an additional assumption. We
then show that existing resampling oracles for perfect matchings and permutations do satisfy
this condition.
Finally, we generalize the precondition in [2] (in the case of symmetric potential causality
graphs). This unifies special cases that previously were treated separately.

1

Introduction

Let Ω be a (large) set of objects and F be a set of flaws, where a flaw f ∈ F is some non-empty set
of “bad” objects, i.e. f ⊆ Ω. Flaw f is said to be present in σ if σ ∈ f . Let Fσ = {f ∈ F | σ ∈ f }
be the set of flaws present in σ. Object σ is called flawless if Fσ = ∅.
The existence of flawless objects can often be shown via a probabilistic method. First, a probability measure ω on Ω is introduced, then flaws in F become (bad) events that should be avoided.
Proving the existence of a flawless object is now equivalent to showing that the probability of avoiding all bad events is positive. This holds if, for example, all events f ∈ F are independent and the
probability of each f is smaller than 1. The well-known Lovász Local Lemma (LLL) [5] is a powerful tool that can handle a (limited) dependency between the events. Roughly speaking, it states
that if the dependency graph is sparse enough (e.g. has a bounded degree) and the probabilities of
individual bad events are sufficiently small then a flawless object is guaranteed to exist.
LLL has been the subject of intensive research, see e.g. [20] for a relatively recent survey. One
of the milestone results was the constructive version of LLL by Moser and Tardos [16]. It applies to
the variable model in which Ω = X1 × . . . × Xn for some discrete sets Xi , event f depends on a small
subset of variables denoted as vbl(f ) ⊆ [n], and two events f, g are declared to be dependent if
vbl(f ) ∩ vbl(g) 6= ∅. The algorithm proposed in [16] is strikingly simple: (i) sample each variable
σi for i ∈ [n] according to its distribution; (ii) while Fσ is non-empty, pick an arbitrary flaw f ∈ Fσ
and resample all variables σi for i ∈ vbl(f ). Moser and Tardos proved that if the LLL condition
in [5] is satisfied then the expected number of resampling is small (polynomial for most of the
known applications).
The recent development has been extending algorithmic LLL beyond the variable model, and
in particular to non-Cartesian spaces. The first such work was by Harris and Srinivasan [8], who
1

considered the space of permutations. Achlioptas and Iliopoulos [1] introduced a more abstract
framework where the behaviour of the algorithm is specified by a certain multigraph. Harvey
and Vondrák proposed a framework with regenerating resampling oracles [9], providing a more
direct connection to LLL. Achlioptas and Iliopoulos [2] extended the framework to more general
resampling oracles.
In this paper we study this setting from [9, 2]. It does not assume any particular structure on
sets Ω and F . Instead, for each object σ ∈ Ω and flaw f ∈ Fσ the user must provide a “resampling
oracle” specified by a set of actions A(f, σ) ⊆ Ω that can be taken to “address” flaw f , and a
probability distribution ρ(σ 0 |f, σ) over σ 0 ∈ A(f, σ). At each step the algorithm selects a certain
flaw f ∈ Fσ , samples an action σ 0 ∈ A(f, σ) according to ρ(σ 0 |f, σ), and goes there. This framework
captures the Moser-Tardos algorithm [16], and can also handle other scenarios such as permutations
and perfect matchings (in which case Ω cannot be expressed as a Cartesian product).
One intriguing difference between the methods of [16] and [1, 9, 2] is that [16] allows an arbitrary
rule for selecting a flaw f ∈ Fσ , whereas [1, 9, 2] require a specific rule (which depends on a
permutation π of F chosen in advance)1 . We will say that a resampling algorithm is flexible if it is
guaranteed to work with any flaw selection rule. We argue that flexibility can lead to a much more
efficient practical implementation: it is not necessary to examine all flaws in Fσ , the first found
flaw will suffice. If the list of current flaws is updated dynamically then flexibility could potentially
eliminate the need for a costly data structure (such as a priority queue) and thus save a factor
of Θ(log n) in the complexity. The rule may also affect the number of resamplings in practice;
experimentally, the selection process matters, as noted in [20].
Achlioptas and Iliopoulos discuss flaw selection rules in [1, Section 4.3], and remark that they
do not see how to accommodate arbitrary rules in their framework. It is known, however, that
in special cases flexible rules can be used even beyond the variable model. Namely, through a
lengthy and a complicated analysis Harris and Srinivasan [8] managed to show the correctness of
a resampling algorithm for permutations, and did not make assumptions on the flaw selection rule
in their proof. They also proved a better bound for the parallel version of the algorithm.
This paper aims to understand which properties of the problem enable flexibility and parallelism.
Our contributions are as follows.
• We formulate a new condition that we call “commutativity”, and prove that it is sufficient
for flexibility.
• We prove that it gives a better bound on the number of rounds of the parallel version of the
algorithm. In particular, we show how to use commutativity for handling “partial execution
logs” instead of “full execution logs” (which is required for analyzing the parallel version).
• We show that existing resampling oracles for permutations [8] and perfect matchings in
complete graphs [9] are commutative. (In fact, we treat both cases in a single framework).
Thus, we provide a simpler proof of the result in [8] and generalize it to other settings,
in particular to perfect matchings in certain graphs (for which existing algorithms require
specific rules).
• We generalize the condition in [2] for the algorithmic LLL to work (in the case of symmetric potential causality graphs). The new condition unifies special cases that were treated
separately in [2].
To our knowledge, our commutativity condition captures all previously known cases when the flaw
selection rules was allowed to be arbitrary.
1

The papers [1, 2] actually allowed more freedom in the choice of permutation π, e.g. it may depend on the
iteration number. However, once π has been chosen, the algorithm should still examine some “current” set of flaws
and pick the lowest one with respect to π.

2

Other related work Applications that involve non-Cartesian spaces Ω (such as permutations,
matchings and spanning trees) have often been tackled via the Lopsided LLL [6]; we refer to [14, 15]
for a comprehensive survey. On the level of techniques there is some connection between this paper
and a recent work by Knuth [10]; we discuss this in Section 3.

2

Background and preliminaries

First, we give a formal description of the algorithm from [9, 2]. Assume that for each object
σ ∈ Ω and each flaw f ∈ Fσ there is a non-empty set of actions A(f, σ) ⊆ Ω that can be taken
for “addressing” flaw f at σ, and a probability distribution ρ(σ 0 |f, σ) over σ 0 ∈ A(f, σ). Note, by
definition A(f, σ) is the support of distribution ρ(·|f, σ). The collection of all resampling oracles
will be denoted as ρ. We fix some probability distribution ω on Ω with ω(σ) > 0 for all σ ∈ Ω
(it will be used later for formulating various conditions). Note that our notation is quite different
from that of Harvey and Vondrák [9].2 The algorithm can now be stated as follows.
Algorithm 1 Random walk. Input: initial distribution ω init over Ω, strategy Λ.
1: sample σ ∈ Ω according to ω init
2: while Fσ non-empty do
3:
select flaw f ∈ Fσ according to Λ
4:
sample σ 0 ∈ A(f, σ) according to distribution ρ(σ 0 |f, σ), set σ ← σ 0 .
5: end while
Clearly, if the algorithm terminates then it produces a flawless object σ. The works [1, 9, 2] used
specific strategies Λ. As stated in the introduction, our goal is to understand when an arbitrary
strategy can be used. This means that flaw f in line 3 is selected according to some distribution
which is a function of the entire past execution history3 . Note that if flaw f ∈ Fσ in line 3 depends
only on σ then the algorithm can be viewed a random walk in a Markov chain with states Ω, while
in a more general case the walk can be non-Markovian.

2.1

Walks and the potential causality graph
f

We say that σ → σ 0 is a (valid) walk if it is possible to get from state σ to σ 0 by “addressing” flaw
f as described in the algorithm, i.e. if two conditions hold: f ∈ Fσ and σ 0 ∈ A(f, σ). Whenever we
f

write σ → σ 0 , we mean that it is a valid walk.
In many applications resampling oracles satisfy a special condition called atomicity [1].
Definition 1. ρ is called atomic if for any f ∈ F and σ 0 ∈ Ω there exists at most one object σ ∈ Ω
f

such that σ → σ 0 .
Next, we need to describe “dependences” between flaws in F . Let ∼ be some symmetric relation
on F (so that (F, ∼) is an undirected graph). It is assumed to be fixed throughout the paper. For
a flaw f ∈ F let Γ(f ) = {g ∈ F | f ∼ g} be the set of neighbors of f . Note, we may or may not
have f ∼
may not contain f . We will denote Γ+ (f ) = Γ(f ) ∪ {f }, and also
Sf , and so Γ(f ) +may or S
Γ(S) = f ∈S Γ(f ) and Γ (S) = f ∈S Γ+ (f ) for a subset S ⊆ F .
2
“Flaws” f correspond to “bad events” Ei in [9]. The distribution over Ω was denoted in [9] as µ, the states of
Ω as ω, and the resampling oracle for the bad event Ei at state ω ∈ Ω as ri (ω).
3
The description of the algorithm in [16] says “pick an arbitrary violated event”. This is consistent with our
definition of an “arbitrary strategy”: in the analysis Moser and Tardos mention that this selection must come from
some fixed procedure (either deterministic or randomized), so that expected values are well-defined.

3

Definition 2. Undirected graph (F, ∼) is called a potential causality graph for ρ if for any walk
f

σ → σ 0 there holds Fσ0 ⊆ (Fσ − {f }) ∪ Γ(f ).
In other words, Γ(f ) must contain all flaws that can appear after addressing flaw f at some
state. Also, Γ(f ) must contain f if addressing f at some state can fail to eradicate f .
Note that in Definition 2 we deviated slightly from [1, 2]: in their analysis the potential causality
graph was directed and therefore in certain cases could capture more information about D. While
directed graphs do matter in some applications (see examples in [1, 2]), we believe that in a typical
application the potential causality relation is symmetric. Using an undirected graph will be essential
for incorporating commutativity.
A subset S ⊆ F will be called independent if for any distinct f, g ∈ S we have f  g. (Thus,
loops f ∼ f in the graph (F, ∼) do not affect the definition of independence). For a subset S ⊆ F
we denote Ind(S) = {T ⊆ S | T is independent}.

2.2

Commutativity

We now formulate new conditions that will allow an arbitrary flaw selection rule to be used.
Definition 3. (ρ, ∼) is called weakly commutative if there exists a mapping SWAP that sends any
f

g

g

f

walk σ1 → σ2 → σ3 with f  g to another valid walk σ1 → σ20 → σ3 , and this mapping is injective.
Note that in the atomic case the definition can be simplified. Namely, (ρ, ∼) is weakly commutative if and only if it satisfies the following condition:
f

g

g

f

• For any walk σ1 → σ2 → σ3 with f  g there exists state σ20 ∈ Ω such that σ1 → σ20 → σ3 is
also a walk.
Indeed, by atomicity the state σ20 is unique, and so mapping SWAP in Definition 3 is constructed in
a natural way. This mapping is reversible and thus injective.
For several results we will also need a stronger property.
Definition 4. (ρ, ∼) is called strongly commutative (or just commutative) if for any walk τ =
f

g

g

f

σ1 → σ2 → σ3 with f  g and SWAP(τ ) = σ1 → σ20 → σ3 there holds
ρ(σ2 |f, σ1 )ρ(σ3 |g, σ2 ) = ρ(σ20 |g, σ1 )ρ(σ3 |f, σ20 )

(1)

It is straightforward to check that strong commutativity holds in the variable model of Moser
f

g

and Tardos. In fact, an additional property holds: for any σ1 → σ2 → σ3 with f  g there
g

f

exists exactly one state σ20 ∈ Ω such that σ1 → σ20 → σ3 . Checking strong commutativity for
non-Cartesian spaces Ω is more involved; we refer to Section 6 for details.

2.3

Parallel version

We will also consider the following version of the algorithm (see Algorithm 2). It is equivalent to
the parallel algorithm of Moser and Tardos [16] in the case of the variable model, and to the parallel
algorithm of Harris and Srinivasan [8] in the case of permutations. It is also closely related to the
“MaximalSetResample” algorithm of Harvey and Vondrák [9] (see below).
Lines 3-8 will be called a round. In some cases each round admits an efficient parallel implementation (with a polylogarithmic running time). For example, this holds in the variable model of
Moser and Tardos [16]. Also, Harris and Srinivasan [8] presented an efficient implementation for
permutations. Accordingly, we will be interested in the number of rounds of the algorithm.
4

Algorithm 2 Parallel random walk.
1: sampe σ ∈ Ω according to distribution ω init
2: while Fσ non-empty do
3:
set I = ∅
4:
while set Fσ − Γ+ (I) is non-empty do
5:
pick some f ∈ Fσ − Γ+ (I)
6:
sample σ 0 ∈ A(f, σ) according to ρ(σ 0 |f, σ), set σ ← σ 0 .
7:
set I ← I ∪ {f }
8:
end while
9: end while
Note, during round r set Fσ − Γ+ (I) in line 5 shrinks from iteration to iteration (and so flaw f
in line 5 satisfies f ∈ Fσr , where σr is the state in the beginning of round r). This property can be
easily verified using induction and Definition 2.
π-stable strategy Let us fix a total order π on F defined by some permutation π of F . Consider
a version of Algorithm 2 where flaw f in line 5 is selected as the lowest flaw in Fσ − Γ+ (I) (with
respect to π ). This corresponds to Algorithm 1 with a specific strategy Λ; this strategy will be
called π-stable. It coincides with the MaximalSetResample algorithm of Harvey and Vondrák [9].
Although we focus on the commutative case, we will also state results for π-stable strategies
since they follow automatically from the proof (which is based on the analysis of π-stable walks).

2.4

Algorithmic LLL conditions

In this section we formulate sufficient conditions under which a flawless object will be guaranteed to
exist. The conditions involve two vectors, λ and µ. Roughly speaking, λ characterizes resampling
oracles and µ characterizes graph (F, ∼).
Definition 5. The pair (ρ, ∼) is said to satisfy Algorithmic LLL conditions if there exist vectors
λ, µ ∈ R|F | such that
X

λf ≥

ρ(σ 0 |f, σ)

σ∈f :σ 0 ∈A(f,σ)

λf
µf

X

ω(σ)
ω(σ 0 )

µ(S) ≤ θ

∀f ∈ F, σ 0 ∈ Ω

(2a)

∀f ∈ F

(2b)

S∈Ind(Γ(f ))

where θ ∈ (0, 1) is some constant and µ(S) =

Q

g∈S

µg .

Of course, vector λ can be easily eliminated from (2). However, it is convenient to have it
explicitly since in many cases it has a natural interpretation. Achlioptas and Iliopoulos [2] called λ
flaw charges, though instead of (2a) they used slightly stronger conditions. Namely, they considered
the following cases; it is straightforward to check that in each one of them vector λ satisfies (2a):
• The case from their earlier work [1], which in the current terminology can be described as
follows: ω is a uniform distribution over Ω, ρ(·|f, σ) is a uniform distribution over A(f, σ),
and ρ is atomic. They then defined λf = 1/ minσ∈f |A(f, σ)|.
• Regenerating resampling oracles of Harvey and Vondrák [9] specified by the equation
1 X
ρ(σ 0 |f, σ)ω(σ) = ω(σ 0 )
ω(f )
σ∈f

5

∀f ∈ F, σ 0 ∈ Ω

P
where ω(f ) = σ∈f ω(σ). In this case Achlioptas and Iliopoulos [2] defined λf = ω(f ).
• In the general case, [2] defined flaw charges via


ω(σ)
0
ρ(σ |f, σ)
λf = bf
max
ω(σ 0 )
σ∈f,σ 0 ∈A(f,σ)
where bf = max
|{σ ∈ f : σ 0 ∈ A(f, σ)}|.
0
σ ∈Ω

Remark 1. An alternative condition that appeared in the literature (for certain λ’s) is
λf
µf

X
S⊆Γ(f )

µ(S) =

λf Y
(1 + µg ) ≤ θ
µf

(3)

g∈Γ(f )

Clearly, (2b) is weaker than (3). We mention that (3) is analogous to the original LLL condition
in [5], while (2b) corresponds to the cluster expansion improvement by Bissacot et al. [3] (with
the matching algorithmic version by Pedgen [18] who considered the variable model of Moser and
Tardos). It is known that the cluster expansion version can give better results for some applications,
see e.g. [4, 17, 9].
Shearer’s condition Shearer [19] gave a sufficient and necessary condition for a general LLL
to hold for a given dependency graph. Kolipaka and Szegedy [11] showed that this condition is
sufficient for the Moser-Tardos algorithm, while Harvey and Vondrák [9] generalized the analysis
to regenerating resampling oracles. We will show that the same analysis holds for the framework
considered in this paper.
Q
Consider vector p ∈ R|F | . For a subset S ⊆ F denote pS = f ∈S pf ; this is a monomial in
variables {pf | f ∈ F }. Also, define polynomial qS as follows:
X
qS = qS (p) =
(−1)|I|−|S| pI
(4)
I:S⊆I∈Ind(F )

Definition 6. Vector p is said to satisfy the Shearer’s condition if qS (p) ≥ 0 for all S ⊆ F , and
q∅ (p) > 0.
The pair (ρ, ∼) is said to satisfy Shearer’s condition if there exist vector p satisfying Shearer’s
condition, vector λ satisfying (2a), and a constant θ ∈ (0, 1) such that λf ≤ θ · pf for all f ∈ F .

3

Our results

First, we state our results for the sequential version (Algorithm 1). Unless mentioned otherwise,
the flaw selection strategy and the initial distribution ω init are assumed to be arbitrary.
Theorem 7. Suppose that (ρ, ∼) satisfies either condition (2) or the Shearer’s condition, and one
of the following holds:
(a) Algorithm 1 uses a π-stable strategy.
(b) (ρ, ∼) is weakly commutative and atomic.
(c) (ρ, ∼) is strongly commutative.
Define
(S
ω init (σ)
σ∈supp(ω init ) Ind(Fσ ) in cases (a,b)
init
init
γ
= max
,
Ind
=
σ∈Ω
ω(σ)
Ind(F )
in the case (c)
6

where supp(ω init ) = {σ ∈ Ω|ω init (σ) > 0} is the support of ω init . The probability that Algorithm 1
produces a flawless object in fewer than T + r steps is at least 1 − θr where


X
1
log γ init + log
µ(R)
(5)
T =
log θ−1
init
R∈Ind

and µ(R) =
condition).

Q

f ∈R µf

(in the case of condition (2)) or µ(R) =

qR (p)
q∅ (p)

(in the case of the Shearer’s

Note that part (a) of Theorem 7 is a minor variation of existing results [9, 2] (except that our
precondition (2a) unifies conditions in previous works - see Section 2.4):
• Harvey and Vondrák [9] proved Theorem 7(a) in the case of regenerating oracles and distributions ω init = ω, with a slightly different expression for T .
• Achlioptas and Iliopoulos [2] proved the result for the “RecursiveWalk” strategy in the
special cases described in Section 2.4 (and assuming condition (2b)).
Parts (b,c) are new results.
Remark 2. The possibility of using distribution ω init which is different from ω was first proposed
by Achlioptas and Iliopoulos in [1]. Namely, they used a distribution with |supp(ω init )| = 1, and
later extended it to arbitrary distributions ω init in [2]. There is a trade-off in choosing ω init :
smaller supp(ω init ) leads to a smaller set Indinit but increases the constant γ init . It is argued
in [2] that using ω init 6= ω can be beneficial when sampling from ω is a difficult problem, or when
the number of flaws is exponentially large.
Next, we analyze the parallel version.
Theorem 8. Suppose that (ρ, ∼) satisfies either condition (2) or the Shearer’s condition, and is
strongly commutative. Then the probability that Algorithm 2 produces a flawless object in fewer
than T + r rounds is at least 1 − θr where


X
1
log γ init + log
T =
µf 
(6)
log θ−1
f ∈F

where γ init is the constant from Theorem 7, and µf =
tion).

q{f } (p)
q∅ (p)

(in the case of the Shearer’s condi-

Our techniques The general idea of the proofs is to construct a “swapping mapping” that
transforms “walks” (which are possible executions of the algorithm) to some canonical form by
applying swap operations from Definition 3. Importantly, we need to make sure that the mapping
is injective: this will guarantee that the sum over original walks is smaller or equal than the sum over
“canonical walks”. We then upper-bound the latter sum using some standard techniques [11, 9].
We use two approaches:
1. Theorem 7(b): transforming walks to “forward stable sequences” (a forward-looking analysis). This works only in the atomic case (under the weak commutativity assumption), and
can make use of the knowledge of the set supp(ω init ), leading to a tighter definition of the
set Indinit .

7

2. Theorems 7(c) and 8: transforming walks to “backward stable sequences” (a backwardlooking analysis). This works in the non-atomic cases, but requires strong commutativity.
In this approach the “roots” of stable sequences are on the right, and have no connection to
ω init ; this means that we must use Indinit = Ind(F ).
Analyzing the parallel version requires dealing with “partial execution logs” instead of “full
execution logs”. It appears that this is possible only with backward sequences.
Note that previously a backward-looking analysis (with either “stable sequences” or “witness
trees”) was used for the variable model of Moser and Tardos [16, 11, 18], while a forward-looking
analysis was used for LLL versions on non-Cartesian spaces [1, 9, 2] and also on Cartesian spaces [7].
After the first version of this work [12] we learned about a recent book draft by Knuth [10].
He considers the variable model of Moser-Tardos, and gives an alternative proof of algorithm’s
correctness which is also based on swapping arguments (justified by a technique of “coupling” two
random sources, similar to [16]). We emphasize that we go beyond the variable model, in which
case justifying “swapping” seems to require different techniques.
The proofs of Theorems 7 and 8 are given below in Sections 4 and 5. (A brief overview of these
proofs can be found in [13]). The most technical part is probably constructing an injective swapping
mapping for transforming to backward stable sequences (proved in Section 5.6). In Section 6 we
describe our third result, which is a proof of strong commutativity of some existing resampling
oracles. We also consider one application, namely rainbow matchings in complete graphs.

4

Proof of Theorem 7(a)

First, we will describe those results that do not involve commutativity. In particular, we will
prove Theorem 7(a). Techniques used in this section are a combination of ideas from previous
works [11, 1, 9, 2].
We write f ∼
= g for flaws f, g ∈ F if either f ∼ g or f = g (and f 6∼
= g otherwise).
w1
wt
A walk of length t is a sequence τ = σ1 → σ2 . . . σt → σt+1 such that wi ∈ Fσi and σi+1 ∈
A(wi , σi ) for i ∈ [t]. Its length is denoted as |τ | = t. For such a walk we define quantity
Y
p(τ ) = ω init (σ1 ) ·
ρ(σi+1 |wi , σi )
(7)
i∈[t]

Let Λ be the strategy for selecting flaws used in Algorithm 1. We assume in the analysis that
wi−1
w
w
this strategy is deterministic, i.e. the flaw wi in a walk τ = σ1 →1 . . . → σi →i . . . is uniquely
wi−1
w
determined by the previous history τi = σ1 →1 . . . → σi . This assumption can be made w.l.o.g.:
if Λ is randomized (i.e. a distribution over some set of deterministic strategies) then the claim of
Theorem 7 can be obtained by taking the appropriate expectation over strategies (whose number
is finite for a fixed finite t). A similar argument applies to Theorem 8.
A walk τ of length t that can be produced by Algorithm 1 with a positive probability will be
called a bad t-trajectory. Equivalently, it is a walk that starts at a state σ ∈ supp(ω init ) and follows
strategy Λ. Note that it goes only through flawed states (except possibly the last state). Let Bad(t)
be the set of all bad t-trajectories. Clearly, for any τ ∈ Bad(t) the probability that the algorithm
will produce τ equals p(τ ), as defined in (7). This gives
P
Proposition 9. The probability that Algorithm 1 takes t steps or more equals τ ∈Bad(t) p(τ ).
•

If W = w1 . . . wt is the complete sequence of flaws in a walk τ then we will write τ = W . If
we want to indicate certain intermediate states of τ then we will write them in square brackets at
•
appropriate positions, e.g. τ = [σ1 ]w1 w2 [σ3 ]w4 w5 [σ6 ].
8

In general, a sequence of flaws will be called a word, and a sequence of flaws together with some
intermediate states (such as [σ1 ]w1 w2 [σ3 ]w4 w5 [σ6 ]) will be called a pattern. For a pattern X we
•
define hXi = {τ | τ = X} to be the set of walks consistent with X. The length of X (i.e. the number
of flaws in it) is denoted as |X|.
Lemma 10. For any word W and state σ we have
X
p(τ ) ≤ γ init · λW · ω(σ)

(8a)

τ ∈hW [σ]i

X

p(τ ) ≤ γ init · λW

(8b)

τ ∈hW i

Q
where for a word W = w1 . . . wt we denoted λW = i∈[t] λwi . (As described in the previous paragraph, hW [σ]i is the set of walks τ whose sequence of flaws is W and the last state is σ.)
Proof. Summing (8a) over σ ∈ Ω gives (8b), so it suffices to prove the former inequality. We use
induction on the length of W . If W is empty then hW [σ]i contains a single walk τ with the state
σ; we then have p(τ ) = ω init (σ), and the claim follows from the definition of γ init in Theorem 7.
This establishes the base case. Now consider a word W 0 = W f with f ∈ F and a state σ 0 . We can
write
X
X
X
p(τ 0 ) =
p(τ ) · ρ(σ 0 |f, σ)
τ 0 ∈hW 0 [σ 0 ]i

σ:σ 0 ∈A(f,σ) τ ∈hW [σ]i
(a)

≤

X

(b)

γ init · λW · ω(σ) · ρ(σ 0 |f, σ) ≤ γ init · λW · [λf · ω(σ 0 )] = γ init · λW 0 · ω(σ 0 )

σ:σ 0 ∈A(f,σ)

where (a) is by the induction hypothesis, and (b) follows from (2a). This gives the induction step,
and thus concludes the proof of the lemma.
The following technical result will also be useful.
•

Lemma 11. Consider a walk τ = . . . [σ]u1 . . . uk . . . where k ≥ 1. Suppose at least one of the
following holds:
(a) uk is not present in σ.
(b) u1 = uk .
Then there exists index i ∈ [k − 1] such that ui ∼ uk .
u

uk−1

u

u

Proof. We will assume that τ = . . . σ1 →1 σ2 →2 . . . → σk →k σk+1 . . . where σ1 = σ.
u
(a) Flaw uk is present in σk (since σk →k σk+1 is a walk) but not in σ1 . Thus, there must exist
u
index i ∈ [k − 1] such that uk is present in σi+1 but not in σi . We know that σi →i σi+1 is a valid
walk. Thus, addressing ui have caused uk to appear, and therefore ui ∼ uk .
(b) Assume that uk is present in σ1 (otherwise the claim holds by (a)). If uk is present in σ2
then uk ∼ uk (since addressing u1 = uk at state σ1 did not eliminate flaw uk ). Otherwise, if uk is
not present in σ2 , we can apply part (a) and conclude that ui ∼ uk for some i ∈ [2, k − 1].

4.1

Stable walks and stable sequences

As shown in [9], if Λ is a π-stable strategy then walks τ that it produces have a special structure:
the word W corresponding to τ can be uniquely described by a stable sequence. This section gives
all necessary definitions.
9

Definition 12. A sequence of sets ϕ = (I1 , . . . , Is ) with s ≥ 1 is called stable if Ir ∈ Ind(F ) for
each r ∈ [s] and Ir+1 ⊆ Γ+ (Ir ) for each r ∈ [s − 1].
Definition 13. A word W = w1 . . . wt is called stable if it can be partitioned into non-empty words
as W = W1 . . . Ws such that flaws in each word Wr are distinct, and the sequence (I1 , . . . , Is ) is
stable where Ir is the set of flaws in Wr (for r ∈ [s]). If in addition each word Wr = wi . . . wj
satisfies wi ≺π . . . ≺π wj then W is called π-stable.
•
A walk τ = W is called stable (π-stable) if the word W is stable (π-stable).
It can be seen that for a stable word the partitioning in Definition 13 is unique, and can be
obtained by the following algorithm. Start with one segment containing w1 , and then for i = 2, . . . , t
do the following: if there exists flaw wk in the last segment with wk ∼
= wi then start a new segment
containing wi , otherwise add wi to the last segment. (If this algorithm is applied to an arbitrary
word W then it may fail to produce a stable sequence since in the latter case, when wi is added to
the last segment Ir , wi may not belong to Γ+ (Ir−1 )).
Let Stabπ be the set of π-stable words W that satisfy the following condition:
•
•
• There exists walk τ such that either τ = W or τ = REV[W ], where REV[W ] = wt . . . w1 is the
reverse of word W = w1 . . . wt .
For a stable word W let RW be the first set (the “root”) of the stable sequence ϕ = (I1 , . . . , Is )
corresponding to W , i.e. RW = I1 . (If W is empty then RW = ∅). Denote Stabπ (R) = {W ∈
Stabπ : RW = R}, Stabπ (t) = {W ∈ Stabπ : |W | ≥ t} and Stabπ (R, t) = Stabπ (R) ∩ Stabπ (t).
The following result is proven in Section A using techniques from [11, 9].
Theorem 14. Suppose that (ρ, ∼) satisfies either the cluster expansion condition (2b) or the
Shearer’s condition from Definition 6. Then
X
λW ≤ µ(R) · θt
∀R ∈ Ind(F )
(9)
W ∈Stabπ (R,t)

4.2

Proof of Theorem 7(a): a wrap-up

It is not difficult to show that a π-stable strategy produces π-stable walks (see the statement below).
The reverse, however, is not necessary true: it may e.g. happen that some flaw f does not appear
in a π-stable walk τ , but is present in all states of τ and would have been selected by any π-stable
strategy.
Proposition 15. Suppose that strategy Λ is implemented as in Algorithm 2 (with a deterministic
choice in line 5). Then any τ ∈ Bad(t) is a stable walk. If in addition Λ is a π-stable strategy (i.e.
flaw f in line 5 is chosen as the lowest flaw in Fσ − Γ+ (I) with respect to π ) then any τ ∈ Bad(t)
is a π-stable walk.
Proof. Let s be the number of rounds of Algorithm 2 that produced walk τ , and Ir ⊆ [s] be the set
of flaws addressed in round r ∈ [s], or equivalently the set I at the end of round r (with a possible
exception for r = s: Ir may correspond to the “intermediate” set I, depending on where walk τ
•
was “cut”). By this definition, we have τ = W1 . . . Ws where Wr is a word containing the flaws in
Ir in some order (with |Wr | = |Ir |). We will prove that (I1 , . . . , Is ) is a stable sequence; this will
imply the first claim of the proposition.
The independence of each set Ir follows directly from the construction. Consider r ∈ [2, s], and
•
let τ = . . . Wr−1 [σ]Wr . . .. We need to show that for each flaw f present in Wr (i.e. f ∈ Ir ) we have
f ∈ Γ+ (Ir−1 ). Suppose it is not the case. Lemma 11(a) gives that f is present in σ. Therefore, set
10

Fσ − Γ+ (Ir−1 ) is non-empty (it contains σ). But then round r − 1 would not have terminated at
the state σ - a contradiction.
It remains to consider the case when flaw f in line 5 is chosen as the lowest flaw in Fσ − Γ+ (I)
with respect to π . Consider round r, and let Wr = wi . . . wj . Definition 2 and an induction
argument show that during this round set Fσ − Γ+ (I) in line 5 shrinks from iteration to iteration.
This implies that wi ≺π . . . ≺π wj , as desired.
We also need the following observation.
•

Lemma 16. If τ = W is a π-stable walk starting at state σ1 then RW ∈ Ind(Fσ1 ).
Proof. By definition of a stable word, set RW is independent, and corresponds to some prefix
w1 . . . wk of the word W . It remains to show that for each i ∈ [k] we have wi ∈ Fσ1 . This follows
from Lemma 11(a) and the condition that wj  wi for all j ∈ [i − 1].
We now have all ingredients to prove part (a) of Theorem 7. Consider Algorithm 1 with a
•
π-stable strategy. Then each walk τ = W from Bad(t) is π-stable, with WS∈ Stabπ (t). By the
definition of Bad(t) and Lemma 16 we also know that RW ∈ Indinit = σ∈supp(ωinit ) Ind(Fσ ).
Therefore,
X
X
X
X
P r[#steps ≥ t] =
p(τ ) ≤
p(τ )
τ ∈Bad(t)
(a)

≤

R∈Indinit W ∈Stabπ (R,t) τ ∈hW i

X

X

(b)

γ init · λW ≤ γ init ·

R∈Indinit W ∈Stabπ (R,t)

X

µ(R) · θt = θt−T

R∈Indinit

where (a) holds by Lemma 10, (b) holds by Theorem 14, and T is given by the expression in (5).

5

Commutativity: Proof of Theorems 7(b,c) and 8
f

g

From now on we assume that (ρ, ∼) is weakly commutative. Therefore, for any walk τ = . . . σ1 → σ2 → σ3 . . .
g
f
with f ∼
6 g there exists another walk τ 0 = . . . σ1 → σ 0 → σ3 . . . obtained from τ by applying the
=
2

f

g

SWAP operator to the subwalk σ1 → σ2 → σ3 . Such operation will be called a valid swap applied to
τ . A mapping Φ on a set of walks that works by applying some sequence of valid swaps will be called
a swapping mapping. Note that if τ 0 = Φ(τ ) then the first and the last states of τ 0 coincide with
•
•
that of τ , and λW 0 = λW where τ = W , τ 0 = W 0 . Furthermore, if (ρ, ∼) is strongly commutative
then p(τ 0 ) = p(τ ).
We now deal with the case when Λ is an arbitrary deterministic strategy, and so walks τ ∈ Bad(t)
are not necessarily π-stable. Our approach will be to construct a bijective swapping mapping Φ
that sends walks τ ∈ Bad(t) to some canonical walks, namely either to π-stable walks (which will
work only in the atomic case) or to the reverse of such walks (which will work in the general case).

5.1

Proof of Theorem 7(b)

In this section we assume that (ρ, ∼) is atomic. This gives the following observation.
w

w

Proposition 17 ([1]). Walk τ = σ1 →1 σ2 . . . σt →t σt+1 can be uniquely reconstructed from the
sequence of flaws w1 . . . wt and the final state σt+1 .

11

Proof. By atomicity, state σi can be uniquely reconstructed from the flaw wi and the state σi+1 .
Applying this argument for i = t, t − 1, . . . , 1 gives the claim.
The proposition allows us to write walks more compactly as τ = w1 . . . wt [σt+1 ]. Also, Lemma 10
gives for a walk τ = W [σt+1 ] that
p(τ ) ≤ γ init · λW · ω(σt+1 )

(10)

In Section 5.5 we will prove the following result.
Theorem 18. Suppose that (ρ, ∼) is atomic and weakly commutative. There exists a set of π-stable
walks Badπ (t) and a swapping mapping Φ : Bad(t) → Badπ (t) which is a bijection.
We can now prove Theorem 7(b):
(a)

X

P r[#steps ≥ t] =

p(τ ) ≤

τ ∈Bad(t)
(b)

γ init · λW · ω(σ)

τ =W [σ]∈Bad(t)

X

=

X

γ init · λW · ω(σ) ≤ γ init ·

R∈Indinit

τ =W [σ]∈Badπ (t)

≤ γ

init

·

X

X

X

λW ≤ γ

R∈Indinit W ∈Stabπ (R,t)

init

·

X

X

X

λW · ω(σ)

W ∈Stabπ (R,t) σ∈Ω

µ(R) · θt = θt−T

R∈Indinit

where in (a) we used eq. (10), (b) follows from Theorem 18, and the rest is similar to the derivation
in Section 4.2.

5.2

Reverse stable sequences

To prove Theorem 7(c) and Theorem 8, we will use reverse stable sequences instead of forward
stable sequences.
Walk τ will be called a prefix of a walk τ 0 if τ 0 starts with τ . Walk τ is a proper prefix of τ 0 if
•
in addition τ 0 6= τ . A word W is called a prefix of τ if τ = W U for some word U .
A set of walks X will be called valid if (i) all walks in X follow the same deterministic strategy
(not necessarily the one used in Algorithm 1), and (ii) for any τ, τ 0 ∈ X the walk τ is not a proper
prefix of τ 0 .
For a walk τ containing flaw f we define word Wτf as the longest prefix of τ that ends with
•
f . Thus, we have τ = Wτf U where Wτf = . . . f and word U does not contain f . We will also allow
•
f = ∅; in this case we say that any walk τ contains such f , and define word Wτf so that τ = Wτf .
Recall that for a word W = w1 . . . wt its reverse is denoted as REV[W ] = wt . . . w1 . The following
result is proven in Section 5.6.
Theorem 19. Fix f ∈ F ∪ {∅}, and let X f be a valid set of walks containing f . If (ρ, ∼) is weakly
commutative then there exists a set of walks Xπf and a swapping mapping Φf : X f → Xπf which is
a bijection such that
(a) for any τ ∈ Xπf the word W = REV[Wτf ] is π-stable (W ∈ Stabπ ), and RW = {f } if f ∈ F ;
(b) for any word W the set {τ ∈ Xπf | REV[Wτf ] = W } is valid.

12

5.3

Proof of Theorem 7(c)

In this case we have Indinit = Ind(F ). We will use Theorem 19 with f = ∅ and X f = Bad(t).
•
Part (a) gives that for any τ = W 0 from Xπ∅ the word W = REV[W 0 ] satisfies W ∈ Stabπ (R, t) for
some R ∈ Ind(F ). We can write
X
X
(a)
p(τ ) =
p(τ ) ≤ θt−T
P r[#steps ≥ t] =
τ ∈Bad(t)

τ ∈Xπ∅

where in (a) we used bijectiveness of mapping Φ∅ and strong commutativity of (ρ, ∼), and the rest
is similar to the derivation in Section 4.2.

5.4

Analysis of the parallel version: Proof of Theorem 8

We now analyze Algorithm 2 with a deterministic choice of flaw f in line 5. Equivalently, this can
be viewed as running Algorithm 1 with some deterministic strategy.
Theorem 20. Consider a word W and a valid set of walks X such that W is a prefix of every walk
in X . Then
X
p(τ ) ≤ γ init · λW
(11)
τ ∈X

P
Proof. We use induction on τ ∈X (|τ |−|W |). The base case τ ∈X (|τ |−|W |) = 0 is straightforward:
we
set X with
P then have X ⊆ hW i, and so the claim follows from Lemma 10. Consider a valid
− be the proper
(|τ
|
−
|W
|)
≥
1.
Let
τ̂
be
a
longest
walk
in
X
,
then
|τ̂
|
≥
|W
|
+
1.
Let
τ̂
τ ∈X
prefix of τ̂ of length |τ̂ | − 1. We have τ̂ − ∈
/ X since X is a valid set. Define set Y as follows:
Y = {τ ∈ X | τ̂ − is a proper prefix of τ }. By the choice of τ̂ we get |τ | = |τ̂ | for all τ ∈ Y, and
w
so we must have τ = τ̂ − → σ for some w ∈ F and σ ∈ Ω. Since all walks in X follow the same
w
deterministic strategy, the flaw w in the expression τ = τ̂ − → σ must be the same for all τ ∈ Y.
w
Thus, Y = {τ̂ − → σ | σ ∈ Y } for some set of flaws Y ⊆ F . In fact, we must have Y ⊆ A(w, σ̂)
where σ̂ is the final state of τ̂ − .
Define X − = (X − Y) ∪ {τ̂ − }. We have
"
#
X
X
X
X
−
−
p(τ ) −
p(τ ) =
p(τ ) − p(τ̂ ) = p(τ̂ ) ·
ρ(σ|w, σ̂) − 1 ≤ 0
P

τ ∈X

τ ∈X −

τ ∈Y

σ∈Y

X−

It is straightforward to check that set
is valid, and W is a prefix of every walk in X − . Using
the induction hypothesis for X − and the inequality above gives the claim for X .
Consider executions of Algorithm 2 consisting of at least s rounds. For each such execution let
τ be the walk containing flaws addressed in the first s − 1 rounds and the first flaw addressed in
round s. Let BadPar(s) be the set of such walks τ .
•
We say that a word U = u1 . . . us is a chain of a walk τ = w1 . . . wt if U is a subsequence of the
sequence w1 . . . wt and ui ∼
= ui+1 for i ∈ [s − 1].
Proposition 21. (a) For each τ ∈ BadPar(s) the length of a longest chain in τ equals s. (b) Set
BadPar(s) is valid.
Proof. Part (a) follows directly from Proposition 15 and the definition of a stable walk. Let us
prove (b). By construction, all walks in BadPar(s) follow the same deterministic strategy used in
Algorithm 2. Now consider a walk τ 0 ∈ BadPar(s). By the definition of τ 0 ∈ BadPar(s), any proper
prefix τ of τ 0 corresponds to an execution of Algorithm 2 with at most r − 1 rounds, and so the
length of a longest chain in τ is at most r − 1. Thus, τ ∈
/ BadPar(s).
13

For a flaw f ∈ F let BadParf (s) be the set of walks τ ∈ BadPar(s) that contain a chain of length
s that ends with f . We now apply Theorem 19 with the set X f = BadParf (s). Since every walk
τ ∈ BadParf (s) has a chain of length s that ends with f , so does every walk τ ∈ Xπf (applying a
swapping mapping to τ does not affect the chain). This means that |Wτf | ≥ s for each τ ∈ Xπf .
For a word W ∈ Stabπ ({f }, s) let hW if be the set of walks τ ∈ Xπf that satisfy REV[Wτf ] = W .
S
By Theorem 19 and the argument above we have Xπf = W ∈Stabπ ({f },s) hW if . We can thus write
X
τ ∈BadParf (s)

(a)

p(τ ) =

X
τ ∈Xπf

X

p(τ ) =

X

(b)

p(τ ) ≤

W ∈Stabπ ({f },s) τ ∈hW if

X

(c)

γ init · λW ≤ γ init · µf · θs

W ∈Stabπ ({f },s)

where in (a) we used bijectiveness of Φf and strong commutativity of (ρ, ∼), in (b) we used Theorem 20 (and the fact that hW if is
Theorem 19(b)), and in (c) we used Theorem 14.
S a valid set by
f
By Proposition 21, BadPar(s) = f ∈F BadPar (s), therefore
X
X
X
X
P r[#rounds ≥ s] ≤
p(τ ) ≤
p(τ ) ≤
γ init · µf · θs = θs−T
τ ∈BadPar(s)

f ∈F τ ∈BadParf (s)

f ∈F

where T is given by the expression in (6).

5.5

Proof of Theorem 18 (swapping mapping for the atomic case)

We can extend a “valid swap” operation to words in a natural way: it is a transformation of the
form . . . f g . . . 7→ . . . gf . . . where f ∼
6 g. We will write W ≡ W 0 if W 0 can be obtained from W
=
via a sequence of valid swaps. Clearly, “≡” is an equivalence relation. It can be seen that a walk
τ = W [σ] can be transformed to a walk τ 0 = W 0 [σ] if and only if W ≡ W 0 . In this case we will
write τ 0 ≡ τ ; again, “≡” is an equivalence relation on the set of walks.
Lemma 22. For any word W there exists a sequence of valid swaps that transforms W to a π-stable
word.
Proof. It suffices to show that W can be transformed to a stable word via valid swaps. (Transforming a stable word W to a π-stable word is straightforward: if W = W1 . . . Ws is the partition
described in Definition 13 then we simply need to apply swaps inside each word Wr to “sort” it
according to π ; any such swap will be valid by the property of Wr ).
Let W = ŵ1 . . . ŵt . We will prove by induction on i = 1, . . . , t that W can be transformed via
valid swaps to a word W 0 = w1 . . . wi . . . wt such that the prefix w1 . . . wi is a stable word. The base
case i = 1 is trivial. Suppose the claim holds for i − 1, and let us show it for i ∈ [2, t].
By the induction hypothesis, W can be transformed to a word W 0 = w1 . . . wi−1 f . . . wt such that
w1 . . . wi−1 is a stable word. Let w1 . . . wi−1 = W1 . . . Ws be the corresponding partition described
in Definition 13. Let Wr be the rightmost word that contains a flaw g with f ∼
= g. (If such word
doesn’t exist then we set r = 0; thus, r ∈ [0, s]). If r = s then we can leave the word W 0 as it is it satisfies the induction hypothesis for i.
Suppose that r ∈ [0, s − 1]. Then we repeatedly swap f with the left neighbor, stopping when
f gets between words Wr and Wr+1 (or at the first position, if r = 0). By the definition of r, these
are valid swaps. The new word now satisfies the induction hypothesis for i (flaw f will be assigned
to word Wr+1 ).
The lemma means that there exists a swapping mapping Φ that sends any walk τ = W [σ] ∈
Bad(t) to a π-stable walk τ 0 = W 0 [σ]. Next, we will show that any such mapping is injective on
Bad(t).
14

Lemma 23. Suppose that walks τ, τ 0 follow the same deterministic strategy and τ ≡ τ 0 . Then
τ = τ 0.
Proof. We use induction on the length of τ . The base case is trivial: if |τ | = |τ 0 | = 0 then condition
τ ≡ τ 0 implies that τ = τ 0 = [σ] for some state σ.
Suppose that τ = f W [σ]. Condition τ ≡ τ 0 means that τ 0 and τ start at the same state.
Therefore, since τ 0 and τ follow the same deterministic strategy, the first flaw addressed in τ 0 is
the same as in τ . Thus, τ 0 = f W 0 [σ]. Clearly, walks W [σ] and W 0 [σ] follow the same deterministic
strategy. We will show below that W [σ] ≡ W 0 [σ]; this will mean that W [σ] = W 0 [σ] by the
induction hypothesis, thus giving the desired result.
We need to show that W ≡ W 0 . We know that f W ≡ f W 0 , therefore there exists a sequence
of words U (1) , . . . , U (k) with U (1) = f W , U (k) = f W 0 such that U (i+1) is obtained from U (i) via a
single valid swap operation. Let V (i) be the word obtained from U (i) by moving the first occurence
of flaw f in U (i) to the first position. Thus, for each i ∈ [k] we have V (i) = f W (k) for some
word W (k) . It can be seen that either V (i+1) = V (i) (if the valid swap operation applied to U (i)
involved the first occurence of f ) or V (i+1) is obtained from V (i) via a valid swap (otherwise). Thus,
either W (i+1) = W (i) or W (i+1) is obtained from W (i) via a valid swap. It remains to notice that
W (1) = W and W (k) = W 0 .
We can now prove that Φ is injective. Suppose that τ, τ 0 ∈ Bad(t) and Φ(τ ) = Φ(τ 0 ). We have
τ ≡ Φ(τ ) = Φ(τ 0 ) ≡ τ 0 , and so τ ≡ τ 0 . From the previous lemma we obtain that τ = τ 0 , which
concludes the proof of Theorem 18.

5.6

Proof of Theorem 19 (swapping mapping for the non-atomic case)

Consider a word W = w1 . . . wt . It will be convenient to alternatively write it as W = w1 . . . wt
where wi = (wi , ni ) and ni counts from the left which occurrence of the flaw wi it is: ni = |{j ∈
[i] | wj = wi }| ≥ 1. Note that all elements w1 , . . . , wt are distinct. Tuple wi will be called a named
flaw. The flaw associated with the named flaw f will be denoted without the bold font as f , i.e.
f = (f, nf ).
We will denote the element of F ∪ {∅} fixed in the theorem as fˆ (rather than f ).
•
For a walk τ = w1 . . . wt let us define a directed acyclic graph Gτ = (Vτ , Eτ ) as follows: its
nodes are Vτ = {w1 , . . . , wt }, and the set Eτ contains all edges of the form (f , g) where f ∼
= g and
•
f occurs in τ before g, i.e. τ = . . . f . . . g . . ..
For a walk τ containing fˆ we make the following definitions:
• If fˆ ∈ F , let Wτ be the set of flaws g ∈ Vτ from which node f̂ can be reached in Gτ , where
f̂ is the named flaw corresponding to the rightmost occurence of fˆ in τ . For f ∈ Wτ let dτ (f )
be the length of the longest path from f to f̂ in Gτ plus one (so that dτ (f̂ ) = 1).
• If fˆ = ∅, let Wτ = Vτ . For f ∈ Wτ let dτ (f ) be the length of the longest path from f to a
sink of Gτ plus one (so that for any sink node f ∈ Vτ we have dτ (f ) = 1).
Let Wτ be the word consisting of the named flaws in Wτ listed in the order in which they appear
in τ .
It is straighforward to check that applying valid swaps to τ does not affect graph Gτ and set Wτ
(but may affect the order of named flaws in Wτ ). Our goal will be to apply swaps to τ so that
in the end word Wτ becomes a prefix of τ , and furthermore this prefix equals the word Stabπ (τ )
which is defined below.

15

Definition 24. For a walk τ containing fˆ define word Stabπ (τ ) as follows. For an integer r ≥ 1 let
Ir = {f ∈ Wτ | dτ (f ) = r}, and let Wr be the word consisting of the named flaws in Ir sorted in the
decreasing order (with respect to π ). Then Stabπ (τ ) = Ws . . . W1 where s = max{dτ (f ) | f ∈ Wτ }.
It can be seen that we have f 6= g for any distinct f , g ∈ Ir . Therefore, “sorting Ir in the
decreasing order” in the definition is a valid operation (where we assume that f ≺π g if f ≺π g).
Clearly, applying a valid swap to τ does not affect word Stabπ (τ ) (since graph Gτ and set Wτ
are unaffected). It is also not difficult to show the following.
ˆ
Lemma 25. For any τ ∈ X f word W = REV[Stabπ (τ )] is π-stable. Also, RW = {fˆ} if fˆ ∈ F .

Proof. Let Ir = {f | f ∈ Ir } be the “unnamed” version of the set Ir from Definition 24. Consider
r ∈ [s − 1]. From the the definition of Ir and Ir+1 we obtain that for every g ∈ Ir+1 there exists
f ∈ Ir with (f , g) ∈ Eτ (implying that g ∈ Γ+ (f )). This gives that Ir+1 ⊆ Γ+ (Ir ). Also, if fˆ ∈ F
then we have I1 = {f̂ } and so I1 = {fˆ}. Observing that W = REV[Stabπ (τ )] = REV[W1 ] . . . REV[Ws ]
we obtain the desired claims.
ˆ

•

Our next goal is to show how to transform walk τ ∈ X f to a walk τ 0 = Stabπ (τ )U . We will do
this by applying swaps to swappable pairs in τ .
Definition 26. Consider a walk τ containing fˆ. A pair (f , g) of named flaws is called a swappable
•
pair in τ if it can be swapped in τ (i.e. τ = . . . fg . . . and f 6∼
= g) and either
(i) (f , g) ∈ (Vτ − Wτ ) × Wτ , or
(ii) (f , g) ∈ Wτ × Wτ and their order in Stabπ (τ ) is different: Stabπ (τ ) = . . . g . . . f . . ..
The position of the rightmost swappable pair in τ will be denoted as k(τ ), where the position of
(f , g) in τ is the number of named flaws that precede g in τ . If τ does not contain a swappable pair
then k(τ ) = 0. Thus, k(τ ) ∈ [0, |τ | − 1].
It can be seen that the procedure of repeatedly applying swaps to swappable pairs in τ must
terminate. Indeed, swapping a pair of the form (i) moves a named flaw in Wτ to the left, which
can happen only a finite number
 of times. Similarly, swapping a pair of the form (ii) decreases the
number of pairs {f , g} ∈ W2 τ whose relative order in Wτ is not consistent with the relative order
in Stabπ (τ ), which again can happen only a finite number of times. (Note, swaps of the other type
do not affect these arguments).
•
Lemma 27. Consider a walk τ = AU containing fˆ where A, U some words, and there are no
swappable pairs inside U . Then U = BC where sequence B is a subsequence of Stabπ (τ ), and C
does not contain named flaws from Wτ .
•
•
In particular, if |A| = 0 and τ = U does not contain a swappable pair then τ = Stabπ (τ )C.

Proof. Let u1 , . . . , um be the named flaws from Wτ that occur in U (listed in the order of their
appearance in U ). We claim that u1 . . . um is a prefix of U . Indeed, suppose not, then U = . . . fui . . .
where f ∈
/ Wτ and ui ∈ Wτ . This means that (f , ui ) ∈
/ Eτ , and so f 6∼
= ui . But then (f , ui ) is a
swappable pair in U - a contradiction.
•
We obtained a decomposition τ = ABC where B = u1 . . . um . It remains to show that B is a
subsequence of Stabπ (τ ). For that it suffices to prove that for any i ∈ [m−1] the relative order of ui
and ui+1 in B is the same as in Stabπ (τ ). Suppose not, i.e. Stabπ (τ ) = . . . ui+1 . . . ui . . .. We must
have ui ∼
= ui+1 (otherwise (ui , ui+1 ) would be a swappable pair in τ , contradicting the assumption).
Therefore, (ui , ui+1 ) ∈ Eτ , implying that dτ (ui ) > dτ (ui+1 ). Inspecting Definition 24, we conclude
that ui should be to the left of ui+1 in Stabπ (τ ). We obtained a contradiction.
16

ˆ

ˆ

ˆ

ˆ

Results so far can be used to obtain a mapping Φf and set Xπf = Φf (X f ) that satisfy condition
(a) of Theorem 19. To satisfy bijectiveness and condition (b), we need to be careful with the
order in which we apply swaps to swappable pairs. We will use the following algorithm. First, let
ˆ
X0 = X f , and then for p = 0, 1, 2, . . . do the following:
• Let k = maxτ ∈Xp k(τ ). If k = 0 then terminate.
• For each τ ∈ Xp do the following: if k(τ ) = k then swap the pair (f , g) at position k in τ ,
otherwise leave τ unchanged. Let Xp+1 be the new set of walks.
Let us fix a word W (over named flaws), and define Xp [W ] = {τ ∈ Xp | Stabπ (τ ) = W } for an
ˆ
index p ≥ 0. Theorem 19 will follow from the following result (note that set X0 [W ] ⊆ X f is valid
by the assumption of the theorem).
Lemma 28. If set Xp [W ] is valid then so is Xp+1 [W ], and the mapping from Xp [W ] to Xp+1 [W ]
defined by the algorithm above is injective.
Proof. First, let us prove injectiveness. Suppose that two distinct walks τ ◦ , τ̄ ◦ ∈ Xp [W ] are transformed to the same walk τ ∈ Xp+1 [W ]. At least one of one walks τ ◦ , τ̄ ◦ must have changed. Assume
•
•
w.l.o.g. that τ 6= τ ◦ . Thus, walk τ ◦ = AfgB with f ∼
6 g is transformed to a walk τ = Agf B. We
=
cannot have τ̄ ◦ = τ (then walks τ ◦ , τ would both be in Xp [W ], but they do not follow the same
•
same deterministic strategy - a contradiction). Thus, τ̄ ◦ = AfgB, and τ was obtained from τ̄ ◦ by
swapping f and g. Since the SWAP operation from Definition 3 is injective, we obtain that τ ◦ = τ̄ ◦ .
Now suppose that Xp+1 [W ] is not valid. Then it contains walks τ, τ̄ of the form
τ
τ̄

•

=
•

=

w1 . . . w` fg . . .
w1 . . . w` f̄ ḡ . . .

such that f 6= f̄ , and the states in τ to the left of f match the corresponding states in τ̄ to the left
of f̄ . Here we assume some of the symbols f , g, f̄ , ḡ can equal ∅, which means that they don’t exist.
We also assume that f = ∅ ⇒ g = ∅ and f̄ = ∅ ⇒ ḡ = ∅.
Let τ ◦ and τ̄ ◦ be respectively the walks in Xp [W ] that were transformed to τ and τ̄ . Since
Xp [W ] is valid, at least one of them must have changed. Assume w.l.o.g. that τ 6= τ ◦ . We know
that
(∗) τ ◦ and τ̄ ◦ follow the same deterministic strategy, and they are not proper prefixes of each
other;
(∗∗) named flaws w1 , . . . , w` , f are distinct.
We will also implicitly use the fact that the first ` + 1 states of τ match those of τ̄ , and also that
swapping adjacent flaws only affects the state between them in a deterministic way, as specified by
the mapping SWAP. Four cases are possible:
•
• The swapped pair in τ was (wi , wi+1 ) for i ∈ [` − 1], and so τ ◦ = w1 . . . wi+1 wi . . . w` fg . . ..
•
Using (∗) and (∗∗), we conclude that τ̄ 6= τ̄ ◦ , and so τ̄ ◦ = w1 . . . wi+1 wi . . . w` f̄ ḡ . . .. (Recall
that swaps are applied at the same position for walks in Xp ). Condition (∗) now gives f = f̄ .
•
• The swapped pair in τ was (w` , f ), and so τ ◦ = w1 . . . fw` g . . .. Using (∗) and (∗∗), we
•
conclude that τ̄ 6= τ̄ ◦ , and so τ̄ ◦ = w1 . . . f̄ w` ḡ . . .. Condition (∗) now gives f = f̄ .
•
• The swapped pair in τ was (f , g), and so τ ◦ = w1 . . . w` gf . . . and f ∈ Wτ ◦ . Since there are
•
no swappable pairs in τ ◦ to the right of (g, f ), Lemma 27 gives that τ ◦ = w1 . . . w` gBC where
B is a subsequence of Stabπ (τ ◦ ) and C does not contain named flaws from Wτ ◦ . Note that
B starts with f .
17

•

By property (∗) we get that τ̄ ◦ = w1 . . . w` g . . .. Using Lemma 27 as before, we obtain that
•
τ̄ ◦ = w1 . . . w` gB̄ C̄ where B̄ is a subsequence of Stabπ (τ̄ ◦ ) and C̄ does not contain named
flaws from Wτ̄ ◦ .
We now observe that τ ◦ , τ̄ ◦ ∈ Xp [W ], i.e. Stabπ (τ ◦ ) = Stabπ (τ̄ ◦ ) = W . Therefore, Wτ ◦ =
Wτ̄ ◦ . This fact together with the forms of τ ◦ , τ̄ ◦ given above implies that B is a permutation
of B̄. We also know that both B and B̄ are subsequences of Stabπ (τ ◦ ) = Stabπ (τ̄ ◦ ) = W
and all elements of W are distinct. Thus, we can conclude that B = B̄.
•
We showed that τ̄ ◦ = w1 . . . w` gf . . .. Since (g, f ) is a swappable pair in τ ◦ , it is also a
•
swappable pair in τ̄ ◦ (at the same position as in τ ◦ ). Therefore, τ̄ = w1 . . . w` fg . . ., and so
f = f̄ .
• The swapped pair in τ was to the right of (f , g). In this case condition (∗) immediately gives
f = f̄ .

6

Constructing atomic commutative resampling oracles

Let us define a directed multigraph D as follows: its set of nodes is Ω, and its set of edges is the
f

set of all valid walks σ → σ 0 . (Each edge of D is labeled by a flaw in F ). The atomicity of ρ means
any state σ 0 ∈ Ω has at most one incoming edge in D labeled by a given flaw f ∈ F .
f

Note that we can recover sets A(f, σ) from D, since A(f, σ) = {σ 0 | edge σ → σ 0 belongs to D}.
Therefore, resampling oracles can be uniquely reconstructed from D, if we assume that ρ(σ 0 |f, σ)
is a uniform distribution over A(f, σ).
In this section we show that resampling oracles for permutations used in [8, 9] and for perfect
matchings in complete graphs used in [9] are strongly commutative. To prove this, we find it
easier to take an indirect approach: first, we will describe a generic route for constructing atomic
multigraphs, then apply it to permutations and matchings and prove weak commutativity. We will
then see that the resulting resampling procedure coincides with that in [8, 9].
The constructed multigraph will satisfy the following property: for each flaw f there exists
constant Af such that |A(f, σ)| = Af all σ ∈ f . Thus, ρ(σ 0 |f, σ) = A1f for σ 0 ∈ A(f, σ), and so
weak commutativity will imply strong commutativity.
We start with some general observations. For an atomic multigraph D let us define a mapping
ψ : F × Ω → Ω ∪ {undefined} that specifies a “backward step” for f ∈ F and σ 0 ∈ Ω as
f

follows: if there exists the (unique) state σ ∈ Ω such that σ → σ 0 then ψ(f, σ 0 ) = σ, otherwise
ψ(f, σ 0 ) = undefined. Note that ψ satisfies the following properties:
(I) If ψ(f, σ 0 ) 6= undefined then ψ(f, σ 0 ) ⊆ f .
(II) For any f ∈ F and σ ∈ f there exists at least one σ 0 ∈ Ω with ψ(f, σ 0 ) = σ.
It is not difficult to see that D can be uniquely reconstructed from Ω, F and ψ, since for each
f ∈ F and σ ∈ f we have A(f, σ) = {σ 0 ∈ Ω | ψ(f, σ 0 ) = σ}. Furthermore, any triplet (Ω, F, ψ)
specifies a valid atomic multigraph D, as long as ψ satisfies properties (I) and (II) (and F is some
set of non-empty subsets of Ω). Property (II), in particular, is equivalent to the condition that
A(f, σ) is non-empty for each f ∈ F and σ ∈ f .
Thus, the problem of constructing the set of actions A(f, σ) for a given f, σ can be shifted to
the problem of constructing a mapping ψ. Of course, after constructing ψ one still needs to show
that sampling from A(f, σ) can be done efficiently.
We remark that Definition 2 of the potential causality graph can also be reformulated in terms
of the mapping ψ, as stated below (this claim follows directly from definitions).
18

Proposition 29. Undirected graph (F, ∼) is a potential causality graph for D if for any f, g ∈ F
with f  g and any σ 0 ∈ g with ψ(f, σ 0 ) 6= undefined we have ψ(f, σ 0 ) ∈ g and f =
6 g.

6.1

Matchings

We now apply the route outlined above to some matching problems. Let G = (V, E) be an
undirected graph with |V | = 2n nodes that satisfies the following condition:
(∗) If (u0 , u, v, v 0 ) is a path in G with distinct nodes then {u0 , v 0 } ∈ E.
We will consider the case when Ω is the set of perfect matchings in G (so that each object σ ∈ Ω is
a subset of E). We allow any flaw of the form fM = {σ ∈ Ω | M ⊆ σ} where M is a fixed subset of
E. It can be assumed w.l.o.g. that M is a matching (otherwise fM would be empty). Thus, F can
be any subset of {fM | M ∈ M} where M denotes the set of matchings in G, with Ω ⊂ M. Two
special cases of this framework have been considered [8, 1, 9]:
[P1] G is the complete graph on 2n vertices, so that Ω is the set of all perfect matchings of V .
[P2] Set V can be partitioned into disjoint subsets A1 , B1 , . . . , Ar , Br such that |Ai | = |Bi | for
i ∈ [r] and E = {{u, v} | u ∈ Ai , v ∈ Bi , i ∈ [r]}. Thus, G is a union of r complete bipartite
graphs, and set Ω corresponds to r permutations.
In fact, these are essentially the only possibilities allowed by condition (∗): it can be shown that
if G contains at least one perfect matching then each component of G is either a complete graph
Km or a complete bipartite graph Km,m . We will not need this claim, and so we leave it without a
proof. Instead, we just assume that one of the two cases [P1,P2] holds (but unlike previous work,
we will treat them in a unified way, relying mostly on condition (∗)).
We use the following potential causality graph: fM ∼ fM 0 for fM , fM 0 ∈ F if M ∪ M 0 is not a
matching or M = M 0 . This graph is the same or slightly smaller than graphs used previously for
cases [P1] and [P2]. (For [P2] the works [8, 9] used a larger relation ∼0 instead where fM ∼0 fM 0 if
M ∪ M 0 is not a matching or M ∩ M 0 6= ∅).
We will construct a mapping ψ̂ : M × Ω → Ω that satisfies M ⊆ ψ̂(M, σ) for any M ∈ M and
σ ∈ Ω. It will correspond to the mapping ψ in a natural way, i.e. ψ(fM , σ) = ψ̂(M, σ) for fM ∈ F .
Clearly, such ψ will be defined everywhere on F × Ω, and will satisfy property (I).
Defining ψ̂ Consider M ∈ M and σ ∈ Ω. If M contains a single edge e = {u, v}, then we find
unique u0 , v 0 with {u, u0 }, {v, v 0 } ∈ σ, and set
ψ̂({e}, σ) = (σ − {{u, u0 }, {v, v 0 }}) ∪ {{u, v}, {u0 , v 0 }}

(12)

Note that if {u, v} ∈ σ 0 then ψ̂(M, σ) = σ. Otherwise nodes u, v, u0 , v 0 are distinct, and we have
ψ̂(M, σ) ∈ Ω by the assumption (∗) on the graph G.
Now suppose that M = {e1 , . . . , ek } contains more than one edge. Then we define
σ0 = σ

σ1 = ψ̂({e1 }, σ0 ) σ2 = ψ̂({e2 }, σ1 )

...

σk = ψ̂({ek }, σk−1 )

(13)

and set ψ̂(M, σ) = σk . To show that this is well-defined, we need to prove that the result does
not depend on the chosen ordering of M . It suffices to prove this claim for |M | = 2, then we can
use an induction argument (since any ordering of M can be transformed to any other ordering via
a sequence of operations that swap adjacent elements). Proving it for |M | = 2 can be done by
inspecting all possible cases, which are visualized in Fig. 1; verification of the claim in each case is
left to the reader.

19

Figure 1: Possible cases for M = {e1 , e2 } ∈ M and σ ∈ Ω. Top row: solid lines indicate edges in σ,
dashed lines indicate edges in M . Bottom row: result of ψ({e1 }, ψ({e2 }, σ)) = ψ({e2 }, ψ({e1 }, σ)).
Proposition 30. (a) In (13) we have {e1 , . . . , ei } ⊆ σi for any i ∈ [k]. Consequently, M ⊆ ψ̂(M, σ)
for any M ∈ M and σ ∈ Ω (and so property (I) holds).
(b) For any σ ∈ Ω and M, M 0 ∈ M with M ∪ M 0 ∈ M we have ψ̂(M, ψ̂(M 0 , σ)) = ψ̂(M 0 , ψ̂(M, σ)).
Consequently, the multigraph D defined by (Ω, F, ψ) is weakly commutative with respect to ∼.
(c) Relation ∼ is a potential causality graph for D.
Proof. (a) We can use induction on i. The base case i = 0 is vacuous. The induction step for
i follows from the definition of the mapping ψ̂({ei }, σi−1 ) and the fact that σi−1 cannot contain
edges that connect an endpoint of ei to an endpoint of ej for j ∈ [i − 1] (since {e1 , . . . , ei−1 } ⊆ σi−1
by the induction hypothesis, and {e1 , . . . , ei } is a matching).
(b)
We claim ψ̂(M 0 , ψ̂(M, σ)) = ψ̂(M ∪ M 0 , σ). Indeed, let M = {e1 , . . . , e` } and M 0 =
{e`+1 , . . . , ek }. Define σ0 , σ1 , . . . , σk as in (13), then ψ̂(M, σ) = σ` and ψ̂(M 0 , σ` ) = σk . Thus,
it remains to show that ψ̂(M ∪ M 0 , σ) = σk . For that we need to observe that if some edge ei
appears in the sequence the (e1 , . . . , ek ) the second time then we have ei ∈ σi−1 and consequently
σi = ψ̂({ei }, σi−1 ) = σi−1 . Thus, such ei can be removed from the sequence without affecting the
result. After removing duplicates we conclude that ψ̂(M ∪ M 0 , σ) = σk by the definition of ψ̂.
In a similar way we can show that ψ̂(M, ψ̂(M 0 , σ)) = ψ̂(M ∪ M 0 , σ). This proves the claim.
(c) Let us show that conditions of Proposition 29 hold. Consider flaws f = fM , g = fM 0 in F
with fM  fM 0 and object σ ∈ fM 0 . Condition fM 6= fM 0 holds since fM  fM 0 , so we need to
show that ψ(fM , σ) ∈ fM 0 , or equivalently M 0 ⊆ ψ̂(M, σ).
Assume that M = {e1 , . . . , ek }, and define sequence σ0 , σ1 , . . . , σk−1 , σk = ψ̂(M, σ) as in (13).
Indeed, for the base case the claim M 0 ⊆ σ holds since σ ∈ fM 0 , and for the induction step we need
to use the definition of ψ̂ and the fact that M ∪ M 0 ∈ M (which holds since fM  fM 0 ). We leave
verification of the induction step to the reader.
Sampling from A(fM , σk ) The general idea is to “reverse” the process in eq. (13): given flaw
fM with M = {e1 , . . . , ek } ∈ M and object σk ∈ fM , we first generate possible values for σk−1 ,
then for σk−2 , and so on.
→
−
For a subset S ⊆ E let S = {(u, v), (v, u) | {u, v} ∈ A} be a “directed copy” of S. For an object
−
σ ∈ Ω and edges (u, v), (u0 , v 0 ) ∈ →
σ define
Swapσ ((u, v), (u0 , v 0 )) = (σ − {{u, v}, {u0 , v 0 }}) ∪ {{u, u0 }, {v, v 0 }}

(14)

−
Finally, for an object σ ∈ Ω and an edge (u, v) ∈ →
σ let us define
−
Nσ (u, v) = {(u0 , v 0 ) ∈ →
σ | Swapσ ((u, v), (u0 , v 0 )) ∈ Ω}
20

(15)

It can be checked that (v, u) ∈ Nσ (u, v) and (u, v) ∈
/ Nσ (u, v). Furthermore, in the special cases
above we have the following:
−
[P1] Nσ (u, v) = →
σ − {(u, v)}.
−
[P2] If (u, v) ∈ Ai × Bi then Nσ (u, v) = (Bi × Ai ) ∩ →
σ.
We can now formulate the sampling algorithm (see Algorithm 3).
Algorithm 3 Sampling from A(fM , σk ) for M = {e1 , . . . , ek } ⊆ σk ∈ Ω
1: for i = k, k − 1, . . . , 1 do
2:
choose orientation (u, v) of edge ei = {u, v}
−−−−−−−−−→
3:
select (u0 , v 0 ) ∈ Nσi (u, v) − {e1 , . . . , ei−1 } uniformly at random
4:
set σi−1 = Swapσi ((u, v), (u0 , v 0 ))
5: end for
6: return σ0
Let us verify the correctness of this algorithm. Using the definitions of ψ̂ and Swapσ , the
following fact can be easily checked.
Lemma 31. (a) Suppose that {u, v} ∈ σi ∈ Ω, (u0 , v 0 ) ∈ Nσi (u, v) and σi−1 = Swapσi ((u, v), (u0 , v 0 )).
Then ψ̂({{u, v}}, σi−1 ) = σi .
(b) Conversely, suppose that ψ̂({{u, v}}, σi−1 ) = σi for ei = {u, v} ∈ E and σi−1 ∈ Ω. Then there
exists unique (u0 , v 0 ) ∈ Nσi (u, v) such that σi−1 = Swapσi ((u, v), (u0 , v 0 )). Furthermore, it satisfies
{u0 , v 0 } ∈
/ σi−1 − {ei }.
Using this lemma, we can now show establish correctness of the sampling procedure. We say
that two executions of Algorithm 3 are distinct if they made different choices in line 3 for some
i ∈ [k].
Proposition 32. Algorithm 3 is well-defined, i.e. in line 3 we have ei ∈ σi . It can generate object
σ0 ∈ Ω if and only if ψ̂(M, σ0 ) = σk . Finally, distinct executions produce distinct outputs.
Proof. The proof will have two parts corresponding to two directions.
(a) Let σk , σk−1 , . . . be the sequence of objects produced by the algorithm. We will show using
induction on i = k, . . . , 1, 0 that {e1 , . . . , ei } ⊆ σi (and therefore line 3 for index i is well-defined)
and ψ̂({ei+1 , . . . , ek }, σi ) = σk . The base case i = k is trivial. Suppose the claim holds for i ∈ [k],
let us show it for i − 1. We have {e1 , . . . , ei } ⊆ σi by the induction hypothesis; inspecting the rule
for choosing (u0 , v 0 ), we conclude that {e1 , . . . , ei−1 } ⊆ σi−1 . For the second claim we can write
ψ̂({ei , . . . , ek }, σi−1 ) = ψ̂({ei+1 , . . . , ek }, ψ̂({ei }, σi−1 )) = ψ̂({ei+1 , . . . , ek }, σi ) = σk
where the first equality is by the definition of ψ̂, the second is by Lemma 31(a) and third is by the
induction hypothesis. This concludes the argument.
(b) Suppose that ψ̂(M, σ0 ) = σk for σ0 ∈ Ω and M = {e1 , . . . , ek }. Define objects σ1 , . . . , σk
as in (13). We claim that Algorithm 3 can replicate this sequence (in the reverse order). Indeed,
by Lemma 31(b) it suffices to show that for any (u0 , v 0 ) ∈ Nσi (u, v) with {u0 , v 0 } ∈
/ σi−1 − {ei }
−−−−−−−−−→
−−−−−−−−−→
0
0
0
0
we also have (u , v ) ∈ Nσi (u, v) − {e1 , . . . , ei−1 }. Suppose not, then (u , v ) ∈ {e1 , . . . , ei−1 }. By
Proposition 30(a) we have {e1 , . . . , ei−1 } ⊆ σi−1 , and so {u0 , v 0 } ∈ σi−1 . Thus, {u0 , v 0 } = ei . But ei
−−−−−−−−−→
does not appear in {e1 , . . . , ei−1 }, and so we cannot have (u0 , v 0 ) ∈ {e1 , . . . , ei−1 } - a contradiction.
Let us now prove that the input M , σk and the output σ0 uniquely determine choices made
during the execution (this will give the last claim of the lemma). Let σ̃k , . . . , σ̃1 , σ̃0 be the objects
21

produced during the execution, with σ̃k = σk and σ̃0 = σ0 . Set i = 1. By Lemma 31(a) we have
ψ̂({ei }, σi−1 ) = σ̃i , implying that σ̃i = σi is determined uniquely. By Lemma 31(b) the choice
of (u0 , v 0 ) in line 3 for index i is also determined uniquely from σi−1 , σi and ei . Repeating this
argument for i = 2, . . . , k (i.e. using induction) yields the claim.
We have proved that the output of Algorithm 3 is a distribution whose support is A(fM , σk ). To
show that this distribution is uniform, we need to observe additionally that the number of choices
in line 3 for index i depends on i but not on the past execution history (which can be easily checked
for cases [P1] and [P2]). The cardinality of A(fM , σk ) is the product of these numbers over i ∈ [k],
and thus depends only on the flaw fM (more precisely, on |M |).
To summarize, we have constructed an atomic weakly commutative multigraph D, proved that
Algorithm 3 samples uniformly from A(fM , σk ), and the size of latter set depends only on fM (the
latter implies strong commutativity). It can now be verified that the sampling procedure coincides
with the procedure in [9] for perfect matchings in a complete graph (in the case [P1]), and with
the procedure in [8, 9] for permutations (in the case [P2]).

6.2

Application: rainbow matchings in complete graphs

We refer to [8, 1, 9] for applications of resampling oracles for permutations and perfect matchings.
Here we revisit just one application, namely a rainbow matching problem. Our primary goal is to
demonstrate how the choice of the distribution ω init affects the bound on the expected runtime,
and also compare it with the parallel version.
Let G = (V, E) be a complete graph on 2n vertices such that each edge is assigned a color, and
each color appears in at most q edges. A perfect matching in G is called rainbow if its edges have
distinct colors. Achlioptas and Iliopoulos [1] showed that a rainbow matching exists if q ≤ γn for
1
some constant γ < 2e
' 0.184. Instead of (2b), they used a stronger condition (3). Harvey and
Vondrák [9] improved the constant to γ = 0.21 by exploiting a condition with the cluster expansion
correction analogous to (2). Below we redo their calculations.
Let F be the set of flaws fM such M contains two vertex-disjoint edges of the same color, and
assume that we use the multigraph and relation ∼ constructed in the previous section.
Proposition 33. If γ = 0.21 then condition (2) can be satisfied by setting µf = µ =
(if n is sufficiently large).

3
4n2

for f ∈ F

Proof. Consider flaw fM where M = {{v1 , v2 }, {v3 , v4 }} ∈ F . For node v ∈ V let Γ(v) ⊆ F be
the set of flaws fM 0 such that at least one of the edges in M 0 is incident to v. Clearly, we have
Γ(fM ) ⊆ Γ(v1 ) ∪ Γ(v2 ) ∪ Γ(v3 ) ∪ Γ(v4 ). Furthermore, if S ∈ Ind(Γ(fM )) then for each i ∈ [4] we
have |S ∩ Γ(vi )| ≤
 1 (and consequently |S| ≤ 4). It can be seen that for each k ∈ [0, 4] there are
at most nk = k4 (2n − 1)k (q − 1)k subsets S ∈ Ind(Γ(fM )) of size k. Indeed, feasible S can be
generated as follows: first choose
a subset of {Γ(v1 ), Γ(v2 ), Γ(v3 ), Γ(v4 )} of size k whose elements

will contain a flaw in S ( k4 possibilities), and then for each selected Γ(vi )
• choose a node vi0 matched to vi (at most 2n − 1 possibilities), and
• choose an edge in G of the same color as {vi , vi0 } (at most q − 1 possibilities).
Let us set value µf for all f ∈ F to the same constant µ > 0, then we get
X
S∈Ind(Γ(fM ))

µ(S) ≤

4
X

nk · µk = (1 + (2n − 1)(q − 1)µ)4

k=0

22

By inspecting Algorithm 3 we can conclude that Af = (2n − 3)(2n − 1) for each f ∈ F . Thus, we
get the following condition: there must exist µ > 0 such that expression
θ=

1
· (1 + (2n − 1)(q − 1)µ)4
(2n − 3)(2n − 1)µ

is a constant smaller than 1. Denote β = (2n − 3)(2n − 1)µ, then
θ≤


4
(1 + 12 γβ + o(1))4
β
1
· 1 + 2n · (γn) · 2 · (1 + o(1)) =
β
4n
β

The last expression will be smaller than 1 (for a sufficiently large n) if β = 3 and γ = 0.21, where
we used the constants from [9].
Let us now estimate the expression in (5). We have |Ω| = (2n − 1)!! and log |Ω| = Θ(n log n).
When supp(ω init ) = {σ init } for some σ init ∈ Ω, we get γ init = |Ω| and thus T = Ω(n log n). If,
on the other hand, ω init = ω then we can write
X
X
Y
µ(R) ≤
µ(R) =
(1 + µf ) = (1 + µ)|F |
R∈

S

σ∈Ω

Ind(Fσ )

f ∈F

R⊆F

Observing that |F | ≤ (2n)2 q = O(n3 ) and µ = O(1/n2 ), we obtain that T = O(|F | log(1 + µ)) =
O(n3 log(1 + O( n12 ))) = O(n3 · n12 ) = O(n). Thus, choosing ω init = ω leads to a better bound than
initializing the algorithm with some fixed state σ init . This may not be surprising, given that in
the latter situation we need to consider the worst case. Note that a linear bound on the expected
number of resampling steps has also been shown in [9].
We can also compute a bound on the expected number of rounds of the parallel version (Algorithm 2), assuming that ω init = ω. From Theorem 8 we get
P
T = O(log f ∈F µf ) = O(log(|F | · µ)) = O(log(n3 · n12 )) = O(log n)
It should be noted, however, that at the moment it is not known whether a round of Algorithm 2 can
be implemented efficiently (i.e. in an [expected] polylogarithmic time) for matchings in a complete
graph. Such implementation has only been shown for permutations [8]. We conjecture that the
technique in [8] can be extended to matchings in a complete graph, but leave this question outside
the scope of this work.

A

Counting stable sequences: Proof of Theorem 14

We say that a sequence ϕ = (I1 , . . . , Is ) with s ≥ 1 is strongly stable if
(i) Ir ∈ Ind(F ) for each r ∈ [s],
(ii) Ir+1 ⊆ Γ(Ir ) for each r ∈ [s − 1], and
(iii) Ir 6= ∅ for each r ∈ [2, s].
(Compared to Definition 12, we added condition (iii), and in (ii) replaced condition Ir+1 ⊆ Γ+ (Ir )
with a stronger condition Ir+1 ⊆ Γ(Ir )). For a stable word W let ϕW = (I1 , . . . , Is ) be the
corresponding stable sequence; if W is empty then ϕW = (∅).
Proposition 34. For any W ∈ Stabπ the sequence ϕW is strongly stable.

23

Proof. We need to show that the sequence ϕW = (I1 , . . . , Is ) satisfies additionally property (ii).
•
We will prove this under the assumption that there exists a walk τ = W . (The case when there
•
exists a walk τ = REV[W ] is completely analogous).
Let W = W1 . . . Ws be the partitioning of W given in Definition 13. It suffices to prove that
if a flaw f is present in adjacent segments Wr and Wr+1 then f ∼ f . Suppose not: f  f .
Then by Lemma 11(b) there exists flaw g between the two occurences of f with f ∼ g. We have
Wr Wr+1 = . . . f . . . g . . . f . . .. We have either g ∈ Wr or g ∈ Wr+1 , and so we must have f  g - a
contradiction.
For a sequenceP
ϕ = (I1 , . . . , Is ) withQ s ≥ Q1 let Rϕ = I1 be the first set in the sequence,
and denote |ϕ| =
r∈[s] |Ir | and λϕ =
r∈[s]
f ∈Ir λf . Let Stab be the set of strongly stable
sequences, Stab(R) = {ϕ ∈ Stab : Rϕ = R}, Stab(t) = {ϕ ∈ Stab : |ϕ| ≥ t} and Stab(R, t) =
Stab(R) ∩ Stab(t).
Clearly, a π-stable word W can be uniquely reconstructed from the corresponding sequence ϕW .
Thus, W 7→ ϕW is an injective mapping from Stabπ (R, t) to Stab(R, t). Also, λW = λϕW for any
W ∈ Stabπ (R, t). This means that Theorem 14 will follow from the following result.
Theorem 35. Suppose that (ρ, ∼) satisfies either the cluster expansion condition (2b) or the
Shearer’s condition from Definition 6. 4 Then
X
λϕ ≤ µ(R) · θt
∀R ∈ Ind(F )
(16)
ϕ∈Stab(R,t)

Proof. First, assume that the Shearer’s condition holds. In this case the claim has been proven
in [11, 9]. To elaborate, let p ∈ R|F | be the vector from Definition 6, and define
Y Y
pϕ =
pf
(17)
r∈[s] f ∈Ir

Let Stab0 be the set of sequences φ = (I1 , . . . , Is ) that satisfy conditions (i) and (ii) given in the
beginning of this section. For any integer ` we can write
X
ϕ∈Stab(R,t)

pϕ ≤

X
ϕ=(R,I2 ,...,I` )∈Stab0

pϕ ≤

qR (p)
q∅ (p)

∀R ∈ Ind(F )

(18)

length of ϕ is at most `

where the first inequality holds since for any ϕ = (I1 , . . . , Is ) ∈ Stab(R, t) with s ≤ ` there is a
corresponding sequence ϕ0 = (R, I2 , . . . , Is , ∅, . . . , ∅) ∈ Stab0 of length `, and the second inequality
appears implicitly eq. (2) in [11] and as Lemma 5.10 in [9]. Taking a limit ` → ∞ in (18) and
P
(p)
, we get ϕ∈Stab(R,t) pϕ ≤ µ(R). From definitions we have λϕ ≤ pϕ · θt
observing that µ(R) = qqR∅ (p)
for any ϕ ∈ Stab(R, t), this gives (16).
Now assume that condition (2) holds. We say that a pair of subsets (R, S) is independent if
R ∩ S = ∅ and R ∪ S ∈ Ind(F ). For such pair let Stab(R, S, t, `) be the set of sequences of the
form ϕ = (R, I2 , . . . , Is ) with s ≤ ` that satisfy one of the following:
• |s| = 1 (i.e. ϕ = (R)) and S = ∅;
4

Note that Bissacot et al. [3] proved that the cluster expansion condition implies Shearer’s condition, so it would
suffice to prove just the second claim. However, the definition of the cluster expansion condition in [3] was slightly
stronger: the sum in (2b) was taken over S ∈ Ind(Γ+ (f )), while we sum over S ∈ Ind(Γ(f )). Due to this annoying
technicality we consider the two cases separately in the proof.

24

• |s| ≥ 2, S = I2 − Γ(I1 ) and (I2 , . . . , Is ) ∈ Stab.
It can be seen that Stab(R, ∅, t, ∞) = Stab(R, t) for an independent set R.
We say that a tuple (R, S, t, `) is valid if (R, S) is an independent pair and t ≥ 0, ` ≥ 1 are
integers. We will prove the following for any valid tuple (R, S, t, `):
X
λϕ ≤ µ(R)µ(S) · θt
(19)
ϕ∈Stab(R,S,t,`)

Let us introduce a partial order v on tuples (R, S, t, `) as the lexicographical order on vectors (`, |R|)
(the first component is more significant). We use induction on this partial order. The base case is
given by a tuple (R, S, t, 1). We can assume that S = ∅ and t ≤ |R| (otherwise Stab(R, S, t, 1) is
empty). In this case Stab(R, S, t, 1) contains a single sequence ϕ = (R), and so
Y
Y
X
λϕ =
λf ≤
(µf · θ) = µ(R) · θ|R| ≤ µ(R) · θt
ϕ∈Stab(R,∅,t,1)

f ∈R

f ∈R

where we used inequality λf ≤ µf · θ that follows from condition (2b) with S = ∅.
Now consider a valid tuple (R, S, t, `) with ` ≥ 2, and assume that the claim holds for lower
tuples. Two cases are possible.
• R = ∅. We have a natural isomorphism between sets Stab(∅, S, t, `) and Stab(S, ∅, t, ` − 1),
namely Stab(∅, S, t, `) = {(∅, I1 , . . . , Ir ) | (I1 , . . . , Ir ) ∈ Stab(S, ∅, t, ` − 1)}. This gives
X
X
λϕ =
λϕ ≤ µ(S) · θt
ϕ∈Stab(∅,S,t,`)

ϕ∈Stab(S,∅,t,`−1)

where in the last inequality we used the induction hypothesis.
• R 6= ∅. Pick f ∈ R, and denote R− = R − {f }. Let Γ̃(f ) be the set of flaws g ∈ Γ(f ) that
(i) can occur in the second set of a sequence ϕ ∈ Stab(R, S, t, `), and (ii) do belong to Γ(f 0 )
for any f 0 ∈ R− . Formally, Γ̃(f ) = {g ∈ Γ(f ) | g  f 0 for all f 0 ∈ R ∪ S}. We can write
X
X
X
λϕ =
λf · λϕ
T ∈Ind(Γ̃(f )) ϕ∈Stab(R− ,S∪T,t−1,`)

ϕ∈Stab(R,S,t,`)
(a)

X

≤ λf

µ(R− )µ(S ∪ T ) · θt−1

T ∈Ind(Γ̃(f ))
(b)

= µ(R)µ(S)θt−1 ·

λf
µf

X

µ(T )

T ∈Ind(Γ̃(f ))

(c)

≤ µ(R)µ(S)θt−1 · θ

where (a) is by the induction hypothesis, (b) is true since µ(R− ) = µ(R)/µf and µ(S ∪ T ) =
µ(S)µ(T ), and (c) follows from condition (2b).

Acknowledgements The author is supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160.

25

References
[1] Dimitris Achlioptas and Fotis Iliopoulos. Random walks that find perfect objects and the
Lovász local lemma. In 55th IEEE Annual Symposium on Foundations of Computer Science
(FOCS), pages 494–503, 2014.
[2] Dimitris Achlioptas and Fotis Iliopoulos. Focused stochastic local search and the Lovász local
lemma. In SODA, 2016.
[3] R. Bissacot, R. Fernández, A. Procacci, and B. Scoppola. An improvement of the Lovász local
lemma via cluster expansion. Combin. Probab. Comput., 20:709–719, 2011.
[4] Julia Böttcher, Yoshiharu Kohayakawa, and Aldo Procacci. Properly coloured copies and rainbow copies of large graphs with small maximum degree. Random Structures and Algorithms,
40(4):425–436, 2012.
[5] P. Erdős and L. Lovász. Problems and results on 3-chromatic hypergraphs and some related
questions. In Colloq. Math. Soc. J. Bolyai, Infinite and Finite Sets, volume 10, pages 609–627.
North-Holland, 1975.
[6] P. Erdős and J. Spencer. The lopsided Lovász local lemma and latin transversals. Discrete
Applied Mathematics, 30:151–154, 1991.
[7] Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, , and Dimitrios M. Thilikos. On the
algorithmic Lovász local lemma and acyclic edge coloring. In Proceedings of ANALCO, 2015.
[8] David G. Harris and Aravind Srinivasan. A constructive algorithm for the Lovász local lemma
on permutations. In SODA, pages 907–925, 2014.
[9] Nicholas Harvey and Jan Vondrák. An algorithmic proof of the Lovász local lemma via resampling oracles. In FOCS, 2015.
[10] Donald Knuth.
The art of computer programming, Volume 4B (draft, pre-fascicle
6a). http://web.archive.org/web/20150815030301/http://www-cs-faculty.stanford.
edu/~uno/news.html, July 2015.
[11] Kashyap Babu Rao Kolipaka and Mario Szegedy. Moser and Tardos meet Lovász. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC, pages
235–244, 2011.
[12] Vladimir Kolmogorov. Commutativity in the random walk formulation of the Lovász local
lemma. CoRR, abs/1506.08547v1, June 2015.
[13] Vladimir Kolmogorov. Commutativity in the algorithmic Lovász local lemma. In FOCS, 2016.
[14] Lincoln Lu, Austin Mohr, and László Székely. Quest for negative dependency graphs. In
D. Bilyk, L. De Carli, A. Petukhov, A.M. Stokolos, and B.D. Wick, editors, Recent Advances
in Harmonic Analysis and Applications. Springer, 2013.
[15] Austin Mohr. Applications of the lopsided Lovász local lemma regarding hypergraphs. PhD
thesis, University of South Carolina, 2013.
[16] Robin A. Moser and Gábor Tardos. A constructive proof of the general Lovász local lemma.
J. ACM, 57(2), 2010.
26

[17] Sokol Ndreca, Aldo Procacci, and Benedetto Scoppola. Improved bounds on coloring of graphs.
European Journal of Combinatorics, 33(4):592–609, 2012.
[18] Wesley Pegden. An extension of the Moser-Tardos algorithmic local lemma. SIAM Journal
on Discrete Mathematics, 28(2):911–917, 2014.
[19] James B. Shearer. On a problem of Spencer. Combinatorica, 5(3):241–245, 1985.
[20] Mario Szegedy. The Lovász local lemma - a survey. In Andrei A. Bulatov and Arseny M.
Shur, editors, Computer Science Theory and Applications, volume 7913, pages 1–11. Springer,
Lecture Notes in Computer Science, 2013.

27

