Undefinability of Approximation of 2-To-2 Games

We are interested in $\mathrm{NP}$-hard optimization problems. A standard example is the problem MAX 3SAT, where the aim is to find, given a formula in 3CNF, an assignment of values to its variables that maximizes the number of clauses satisfied. Formally, consider a function problem $M$, which associates with every possible input instance $I$ a value $M(I)$. In our example, MAX 3SAT maps a formula $\varphi$ to the maximum number $m$ of clauses of $\varphi$ that can be simultaneously satisfied. While, in practice, we might be interested in finding an assignment that achieves this maximum, for the purpose of proving hardness, it suffices to show that it is hard to compute the number $m$. When finding $M(I)$ is hard, we may wish to approximate it, and we say that an algorithm computes a $C$-approximation (for a real number $C>1$) of $M$ if it produces a number $M^{\prime }(I)$ with the guarantee that $M^{\prime }(I)\le M(I)\le C\cdot M^{\prime }(I)$.

For the sake of uniformity, we consider function problems that take values in $[0,1]$. Thus, MAX 3SAT assigns to a 3CNF formula $\varphi$ the maximum fraction of the clauses of $\varphi$ that can be simultaneously satisfied. For MAX 3SAT, it is known that, unless $\mathrm{P}=\mathrm{NP}$, there is no polynomial-time algorithm that gives a $C$-approximation for any . Such hardness of approximation results are usually proved by means of a hardness of separation, which allows us to frame this in terms of the hardness of decision problems.

Formally, let $A$ and $B$ be two sets (i.e. decision problems) with $A\cap B=\mathrm{\varnothing }$. We say that $A$ and $B$ are $\mathrm{NP}$-hard to separate, if every set $C$ with $A\subseteq C\subseteq \overline{B}$ is $\mathrm{NP}$-hard, where $\overline{B}$ denotes the complement of $B$. For a function problem $M$, and a constant $c\in [0,1]$, denote by $c$-$M$ the set $\{I\mid M(I)\ge c\}$. Then, for constants $c$ and $s$ with , we say that the gap problem $\text{Gap}M(c,s)$ is $\mathrm{NP}$-hard if it is $\mathrm{NP}$-hard to separate the sets $c$-$M$ and $\overline{s\text{-}M}$. This implies, in particular, that unless $\mathrm{P}=\mathrm{NP}$, there is no polynomial-time algorithm giving a $\frac{c}{s}$-approximation of $M$. The value $c$ in $\text{Gap}M(c,s)$ is called the completeness parameter and $s$ the soundness parameter.

The first hardness of approximation results come from the PCP theorem [2, 15, 3]: one of its direct consequences is the $\mathrm{NP}$-hardness of $\mathrm{Gap}\text{3SAT}(1,\eta )$ for some constant $\eta$ strictly less than $1$. Håstad [17] obtained an optimum inapproximability result for MAX 3SAT. Namely, he showed that $\mathrm{Gap}\text{3SAT}(1,\frac{7}{8}+ϵ)$ is $\mathrm{NP}$-hard for arbitrarily small $ϵ$. This is optimal since there is an easy $\frac{8}{7}$-approximation algorithm. Similarly, he also showed that $\mathrm{Gap}\text{3XOR}(1-ϵ,\frac{1}{2}+ϵ)$ is $\mathrm{NP}$-hard for arbitrarily small $ϵ$. Again, this is optimal. Here, 3XOR is the problem where we are given a Boolean formula as a conjunction of clauses, each of which is the XOR of three literals and we aim to maximize the number of satisfied clauses. Note that the completeness parameter must be strictly less than $1$, since the problem of determining whether such a formula is satisfiable or not is polynomial-time decidable. Thus $1$-3XOR can be separated in polynomial time from $\overline{(1-ϵ)\text{-}\text{3XOR}}$ for any $ϵ$.

Versions of label cover problems are ubiquitous in the study of hardness of approximation (see [13]). A particularly important case are the unique games of Khot [18], defined below. To arrive at the definition, we first introduce some terminology. For positive integers $d$ and $e$, a relation $R\subseteq U\times V$ is said to be $d$-to-$e$ if it relates each element of $U$ to exactly $d$ elements of $V$ and each element of $V$ to exactly $e$ elements of $U$.

In this paper, we are particularly interested in $2$-to-$2$ games and $1$-to-$1$ games, the latter also being known as Unique Games. We write ${\mathrm{UG}}_q$ for the function problem of determining the value of an instance of unique games with an alphabet of size $q$. We can then state Khot’s unique games conjecture.

The significance of the conjecture is that it has been shown that many optimal hardness of approximation results follow from it, including $\mathrm{Max}\mathrm{Cut}$ and $\mathrm{Vertex}\mathrm{Cover}$ [19, 23, 18].

The best known hardness result for unique games, towards proving Conjecture 2.2 is that ${\mathrm{GapUG}}_q(\frac{1}{2}-ϵ,\delta )$ is $\mathrm{NP}$-Hard for arbitrarily small $\delta$ and $ϵ$. This is obtained as a consequence of the hardness of $2$-to-$2$ games established by Khot, Minzer and Safra, which we return to in Section 3.

It is conjectured that Theorem 2.3 can be strengthened to make the completeness parameter $1$, but this remains unproved.

In this paper, we are particularly concerned with weighted $2$-to-$2$ and $1$-to-$1$ games, attaching a weight to each constraint.

We write $𝒲{𝒢}_{2:2;q}$ to denote the class of weighted $2$-to-$2$ games with $q$ labels and ${\text{Weight2to2}}_q$ to denote the function taking such a game to its value. Similarly, we write ${\text{UG}}_q$ and ${\text{WeightUG}}_q$ for the functions giving the values of unique games and weighted unique games with $q$ labels respectively.

We assume the reader is familiar with first-order logic and the basics of finite model theory. A good introduction is to be found in [14]. Our structures are finite structures in a finite relational vocabulary. Our main inexpressibility results are stated for fixed-point logic with counting ($\mathrm{FPC}$). We do not need a formal definition here but note that every property definable in $\mathrm{FPC}$ is decidable in polynomial-time and indeed $\mathrm{FPC}$ can be understood as a complexity class defined by symmetric polynomial-time computation. For full definitions, refer to [10] and references therein.

The two properties of $\mathrm{FPC}$ that we do need are that (1) every class of structures definable in $\mathrm{FPC}$ has bounded counting width; and (2) that the class of properties definable in $\mathrm{FPC}$ is closed under first-order interpretations. We elaborate on these below.

For a function problem $M$, and real numbers $c$ and $s$ with , we say that $\text{Gap}M(c,s)$ is undefinable in $\mathrm{FPC}$ if there is no $\mathrm{FPC}$ definable class of structures that separates the sets $c$-$M$ and $\overline{s\text{-}M}$. Atserias and Dawar [6] initiated a study of the $\mathrm{FPC}$ undefinability of approximations, showing that many of the $\mathrm{NP}$-hardness results for gap problems can be reproduced as unconditional undefinability results in $\mathrm{FPC}$. In particular $\mathrm{Gap}\text{3SAT}(1,\frac{7}{8}+ϵ)$ is not $\mathrm{FPC}$ definable. More significantly, they established the following

Note the completeness parameter of $1$ in the statement, which contrasts with $1-ϵ$ in the case of Theorem 2.3. Perfect completeness cannot be established in the case of $\mathrm{NP}$-hardness because satisfiability of XOR formulas is decidable in polynomial-time. However, it is not definable in $\mathrm{FPC}$ and this allows the stronger result in the context of undefinability. This is crucial to the application we make of Theorem 2.5 in Section 5.3

Following up on this work, Tucker-Foltz [26] studied the undefinability of gaps in unique games. In particular, he established the inapproximability of unique games in $\mathrm{FPC}$ by any constant factor and the $\mathrm{FPC}$-undefinability of ${\mathrm{GapUG}}_q(\frac{1}{2},\frac{1}{3}+\delta )$ for a suitable value of $q$.

An instance of 3XOR can be seen as a system of linear equations over the field ${𝔽}_2$ with exactly three variables appearing in each equation. We say that such an instance is $d$-regular if every variable appears in exactly $d$ equations and no two equations share more than one variable. It is known that the $\mathrm{NP}$-hardness of $\mathrm{Gap}\text{3XOR}(1-ϵ,\frac{1}{2}+\delta )$ holds even when restricted to $d$-regular instances for some fixed value of $d$ (indeed, taking $d=5$ suffices, see [22, Theorem 3.3.1]). In Section 4.3 we show that this is also true of the undefinability in $\mathrm{FPC}$ of $\mathrm{Gap}\text{3XOR}(1,\frac{1}{2}+\delta )$ From now on, we restrict attention to $d$-regular instances for a suitable fixed value of $d$, and we call the resulting function problem $\mathrm{Gap}\text{Regular3XOR}$.

In the first step of the reduction, we reduce regular 3XOR instances to label cover games with a mixture of $2$-to-$2$ and $1$-to-$1$ constraints, with an additional transitivity requirement. We formally define these below.

Note that the condition on composition only applies when $\mathrm{\Phi }(u,v)$ is $1$-to-$1$, but $\mathrm{\Phi }(v,w)$ may be $1$-to-$1$ or $2$-to-$2$, and this determines whether $\mathrm{\Phi }(u,w)$ is $1$-to-$1$ or $2$-to-$2$.

Now, fix an instance $I$ of GapRegular3XOR, with $X$ being the set of variables that appear in $I$ and $E$ the set of equations. Thus, each equation $e\in E$ is of the form $x+y+z=b$ for some $b\in {𝔽}_2$. We refer to $x,y$ and $z$ as the variables occurring in $e$ and $b$ as the right-hand side of $e$.

Fix a positive integer $k$ and let $𝒰\subseteq E^k$ be the set of $k$-tuples $U$ of equations, satisfying the following properties:

• $\mathrm{■}$

  no variable occurs in more than one equation of $U$; and

• $\mathrm{■}$

  if variables $x$ and $y$ appear in distinct equations of $U$, there is no equation in $E$ (even outside $U$) in which both $x$ and $y$ occur.

For $U=(e_1,\mathrm{\dots },e_k)\in 𝒰$, let $X_U$ denote the set of variables occuring in equations in $U$ and for $i\in \{1,\mathrm{\dots },k\}$ let $v_i\in {𝔽}_2^X$ denote the vector which has $1$s in the three coordinates corresponding to the variables occurring in $e_i$ and $0$s everywhere else. We define the space of side-conditions corresponding to $U$ to be $H_U=\mathrm{Span}(v_1,\mathrm{\dots },v_k)$. We say that a linear function $f:{𝔽}_2^X\to {𝔽}_2$ satisfies the equations in $U$ if $f(v_i)=b_i$ for all $i$, where $b_i$ is the right-hand side of $e_i$.

Now, fix a parameter $l$ with $l\le |X|$, and we define ${ℒ}_U$ to be the collection of $l$-dimensional subspaces of ${𝔽}_2^X$ which are linearly independent of $H_U$. That is

The trivial intersection ensures that for any subspace $L\in {ℒ}_U$, any linear function $f:L\to {𝔽}_2$ can be uniquely extended to one on $L+H_U$²²2Here the sum is to be understood as vector space sum, i.e. $L+H_U$ is the space spanned by the union of $L$ and $H_U$. so that $f(v_i)=b_i$ for all $i$. Therefore, the number of linear functions on $L+H_U$ satisfying the equations in $U$ is exactly $2^l$.

We can now define the reduction $\mathrm{\Theta }$ that takes the instance $I$ to a $2$-to-$2$ transitive game $\mathrm{\Theta }(I)$. The reduction depends on the choice of parameters $k$ and $l$. We omit the details on how to select the right parameters.

The final step of the reduction is to transform the transitive game constructed in Section 3.2 into a weighted $2$-to-$2$ game, getting rid of the $1$-to-$1$ constraints. This weighted game is defined as follows.

Recall the transitive $2$-to-$2$ game $\mathrm{\Theta }(I)$ constructed in Section 3.2. The transitivity condition guarantees that the vertices of $\mathrm{\Theta }(I)$ can be partitioned into cliques $C_1,\mathrm{\dots },C_m$ so that edges in each clique are associated with $1$-to-$1$ constraints. Moreover, these constraints are consistent in the sense that any colouring of a vertex $V$ in a clique $C$ can be extended in a unique way to a colouring of all vertices in $C$ so that all edge constraints in $C$ are satisfied. Also, by the transitivity condition, for distinct cliques $C_i$ and $C_j$, either all pairs $(u,v)\in C_i\times C_j$ are connected by $2$-to-$2$ constraints or none are. Furthermore, these $2$-to-$2$ constraints are consistent in the sense that given a clique-consistent colouring for $C_i$ and $C_j$, either all or none of these $2$-to-$2$ constraints are satisfied.

The final (weighted) 2-to-2 instance $I_{2:2}^w$ we construct from $\mathrm{\Theta }(I)$ has as vertices the vertices of $\mathrm{\Theta }(I)$ and as edges all edges $(u,v)$ of $\mathrm{\Theta }(I)$ where $u$ and $v$ are in distinct cliques. For each such edge, with $u\in C_i$ and $v\in C_j$, we associate the constraint $\mathrm{\Phi }(u,v)$ which is as in $\mathrm{\Theta }(I)$. The weight $w(u,v)$ is the probability assigned to $(u,v)$ by the following sampling process:

• $\mathrm{■}$

  Choose $U\in 𝒰$, uniformly at random.

• $\mathrm{■}$

  Choose a random pair $L,L^{\prime }$ so that $(U,L)$ and $(U,L^{\prime })$ are connected by a $2$-to-$2$ edge. Let $C_i$ be the clique containing $(U,L)$ and $C_j$ be the clique containing $(U^{\prime },L^{\prime })$

• $\mathrm{■}$

  Choose uniformly at random a pair of vertices $(u,v)\in C_i\times C_j$.

For the result in Section 5.3, we need the $\mathrm{FPC}$-undefinability of a different gap problem based on $2$-to-$2$ games. Specifically, we define the value of a game to be, not the fraction of constraints that can be satisfied, but the fraction of the vertices formed by the largest set $X$ so that all constraints between nodes in $X$ are satisfied. Moreover, we relax the notion of colouring to allow vertices to be coloured by multiple colours.

That is to say, a $j$-colouring, i.e., one that assigns a set of $j$ colours to each vertex satisfies a set $X$ if each constraint between vertices in $X$ is satisfied by some choice among the colours assigned to the vertices.

We can now state the theorem below, which is a consequence of Theorem 3.1.

It is not hard to see that this is a consequence of Theorem 3.1, and the corresponding claim for $\mathrm{NP}$-hardness appears in e.g. [20]. For completeness, we give a short proof.

The definition of $2$-to-$2$ games, Definition 2.4 only requires each constraint $\mathrm{\Phi }(u,.v)$ to be a $2$-to-$2$ relation, meaning that each element on the left is related to exactly two elements on the right and vice versa. However, the reductions yield games of a more restricted kind and this will be useful in Section 5.3. Say that a binary relation $R\subseteq A\times B$ is $2\leftrightarrow 2$ if it is the disjoint union of bipartite graphs $K_{2,2}$. That is to say $A$ and $B$ can be each partitioned into sets $A={\bigcup }_i{A}_i$ and $B={\bigcup }_i{B}_i$ so that each $A_i$ and $B_i$ has exactly two elements and $R={\bigcup }_i{A}_i\times B_i$.

We claim that the reductions in the proof of Thereom 3.1 yield games in which all constraint relations are $2\leftrightarrow 2$. Specifically, given linear functions $f\ne f^{\prime }:L+H_U\to {𝔽}_2$ so that their unique extension to the domain $L+H_U+H_{U^{\prime }}$ only differ in their “free dimension”, i.e. they agree in values on $(L+H_U+H_{U^{\prime }})\cap (L^{\prime }+H_U+H_{U^{\prime }})$, $f$ and $f^{\prime }$ are related to the same two linear functions on $L^{\prime }+H_{U^{\prime }}$ (uniquely extensible to $L^{\prime }+H_U+H_{U^{\prime }}$) in $\mathrm{\Phi }((U,L),(U^{\prime },L^{\prime }))$. Thus, the constraint relations constructed are $2\leftrightarrow 2$.

To show that the reduction from Section 3 preserves perfect completeness, it suffices to verify that instances of 3XOR that are satisfiable (i.e. have value $1$) are mapped by the reduction to instances of $𝒲{𝒢}_{2:2}$ which also have value $1$.

Assume $I$ is an 3XOR instance on a set of variables $X$ that is satisfiable, and let $s:X\to {𝔽}_2$ be an assignment of values to the variables that satisfies it. Let $I_{2:2}^w$ denote the weighted $2$-to-$2$ game that $I$ maps to under the reduction. Then, for each vertex $(U,L)$ of $I_{2:2}^w$ the restriction of $s$ to $L+H_U$ is a valid label since all equations are satisfied, and it is easily seen that this labelling satisfies all constraints.

An instance of 3XOR is defined as a structure over the vocabulary ${\tau }_{3\mathrm{X}\mathrm{O}\mathrm{R}}=⟨{\mathrm{Eq}}_0,{\mathrm{Eq}}_1⟩$ with two ternary relations. We think of the universe of a ${\tau }_{3\mathrm{X}\mathrm{O}\mathrm{R}}$-structure $𝔸$ as a set of variables. For $b\in \{0,1\}$, a triple $(x,y,z)\in {\mathrm{Eq}}_b$ is understood as representing the equation $x+y+z=b$, where addition is modulo $2$.

For each positive integer $q$, we define a vocabulary ${\tau }_{{\text{(T) 2-to-2}}_q}$ such that structures in this vocabulary represent instances of transitive $2$-to-$2$ games over a label alphabet of size $q$. Let $S_q$ denote the collection of permutations of $[q]=\{1,\mathrm{\dots },q\}$. Note that there is a natural bijective correspondence between $S_q$ and the $1$-to-$1$ relations on $[q]$. Now, let $S_q^{\mathrm{\#}2}$ denote the set of pairs of permutations $({\pi }_1,{\pi }_2)\in S_q\times S_q$ such that for all $i\in [q]$, ${\pi }_1(i)\ne {\pi }_2(i)$. Then, it is easily seen that each $2$-to-$2$ relation on $[q]$ can be seen as the union of such a pair of permutations. Our vocabulary ${\tau }_{{\text{(T) 2-to-2}}_q}$ contains a binary relation for each element of $S_q$ and one for each element of $S_q^{\mathrm{\#}2}$:

We write ${𝒞}_1$ for the collection of relation symbols ${(C_{\pi })}_{\pi \in S_q}$ and ${𝒞}_2$ for the collection of relation symbols ${(C_{{\pi }_1,{\pi }_2})}_{({\pi }_1,{\pi }_2)\in S_q^{\mathrm{\#}2}}$. Note that the vocabulary itself does not enforce the transitivity property, only a subset of the structures with this vocabulary are transitive 2-to-2 games.

For weighted $2$-to-$2$ games, we construct a vocabulary that allows us to code instances with positive integer weights. This is more limiting than allowing rational weights, but as we show below in Section 4.6, it suffices for our purpose. Specifically,

where $C$ is unary, and the relations ${\mathrm{\Phi }}_{{\pi }_1,{\pi }_2}$ are all ternary. A ${\tau }_{{\text{(w) 2-to-2}}_q}$-structure $𝔸$ is to be understood as an instance $I_{2:2}^w=(G,\mathrm{\Sigma },\mathrm{\Phi })$ of ${𝒢}_{2:2}^w$ with integer weights. The universe of $𝔸$ is the disjoint union of the set $V$ of vertices of $I_{2:2}^w$, and the set $C$ of constraints, with the unary relation $C$ picking out this set. For each $({\pi }_1,{\pi }_2)\in S_q^{\mathrm{\#}2}$, the relation ${\mathrm{\Phi }}_{{\pi }_1,{\pi }_2}\subseteq V^2\times C$ contains those triples $(u,v,c)$ where $\mathrm{\Phi }(u,v)$ is a pair $(R,w)$ with $R$ being the $2$-to-$2$ relation associated with the pair $({\pi }_1,{\pi }_2)$. The integer weight $w$ is given by the number of elements $c$ for which $(u,v,c)$ is in the relation. We assume our structures satisfy the (first-order) axiom that ensures that there is at most one relation ${\mathrm{\Phi }}_{{\pi }_1,{\pi }_2}$ in which triples $(u,v,c)$ appear, for each choice of $u$ and $v$.

The reduction in Section 3 starts from regular games. In contrast, the undefinability result in Theorem 2.5 is stated for general 3XOR. Thus, we begin by arguing that the pfoof of Theorem 2.5 can actually be used to show the undefinability of $\mathrm{Gap}\text{Regular3XOR}(1,\eta )$ for some $\eta$ strictly smaller than $1$.

We first note that the $\mathrm{Gap}\text{3XOR}(1,\frac{1}{2}+\delta )$ is $\mathrm{FPC}$ undefinable even for “half-regular” 3XOR instances. That is, 3XOR instances where each variable appears in the same number of equations. To see this, note that Lemma 5 in [6] uses a bipartite unique-neighbour expander graph with $r|X|$ nodes on the left and $|X|$ nodes on the right. Thus the graph is $3$-left-regular and is an ($\alpha |X|,\beta )$ expander. Such graph exists for every $X$ by [27, Chapter 4]. By a variation shown for Theorem 4.4 in [27], we laim the existence of such a graph with the extra condition that the graph is right-regular. Using this extra assumption on the graph in Lemma 5 in [6] the proof establishes that $\mathrm{Gap}\text{3XOR}(1,\frac{1}{2}+\delta )$ is $\mathrm{FPC}$ undefinable even for “half-regular” 3XOR instances.

A half-regular instance can be converted into a regular one by ensuring that any two equations share at most one variable.

First, by the unique-neighbour expander property of the graph in Lemma 5 in [6], we can assume that the half-regular 3XOR instance has no repeated equations or repeated variables within an equation. This half-regular instance $(X,\mathrm{Eq})$ can be converted into a regular one (call it $(X^{\ast },{\mathrm{Eq}}^{\ast })$) by replacing every equation $e:x+y+z=b$ with three equations (as done in [22]): $x+y_e+z_e=b,x_e+y+z_e=b,x_e+y_e+z=b$, where $x_e,y_e$, and $z_e$ are new variables only used for these equations.

As shown in [22], if $X$ is fully satisfiable then so is $X^{\ast }$ and if $X$ is no more than $\frac{1}{2}+\delta$-satisfiable, then $X^{\ast }$ is at most $\eta$-satisfiable for some (for example, taking $\eta =0.9$ suffices).

The reduction can be easily defined by a first-order interpretation.

One issue that arises with the games constructed in the reduction from Section 3 is that we have a fixed alphabet of size $q=2^l$ and we associate with each vertex $(U,L)$ an arbitrary bijection between this and the $2^l$ distinct linear functions on the space $L+H_U$ that satisfy the equations in $U$. The consistency across different vertices is then enforced by the constraint relations. In order to turn this into a first-order reduction, we want to choose these bijections in a symmetry-preserving fashion.

Let $I$ be our starting instance of 3XOR and $I_{2:2}^T=\mathrm{\Theta }(I)$ the transitive $2$-to-$2$ game obtained from the first step of the reduction of Section 3, and let $X$ be the set of variables of $I$. Let $\rho \in {\text{Sym}}_X$ be a permutation of $X$. This permutation has a natural action on other objects constructed from $X$. In particular, for an equation $e$ of the form $x+y+z=b$, we write $\rho (e)$ for the equation $\rho (x)+\rho (y)+\rho (z)=b$. When $U$ is a tuple of such equations, we write $\rho (U)$ for the tuple obtained by applying $\rho$ componentwise to each element of the tuple. Similarly, for other objects obtained by set and tuple constructions from $X$, we apply the permutation $\rho$ to denote the natural induced action without defining it formally.

Furthermore, we also use $\rho$ to denote the invertible linear map on ${𝔽}_2^X$ obtained by applying $\rho$ to the basis ${(e_x)}_{x\in X}$, and extending linearly to all of ${𝔽}_2^X$. Thus, in particular, for a subspace $L\subseteq {𝔽}_2^X$, $\rho (L)$ denotes the image of this space under this map.

The following is now straightforward.

We now describe how the reduction $\mathrm{\Theta }$ from Section 3.2 can be given as a first-order interpretation. Fix positive integers $k$ and $l$, which are the parameters to the reduction. Given a (regular) 3XOR instance $𝔸=(X,{\mathrm{Eq}}_0^{𝔸},{\mathrm{Eq}}_1^{𝔸})$, our interpretation maps it to the following (transitive) $2$-to-$2$ game (with alphabet size $2^l$) $𝔹$.

We now show how to get a weighted $2$-to-$2$ game, that is an approximation of the instance $I_{2:2}^w$ constructed in Section 3.3. The vertices of the game are exactly those in the structure $𝔹$ above. The main task is to define the weights, by defining a suitable set $C$ of constraints. Recall that the vertices of $I_{2:2}^w$ are partitioned into cliques $C_1,\mathrm{\dots },C_m$ based on the $1$-to-$1$ constraints. Suppose $(U_1,L_1)\in C_i$ and $(U_2,L_2)\in C_j$ are two vertices connected by a $2$-to-$2$ constraint. Then, the weight of the constraint is

Each of the three factors (apart from the indicator variable) describes the probability of a certain choice in the steps of the random process which define the weights.

Of course, $\frac{1}{|𝒰|}$ is constant for all pairs $(U_1,L_1),(U_2,L_2)$. Similarly, $\frac{1}{|\{L,L^{\prime }\in {ℒ}_U\mid \dim (L\cap L^{\prime })=l-1\}|}$ is constant by the symmetry argument presented in Section 4.4. Thus, removing them from the expression does not change the relative weights of the constraints. Also, the clique size only depends on $(U_1,L_1),(U_2,L_2)$, so the weight expression (without the normalising factors) simplifies to