# The Exact Bipartite Matching Polytope Has Exponential Extension Complexity

Xinrui Jia Emails: xinrui.jia, ola.svensson<EMAIL_ADDRESS>This work
was supported by the Swiss National Science Foundation project 200021-184656
“Randomness in Problem Instances and Randomized Algorithms”. EPFL  Ola
Svensson††footnotemark:  EPFL  Weiqiang Yuan††footnotemark:  EPFL

###### Abstract

Given a graph with edges colored red or blue and an integer $k$, the exact
perfect matching problem asks if there exists a perfect matching with exactly
$k$ red edges. There exists a randomized polylogarithmic-time parallel
algorithm to solve this problem, dating back to the eighties, but no
deterministic polynomial-time algorithm is known, even for bipartite graphs.
In this paper we show that there is no sub-exponential sized linear program
that can describe the convex hull of exact matchings in bipartite graphs. In
fact, we prove something stronger, that there is no sub-exponential sized
linear program to describe the convex hull of perfect matchings with an odd
number of red edges.

##  1 Introduction

The perfect matching problem is a central question in combinatorial
optimization with a long and rich history. The first efficient (polynomial-
time) algorithm for bipartite graphs can be traced back more than a century to
Jacobi [1] and, for general graphs, a celebrated result by Edmonds [8] gave an
efficient algorithm in 1965. Furthermore, a very recent breakthrough shows
that we can even solve the problem in bipartite graphs in near-linear time
[6]. We thus have a very good understanding of the basic problem. In contrast,
and perhaps surprisingly, it remains a notorious problem to devise efficient
deterministic algorithms for slight variations. A prominent example is the
_exact perfect matching_ problem: given an integer $k$ and a graph where each
edge is colored either red or blue, the goal is to find a perfect matching
with exactly $k$ red edges or to determine that such a matching does not
exist.

This simple-to-state problem admits a very intriguing status that is related
to the power of randomness in algorithms. While there are several problems
that admit efficient _randomized_ algorithms but for which no efficient
deterministic algorithms are known, celebrated results in complexity theory
strongly indicate that all efficient randomized algorithms can in fact be
derandomized [15]. Thus, our inability to find deterministic algorithms for
problems that admit randomized ones is very likely due to a lack of
algorithmic techniques. The gap in our understanding of the exact matching
problem is especially large. If we restrict ourselves to deterministic
algorithms, then efficient algorithms are only known for very special graph
families such as complete graphs, complete bipartite graphs [12], bounded
independence number graphs, and FPT algorithms [9],[16]. In particular, we
have no deterministic _sequential_ algorithm that solves the above-mentioned
problem efficiently even on _bipartite graphs_. In contrast, if we allow for
randomness, then we have polylogarithmic-time _parallel_ algorithms that solve
them on _general graphs_. Specifically, Mulmuley, Vazirani, and Vazirani [17]
gave a beautiful randomized efficient parallel algorithm for finding perfect
matchings that generalizes nicely to variations such as the exact matching
problem.

The versatile randomized approach by Mulmuley, Vazirani, and Vazirani was
published in 1987 and there was little progress in derandomizing it for
decades. Then, in a relatively recent breakthrough [10], Fenner, Gurjar,
Thierauf almost completely derandomized their approach for the perfect
matching problem in bipartite graphs (almost since their deterministic
parallel algorithm requires quasi-polynomially many processors instead of
polynomially many). Building on the techniques in [10], the results have now
been extended to perfect matchings in general graphs [21], matroid
intersection [13], and totally unimodular polytopes [14]. In all of these
works, our excellent polyhedral understanding of these problems have been
crucial in the derandomization of [17]. A major difficulty in extending these
techniques to obtain a deterministic algorithm for the exact matching problem
is that we do not have a good polyhedral understanding, i.e., an amenable
description of the convex hull of the indicator vectors of exact perfect
matchings. The goal of this paper is to advance our polyhedral understanding
of the exact matching problem.

The convex hull of perfect matchings in bipartite graphs has a very simple and
small (linearly many inequalities) description. But what happens to the exact
matching problem in bipartite graphs? In other words, how much more complex is
this polytope when we introduce the constraint that the perfect matchings must
have exactly $k$ red edges? In this paper, we show that the description of the
polytope becomes significantly more complex and the exact perfect matching
problem cannot be solved by a linear program of subexponential size even for
bipartite graphs111We remark that this question only makes sense for bipartite
graphs and not for general graphs due to the breakthrough result by Rothvoss
[19]: already the perfect matching problem has exponential extension
complexity in general graphs.. More formally, we are given an instance
$\mathcal{I}_{n,k}=(G_{n}=(U,V,E),k)$, where $|U|=|V|=n$, and there are two
parallel edges, one each of red and blue, between every pair $u\in U$ and
$v\in V$. We define the associated polytope of $\mathcal{I}_{n,k}$ as the
convex hull of the characteristic vectors of all perfect matchings with
exactly $k$ red edges, i.e.
$P_{\mathcal{I}_{n,k}}:=\mathrm{conv}(\\{\chi^{M}:M\text{ is a perfect
matching}\land|\\{e:e\in M\land e\text{ is
red}\,\\}|=k\\})\subseteq\mathbb{R}^{E}$. Our main result is that the polytope
$P_{\mathcal{I}_{n,k}}$ has exponential extension complexity.

###### Theorem 1.1

For all $n>0$, there exists some $k:=k(n)$ such that
$\mathrm{xc}(P_{\mathcal{I}_{n,k}})=2^{\Omega(n)}$.

###### Remark 1.1

Theorem 1.1 can be strengthened in the following way: fix any constant
$\epsilon>0$, then for all $n>0$ and $\epsilon n\leq k\leq(1-\epsilon)n$,
$\mathrm{xc}(P_{\mathcal{I}_{n,k}})=2^{\Omega(n)}$. This stronger result
directly follows from the simple observation that for any
$n,k,n^{\prime},k^{\prime}$ such that $k^{\prime}\geq
k,n^{\prime}-k^{\prime}\geq n-k$, $P_{\mathcal{I}_{n,k}}$ is isomorphic to
some face of $P_{\mathcal{I}_{n^{\prime},k^{\prime}}}$.

In fact, our paper proves a stronger result. Consider the following problem:
we are given a bipartite graph where each edge is colored either red or blue.
Instead of finding a perfect matching with exactly $k$ red edges, we aim to
find a perfect matching with an odd number of red edges. We call this problem
_parity bipartite perfect matching_. Given the graph $G_{n}=(U,V,E)$, let
$\mathcal{M}_{\mathrm{all}}(G_{n})$ denote the set of all perfect matchings of
$G_{n}$ with an odd number of red edges. The (odd-)parity bipartite perfect
matching polytope associated with $G_{n}$ is defined as
$P_{G_{n}}:=\mathrm{conv}(\\{\chi^{M}:M\in\mathcal{M}_{\mathrm{all}}(G_{n})\\})$.
We show that this polytope has exponential extension complexity.

###### Theorem 1.2

For all $n>0$, $\mathrm{xc}(P_{G_{n}})=2^{\Omega(n)}$.

Note that $P_{G_{n}}=\mathrm{conv}(\cup_{k\text{ odd}}P_{\mathcal{I}_{n,k}})$.
Using the following basic fact in [3] on the extension complexity of the
convex hull of a union of polytopes, one can directly deduce Theorem 1.1 from
Theorem 1.2.

######  Fact 1.1 ([3])

Let $P_{1},\ldots,P_{k}$ be a set of polytopes. Then $\mathrm{xc}(\cup_{1\leq
i\leq k}P_{i})\leq\sum_{i=1}^{k}\mathrm{xc}(P_{i})$.

###### Remark 1.2

First, our result also applies to perfect matching with an even (instead of
odd) number of red edges (See Claim 3.1 and Remark 3.1). Second, our result
also applies to simple graphs because we can replace parallel edges with a
gadget to get a simple graph. The gadget is as follows: replace each parallel
edge $(u,v)$ with a path of length three by adding two vertices, $x_{r}$,
$y_{r}$ for the vertices subdividing the red edge and $x_{b}$, $y_{b}$ for
subdividing the blue edge. The color of the new edge $(u,x_{r})$ is red and
all others are blue. Then if neither color edge of $(u,v)$ is used in a
perfect matching in the multigraph it means that vertices $u$ and $v$ are both
matched by other edges so we can find a perfect matching in the simple graph
by taking $(x_{r},y_{r})$ and $(x_{b},y_{b})$ of the simple graph, and this
doesn’t change the number of red edges. If the blue edge of $(u,v)$ is taken
in the multigraph then in the simple graph we take $(u,x_{b})$, $(y_{b},v)$,
and $(x_{r},y_{r})$. Otherwise take $(u,x_{r})$, $(y_{r},v)$, and
$(x_{b},y_{b})$, and note that we take one red edge in the simple graph
exactly when one red edge is taken in the multigraph. It is not difficult to
see that this gadget reduction preserves the extension complexity. In the
simple graph we can let $x_{(u,v)}$ be the indicator variable for $(u,x_{r})$
(and $(y_{r},v)$) and then $1-x_{(u,v)}$ is the indicator variable for
$(x_{r},y_{r})$ since $(u,x_{r})$ and $(y_{r},v)$ are always taken together,
exactly when $(x_{r},y_{r})$ is not taken. Then it is clear that the polytope
for perfect matchings with an odd number of red edges in the simple graph can
be projected down to the original multigraph and thus has no smaller extension
complexity (in fact they are isomorphic so they have the same extension
complexity).

#### Further related work.

While we show that the extension complexity of the parity bipartite perfect
matching problem is exponential, the weighted version of parity bipartite
perfect matching admits a deterministic polynomial-time algorithm. One first
computes a min-weight perfect matching, and should this matching have an even
number of red edges, then compute a min-weight alternating cycle with an odd
number of red edges and output the symmetric difference. This can be done in
polynomial time which is implied by a more general result by Artmann,
Weismantel, and Zenklusen [2] on so-called network matrices, which also
capture bipartite matchings. [2] also gave a strongly polynomial-time
algorithm for solving integer programs where the constraint matrix with rank
$n$ is bimodular, i.e. all determinants of $n\times n$ sub-matrices are
bounded by 2 in absolute value. Their first step is to reduce bimodular
integer programming to a totally unimodular integer linear program with an
additional parity constraint, which is a generalization of the parity matching
problem in bipartite graphs. While it is known that certain such problems have
exponential extension complexity [5] via a close connection to the perfect
matching problem in general graphs, it is unlikely that there is a simple
reduction to our problem. In particular, the algorithm for totally unimodular
matrices with a parity constraint is much more complex than the one for the
parity bipartite perfect matching problem.

Other work related to the extension complexity of the matching polytope
include [4] in which the authors generalize the result of [19] by exploring
the approximability of the matching polytope by a linear program. A tight
bound is obtained for a $(1+\epsilon)$-approximation when $\epsilon\in
O(1/n)$. The work in [20] extends the tight lower bounds to all $\epsilon$,
$2/n\leq\epsilon\leq 1$.

###  1.1 Proof Overview

Our proof of the exponential extension complexity of the parity bipartite
perfect matching polytope follows the recipe of Rothvoss’s proof of the
exponential extension complexity of the matching polytope [19]. The end goal
is to demonstrate an exponential lower bound on the non-negative rank of a
slack matrix of inequalities valid for the polytope. However, we have three
fundamental differences when applying this recipe to our problem. The first is
that while the polytope of matchings in general graphs is well-understood (by
the work of Edmonds [7]) and automatically provides a set of inequalities to
be used in the slack matrix, there was no such set of inequalities known for
the parity bipartite matching problem until this work. In addition to the
standard vertex-degree constraints of the bipartite perfect matching polytope,
we have inequalities resulting from what we call labels and these are used to
exhibit an exponential lower bound on the non-negative rank of the slack
matrix. In Section 3, we describe this relaxation in detail and in Section 5
we prove that our relaxation is empty if and only if the graph has no perfect
matching with an odd number of red edges. We leave it as an interesting open
problem to resolve whether or not our relaxation is in fact integral.

The second issue we now face is that we have a problem in a bipartite graph.
The convex hull of integral matchings in bipartite graphs can be expressed by
just linearly many inequalities and we lose the structure of odd-cuts that
Rothvoss uses in his slack matrix. In other words, we have to define our own
concept of partitions that exploits the characteristics of the parity problem.
Our partitions are defined in Section 4.2 and the remainder of Section 4
proves the main technical ingredient, Lemma 4.2, which states that large-
enough rectangles cover too many entries of large slack to be able to
decompose into a subexponential-sized non-negative factorization. In order to
follow the framework of Rothvoss, we need our definition of partitions and
triples of sets to allow us to generate entries in the slack matrix. For a
fixed triple and fixed rectangle, we can look at the probability that a
uniformly random matching (or labeling) selected from all matchings (or
labelings) that respect the triple lies in the rectangle. In particular, these
triples need to be defined in such a way that the measure of small- and large-
slack entries is an expectation over all partitions of the product of the
above described probabilities. Then instead of directly comparing the entries
in the slack matrix we can compare the contribution of triples to small- and
large-slack entries. We use the same naming convention as Rothvoss and split
our triples into three categories: good, small, and bad. Roughly speaking,
good triples are those where generated matchings and labelings are almost
uniform, small triples have small contribution anyway, and bad triples are
neither of the first two. Their formal treatments can be found in Sections
4.4, 4.5, and 4.6, respectively.

Our third challenge is a technical one and is regarding the contribution of
good triples. The details can be found in Section 4.5. Rothvoss uses a
partition structure given in a pair of sets and is able to show that for a
large enough non-zero rectangle, the second set in good pairs that generate
slack-2 entries cannot overlap on more than one element. Hence, large-enough
rectangles cover too few small-slack entries to be decomposed into a small
non-negative factorization of the slack matrix. This argument does not quite
work for us. We require an extra condition on the structure of the triples to
be able to use this approach, which we get in part as a consequence of the
partitions we set up. We also need to take permutations on the part of the
partition that generates positive slack entries and use the probabilistic
method to show that a certain family of permutations exists.

##  2 Preliminaries

In our paper, a set can be either ordered or unordered. We will use bold
letters to denote sequences (ordered sets) and non-bold letters to denote
unordered sets. For example, $\mathbf{A}$ is a sequence while $B$ is an
unordered set.

We specify each edge $e\in E$ by a triple $(u,v,c)$, where $u\in U$ and $v\in
V$ are two vertices and $c$ is the color of the edge (either red or blue).

The extension complexity of a polytope $P$, denoted by $\mathrm{xc}(P)$, is
the smallest integer $r>0$ such that $P$ is a linear projection of some
$r$-facet polytope $Q$.

Let $P$ be a polytope with vertices $x_{1},\ldots,x_{l}$, i.e.
$P=\mathrm{conv}(x_{1},\ldots,x_{l})$, and let $C$ be a set of inequalities
$C=\\{a_{i}^{\top}x\leq b_{i}:1\leq i\leq m\\}$ such that $P$ is feasible
w.r.t. all the inequalities in $C$, i.e. $P\subseteq\\{x:a_{i}^{\top}x\leq
b_{i},\forall 1\leq i\leq m\\}$. Define the slack matrix of $P$ w.r.t. $C$,
denoted $S(P,C)$, as an $l\times m$ non-negative real matrix with
$S(P,C)_{i,j}:=b_{j}-a_{j}^{\top}x_{i}$.

Given a non-negative rank matrix $S\in\mathbb{R}^{n\times m}_{\geq 0}$, we use
$\mathrm{rk}^{+}(S)$ to denote the non-negative rank of $S$, which is defined
as the smallest positive integer $r$ such that $S$ can be written as the sum
of $r$ non-negative rank-1 matrices, or equivalently,
$S=\sum_{i\in[r]}u_{i}v^{\top}_{i}$, where $u_{i}\in\mathbb{R}^{n}_{\geq
0},v_{i}\in\mathbb{R}^{m}_{\geq 0}$ are non-negative vectors.

######  Theorem 2.1 ([22])

Given a polytope $P$ and a set of inequalities $C=\\{a_{i}^{\top}x\leq
b_{i}:1\leq i\leq m\\}$, if the inequalities in $C$ exactly characterize $P$,
i.e. $P=\\{x:a_{i}^{\top}x\leq b_{i},\forall 1\leq i\leq m\\}$, then
$\mathrm{xc}(P)=\mathrm{rk}^{+}(S(P,C))$.

Note that the above theorem holds for any linear inequality characterization
of $P$. This implies that the non-negative rank of the slack matrix associated
with a loose linear inequality characterization is a lower bound for the
extension complexity, since we can make the characterization tight by adding
inequalities and the non-negative rank of a matrix is no smaller than that of
its submatrix.

###### Corollary 2.1

Given a polytope $P$ and a set of inequalities $C=\\{a_{i}^{\top}x\leq
b_{i}:1\leq i\leq m\\}$, if $P$ is feasible w.r.t. all the inequalities in
$C$, then $\mathrm{rk}^{+}(S(P,C))\leq\mathrm{xc}(P)$.

Exactly characterizing the non-negative rank of a matrix is usually difficult.
In [11], the authors use the covering number to give a lower bound for the
non-negative rank. Unfortunately, in our setting, the covering number is too
loose. We will use the following stronger tool from [19] based on hyperplane
separation.

######  Lemma 2.1 ([19])

Let $S\in\mathbb{R}_{\geq 0}^{l\times m}$ be a non-negative real matrix. Then
for any real matrix $W\in\mathbb{R}^{l\times m}$ with at least one positive
entry,

$\mathrm{rk}^{+}(S)\geq\frac{\langle
W,S\rangle}{\|S\|_{\infty}\cdot\max\\{\langle
W,uv^{\top}\rangle:u\in\\{0,1\\}^{l},v\in\\{0,1\\}^{m}\\}}.$

Here, $\langle W,S\rangle:=\sum_{i=1}^{l}\sum_{j=1}^{m}S_{ij}\cdot W_{ij}$ is
the Frobenius inner product.

##  3 Relaxation of the Polytope

In this section, we exhibit a set of inequalities with a nice structure that
is valid for the parity bipartite perfect matching polytope and suffices to
show this polytope has exponential extension complexity. The intuition behind
our relaxation is the following basic idea: if we have a collection of
disjoint 4-cycles where each cycle has alternating red and blue edges then it
is clear that there is no perfect matching with an odd number of red edges.
Similarly, take the bipartite graph in Figure 1 where we partition $U$ into
$U_{0}\sqcup U_{1}$ and $V$ into $V_{0}\sqcup V_{1}$ where for simplicity
suppose for now that $|U_{0}|=|V_{1}|$. Any perfect matching must take the
same number of edges from $(U_{0},V_{0})$ as from $(U_{1},V_{1})$ since
$|U_{0}|=|V_{1}|$. Hence, if all edges in $(U_{0},V_{0})$ and $(U_{1},V_{1})$
are red and all others are blue, this graph does not have a perfect matching
with an odd number of red edges. We now formally give the relaxation in full
generality which is based on this construction.

As aforementioned, our inequalities come from the vertex labelings of $G$.
Define

$\mathcal{L}_{\mathrm{all}}(G):=\\{L:U\cup
V\rightarrow\\{0,1\\}:|L^{-1}(1)|\equiv n\pmod{2}\\}$

as the set of 0-1 labelings for which the number of ones has the same parity
as $n$. We associate each labeling $L\in\mathcal{L}_{\mathrm{all}}(G)$ with a
set of edges

$E_{L}:=\\{e=(u,v,c):L(u)=L(v),c=\mbox{blue}\\}\cup\\{e=(u,v,c):L(u)\neq
L(v),c=\mbox{red}\\}.$

We claim that for any perfect matching $M$ with an odd number of red edges,
there must be some edge in $M$ that belongs to $E_{L}$ for every labeling $L$.
We say a colored edge $e=(u,v,c)$ violates a labeling $L$ if $e\in E_{L}$.
Otherwise, we say that it is correct or consistent with respect to a
labelling.

$U_{0}$$V_{0}$$U_{1}$$V_{1}$ Figure 1: This graph does not have a perfect
matching with an odd number of red edges.

###### Claim 3.1

Let $M\in\mathcal{M}_{\mathrm{all}}(G)$ and
$L\in\mathcal{L}_{\mathrm{all}}(G)$. Then $|M\cap E_{L}|\geq 1$.

  * Proof.

For a contradiction, suppose $M\subseteq E\setminus E_{L}$. Let
$U_{t}:=\\{u\in U:L(u)=t\\}$ and $V_{t}:=\\{v\in V:L(v)=t\\}$. See Figure 1
for a diagram. Let $x:=|M\cap E(U_{1},V_{1})|$ be the number of edges between
$U_{1}$ and $V_{1}$ in $M$. Since $M$ is perfect, $|M\cap
E(U_{0},V_{1})|=|M\cap E(U,V_{1})|-|M\cap E(U_{1},V_{1})|=|V_{1}|-x$. By the
same argument, we have $|M\cap E(U_{0},V_{0})|=(n-|U_{1}|)-(|V_{1}|-x)$.

Since $M\subseteq E\setminus E_{L}$, $\\{e\in M:e\text{ is red}\\}=(M\cap
E(U_{1},V_{1}))\cup(M\cap E(U_{0},V_{0}))$. Thus

$|\\{e\in M:e\text{ is red}\\}|=n-|U_{1}|-|V_{1}|+2x$ (3.1)

is even since $n$ and $|U_{1}|+|V_{1}|=|L^{-1}(1)|$ have the same parity,
leading to a contradiction.

By Claim 3.1, the following relaxation is valid for the parity bipartite
perfect matching polytope.

$\displaystyle\sum_{e\in\delta(u)}x_{e}$ $\displaystyle=1\quad\mbox{for all
}u\in U\cup V$ $\displaystyle\sum_{e\in E_{L}}x_{e}$ $\displaystyle\geq
1\quad\mbox{for all }L\in\mathcal{L}_{\mathrm{all}}(G)$ ($C_{G}$)
$\displaystyle x_{e}$ $\displaystyle\geq 0\quad\mbox{for all $e\in E$}.$

###### Remark 3.1

Note that the relaxation can be formulated for an even number of red edges by
letting $\mathcal{L}_{\mathrm{all}}(G)$ to be the set of labels such that
$|L^{-1}(1)|$ and $n$ have different parities for all
$L\in\mathcal{L}_{\mathrm{all}}(G)$ .

Let $C_{G}$ be the set of constraints above. Recall that $P_{G}$ is the parity
bipartite perfect matching polytope associated with $G$. As Theorem 3.1 shows,
$P_{G}$ is feasible w.r.t. all the inequalities in $C_{G}$. By Corollary 2.1,
to prove Theorem 1.2, it suffices to show the following theorem.

###### Theorem 3.1

For all $n>0$, $\mathrm{rk}^{+}(S(P_{G},C_{G}))=2^{\Omega(n)}$.

Now we can see why the covering number is loose. In fact, it is very similar
to the observation made in [22] that the covering number is insufficient to
show that the perfect matching polytope has exponential extention complexity.
Consider only the labeling constraints. For any pair $e_{1}$, $e_{2}$ of non-
adjacent edges, let $\mathcal{L}_{e_{1},e_{2}}$ be the set of labelings that
are violated by $e_{1}$ and $e_{2}$ and let $\mathcal{M}_{e_{1},e_{2}}$ be the
set of perfect matchings that contain $e_{1}$ and $e_{2}$. By Claim 3.1 we
have that the slack entry $(M,L)$ is non-zero for any
$M\in\mathcal{M}_{e_{1},e_{2}}$ and $L\in\mathcal{L}_{e_{1},e_{2}}$ so the
$O(n^{4})$ rectangles of the form
$\mathcal{L}_{e_{1},e_{2}}\times\mathcal{M}_{e_{1},e_{2}}$ are a valid
rectangle covering. However, an entry with slack $\ell$ lies in
${\ell+1\choose 2}$ rectangles since there are $\ell+1$ edges that are
violating. So we do not get a valid non-negative factorization of the slack
matrix as $O(n^{4})$ many $0/1$ rank-1 matrices, for the same reason as in
[19] that large entries are over-covered. Nonetheless, we will use the
hyperplane separation bound to give an exponential lower bound on the
extension complexity of the parity bipartite matching polytope.

##  4 Proof of Theorem 3.1

In this section we prove Theorem 3.1. From now on, we will focus on the case
when $n=4k(2m+1)+3$ is odd, where $k\geq 400$ is some large constant and $n$
grows with $m$. In particular, our proof works only when $m$ is sufficiently
large, say greater than $20\cdot(4k)!$.

As mentioned in the previous section, our proof for Theorem 3.1 relies on
Lemma 2.1. In Section 4.1, we construct the weight function $W$ which gives an
exponential lower bound in Lemma 2.1. The weight function consists of two key
components: $\mu_{3}$ and $\mu_{4k+3}$ which are distributions on slack-$2$
and slack-$(4k+2)$ entries respectively. Then we convert our problem into
finding $\mu_{3},\mu_{4k+3}$ and proving that any large rectangle w.r.t.
$\mu_{3}$ disjoint from slack-$0$ entries must over-cover $\mu_{4k+3}$. Before
describing $\mu_{3}$ and $\mu_{4k+3}$, we introduce the notion of partitions
in Section 4.2, which will be crucial in generating the distributions. The
idea is that for any fixed partition, we can compare the measures $\mu_{3}$
and $\mu_{4k+3}$ on the entries of a rectangle that are induced by the
partition. In Section 4.3, we use partitions to express $\mu_{3}$ and
$\mu_{4k+3}$ as sums of product distributions. In particular, each product
distribution for $\mu_{3}$ is represented by a triple $(T,H,\mathbf{D})$. To
give an upper bound on $\mu_{3}$ in terms of $\mu_{4k+3}$, in Section 4.4, we
classify the triples into three categories: good, small, and bad, and then
give a one line bound for the contribution of small triples. We will then
bound the contribution of good triples and bad triples in Section 4.5 and 4.6,
respectively.

###  4.1 The Weight Function for Lemma 2.1

We will use Lemma 2.1 to show Theorem 3.1. First, let us construct the weight
function $W$ in the hyperplane separation lemma.

For any $M\in\mathcal{M}_{\mathrm{all}}(G)$ and
$L\in\mathcal{L}_{\mathrm{all}}(G)$, we call $(M,L)$ an $l$-violation pair if
$|M\cap E_{L}|=l$, i.e., it is a slack-$(l-1)$ entry. Our “hard” weight
function $W$ is defined as follows:

$W_{M,L}:=\left\\{\begin{matrix}-\infty&|M\cap E_{L}|=1\\\ \mu_{3}(M,L)&|M\cap
E_{L}|=3\\\ -\frac{1}{4k+2}\cdot\mu_{4k+3}(M,L)&|M\cap E_{L}|=4k+3\\\
0&\text{otherwise},\end{matrix}\right.$

where $\mu_{3}$ and $\mu_{4k+3}$ are some distributions on $3$-violation and
$(4k+3)$-violation pairs respectively, which will be specified later.

It is easy to verify that

$\langle
W,S(P_{G},C_{G})\rangle=0\cdot{-\infty}+(3-1)-\frac{(4k+3)-1}{4k+2}=1.$ (4.2)

We say that a two-party function
$\mathcal{R}:\mathcal{M}_{\mathrm{all}}(G)\times\mathcal{L}_{\mathrm{all}}(G)\rightarrow\\{0,1\\}$
is a rectangle if $\mathcal{R}=uv^{\top}$ for some boolean vectors
$u\in\\{0,1\\}^{\mathcal{M}_{\mathrm{all}}(G)}$ and
$v\in\\{0,1\\}^{\mathcal{L}_{\mathrm{all}}(G)}$. Given a distribution $\mu$
over $\mathcal{M}_{\mathrm{all}}(G)\times\mathcal{L}_{\mathrm{all}}(G)$, we
define $\mu(\mathcal{R}):=\langle\mu,\mathcal{R}\rangle$ as the probability
that a pair $(M,L)$ sampled from $\mu$ belongs to $\mathcal{R}$. We show that
the inner product of $W$ and any rectangle is tiny.

###### Lemma 4.1

Let
$\mathcal{R}:\mathcal{M}_{\mathrm{all}}(G)\times\mathcal{L}_{\mathrm{all}}(G)\rightarrow\\{0,1\\}$
be a rectangle. Then $\langle W,\mathcal{R}\rangle\leq 2^{-\gamma m+1}$ for
some constant $\gamma:=\gamma(k)>0$.

Equation 4.2 and Lemma 4.1 directly imply Theorem 3.1:

$\mathrm{rk}^{+}(S(P_{G},C_{G}))\geq\frac{\overbrace{\langle
W,S(P_{G},C_{G})\rangle}^{=1}}{\underbrace{\|S(P_{G},C_{G})\|_{\infty}}_{\leq
n-1}\cdot\underbrace{\max\\{\langle W,\mathcal{R}\rangle:\mathcal{R}\text{ is
a rectangle}\\}}_{\leq 2^{-\gamma m+1}}}=2^{\Omega(n)}.$

To show Lemma 4.1, we only need to show:

###### Lemma 4.2

Let
$\mathcal{R}:\mathcal{M}_{\mathrm{all}}(G)\times\mathcal{L}_{\mathrm{all}}(G)\rightarrow\\{0,1\\}$
be a rectangle. If for all $(M,L)\in\mathcal{R}$, $|M\cap E_{L}|>1$, then
$\mu_{3}(\mathcal{R})\leq\frac{40}{k^{2}}\cdot\mu_{4k+3}(\mathcal{R})+2^{-\gamma
m}$ when $m$ is sufficiently large.

  * Proof.

[Proof of Lemma 4.1 assuming Lemma 4.2] If $\mathcal{R}$ contains a
$1$-violation entry, by definition, $\langle W,\mathcal{R}\rangle=-\infty$.
Otherwise, when $k\geq 400$, we have

$\langle
W,\mathcal{R}\rangle=2\mu_{3}(\mathcal{R})-\frac{1}{4k+2}\mu_{4k+3}(\mathcal{R})\leq\left(\frac{80}{k^{2}}-\frac{1}{4k+2}\right)\mu_{4k+3}(\mathcal{R})+2^{-\gamma
m+1}\leq 2^{-\gamma m+1}.$

Intuitively, the above lemma is saying that any “large” rectangle disjoint
from $1$-violation entries must over-cover $(4k+3)$-violation entries, where
by “large” rectangles we mean rectangles that cover at least a $2^{-\gamma
m+2}$-fraction of $3$-violation entries according to $\mu_{3}$.

In the rest of this section, we prove Lemma 4.2.

###  4.2 Partitions

$A$$B$$C$ Figure 2: Visualization of a partition $T=(A,C,B)$. Each of the $m$
blocks in $A$ and $B$ have $4k$ pairs of vertices while $C$ has $4k+3$ pairs.

The vertices of the graph are labeled $u_{1},\ldots,u_{n}\in U$ and
$v_{1},\ldots,v_{n}\in V$. For each $i\in[n]$, $(u_{i},v_{i})$ are naturally
made into pairs. Note that a vertex might not be matched with the vertex in
the same pair when talking about $\mu_{3}$ and $\mu_{4k+3}$ later.

Similar to Rothvoss’s partition, our partition consists of
$A=\\{\mathbf{A}_{1},\ldots,\mathbf{A}_{m}\\}$, which will be used to generate
almost uniform labelings, and $B=\\{\mathbf{B}_{1},\ldots,\mathbf{B}_{m}\\}$,
which will be used to generate almost uniform matchings. We also have a set
$C$ (in Rothvoss’s proof $C$ and $D$ are used), the only part that causes
violations.

Unlike Rothvoss’s partition, since our graph is colored, each block
$\mathbf{A}_{i}$ or $\mathbf{B}_{i}$ cannot contain all the labelings or all
the matchings. Thus, in each block, vertices are not “identical”. In fact,
vertices (or more precisely, pairs) are “ordered” in each $\mathbf{A}_{i}$ and
$\mathbf{B}_{i}$ in our partition ($C$ is not ordered at this stage).

Formally, a partition $T$ is defined as
$T:=(A=\\{\mathbf{A}_{1},\ldots,\mathbf{A}_{m}\\},C,B=\\{\mathbf{B}_{1},\ldots,\mathbf{B}_{m}\\})$
where

  * •

$A$ contains $m$ disjoint blocks $\mathbf{A}_{1},\ldots,\mathbf{A}_{m}$ where
each $\mathbf{A}_{i}$ is a sequence of $4k$ pairs of vertices.

  * •

$B$ contains $m$ disjoint blocks $\mathbf{B}_{1},\ldots,\mathbf{B}_{m}$ where
each $\mathbf{B}_{i}$ is a sequence of $4k$ pairs of vertices.

  * •

$C$ is an unordered set of the remaining $4k+3$ pairs of vertices.

Given an ordered set of pairs of vertices $\mathbf{A}$ (resp. an unordered set
$A$), let $G_{\mathbf{A}}$ (resp. $G_{A}$), be a subgraph induced by all the
vertices in $\mathbf{A}$ (resp. $A$). Given an
$M\in\mathcal{M}_{\mathrm{all}}(G)$ and $L\in\mathcal{L}_{\mathrm{all}}(G)$,
let $M_{\mathbf{A}}$ (resp. $M_{A}$) be the matching resulting from
restricting $M$ on $G_{\mathbf{A}}$ (resp. $G_{A}$). Let $L_{\mathbf{A}}$
(resp. $L_{A}$) be the labeling resulting from restricting $L$ on
$G_{\mathbf{A}}$ (resp. $G_{A}$). For $M$ a matching that is perfect on
$G_{A}$, we say $M_{A}$ is consistent with $L_{A}$ if all the edges in $M_{A}$
are correct w.r.t. $L_{A}$.

Now let us see what is inside $\mathbf{A}_{i}$ and $\mathbf{B}_{j}$. Given a
sequence of $4k$ pairs of vertices $\mathbf{D}=((u_{1},v_{1}),\dots$,
$(u_{4k},v_{4k}))$ where $(u_{j},v_{j})$ is the $j$-th pair in $\mathbf{D}$,
let $M_{A}(\mathbf{D})$ be a perfect matching of $G_{\mathbf{D}}$ defined as

$M_{A}(\mathbf{D})=\\{e=(u_{j},v_{2k+j},\mbox{red}):1\leq j\leq
2k\\}\cup\\{e=(u_{2k+j},v_{j},\mbox{red}):1\leq j\leq 2k\\}.$

In each block $\mathbf{A}_{i}$, the matching is fixed to be
$M_{A}(\mathbf{A}_{i})$. And $L_{\mathbf{A}_{i}}$, the labeling restricted on
$\mathbf{A}_{i}$, can be any labeling consistent with $M_{A}(\mathbf{A}_{i})$.

Similarly, given a sequence of $4k$ pairs of vertices
$\mathbf{D}=((u_{1},v_{1}),\ldots,(u_{4k},v_{4k}))$, let $L_{B}(\mathbf{D})$
be a labeling of $G_{\mathbf{D}}$ defined as follows.

  * •

For every $j\in[1,k]\cup[2k+1,3k]$,
$L_{B}(\mathbf{D})(u_{j})=L_{B}(\mathbf{D})(v_{j})=1$.

  * •

For every $j\in[k+1,2k]\cup[3k+1,4k]$,
$L_{B}(\mathbf{D})(u_{j})=L_{B}(\mathbf{D})(v_{j})=0$.

Note that $M_{A}(\mathbf{D})$ is consistent with $L_{B}(\mathbf{D})$.

In each block $\mathbf{B}_{i}$ the labeling is fixed to be
$L_{B}(\mathbf{B}_{i})$. And $M_{\mathbf{B}_{i}}$, the matching restricted on
$\mathbf{B}_{i}$, can be any perfect matching consistent with
$L_{B}(\mathbf{B}_{i})$.

$M_{A}(\mathbf{D})$

$1$$1$$1$$1$$1$$1$$1$$1$$0$$0$$0$$0$$0$$0$$0$$0$$L_{B}(\mathbf{D})$

Figure 3: The matching $M_{A}(\mathbf{D})$ and the labeling
$L_{B}(\mathbf{D})$. $\mathcal{M}_{\mathrm{all}}(T)$ are all matchings that
are exactly $M_{A}(\mathbf{D})$ on all A-blocks and consistent with
$L_{B}(\mathbf{D})$ on all B-blocks. $\mathcal{L}_{\mathrm{all}}(T)$ are
labelings that are exactly $L_{B}(\mathbf{D})$ on B-blocks and consistent with
$M_{A}(\mathbf{D})$ on A-blocks.

Define

$\displaystyle\mathcal{M}_{\mathrm{all}}(T):=$
$\displaystyle\\{M:M_{\mathbf{A}_{i}}=M_{A}(\mathbf{A}_{i}),\,M_{\mathbf{B}_{i}}\text{
is consistent with }L_{B}(\mathbf{B}_{i})\,\forall 1\leq i\leq m,\,M_{C}\text{
has odd number of}$ $\displaystyle\text{ red edges}\\}$

and

$\mathcal{L}_{\mathrm{all}}(T):=\\{L:L_{\mathbf{B}_{i}}=L_{B}(\mathbf{B}_{i}),\,L_{\mathbf{A}_{i}}\text{
is consistent with }M_{A}(\mathbf{A}_{i})\,\forall 1\leq i\leq
m,\,|L_{C}^{-1}(1)|\text{ is odd}\\}.$

For any $M\in\mathcal{M}_{\mathrm{all}}(T)$, by a parity argument, both
$M_{\mathbf{A}_{i}}$ and $M_{\mathbf{B}_{i}}$ contain an even number of red
edges, which implies $M\in\mathcal{M}_{\mathrm{all}}$. Similarly, for any
$L\in\mathcal{L}_{\mathrm{all}}(T)$, both $|L_{\mathbf{A}_{i}}^{-1}(1)|$ and
$|L_{\mathbf{B}_{i}}^{-1}(1)|$ are even, which implies $|L^{-1}(1)|$ is odd.
Thus
$\mathcal{M}_{\mathrm{all}}(T)\subseteq\mathcal{M}_{\mathrm{all}},\mathcal{L}_{\mathrm{all}}(T)\subseteq\mathcal{L}_{\mathrm{all}}$.
Note that for any fixed partition $T$, $M\in\mathcal{M}_{\mathrm{all}}(T)$,
and $L\in\mathcal{L}_{\mathrm{all}}(T)$, violations caused by $(M,L)$ only
occur in $C$.

###  4.3 Generating the distributions

From now on, we fix $\mathcal{R}=\mathcal{M}\times\mathcal{L}$ to be a
rectangle disjoint from 1-violation entries.

To quantitatively characterize $\mu_{3}(\mathcal{R})$ and
$\mu_{4k+3}(\mathcal{R})$, we need the following notation. Let
$T=(A=\\{\mathbf{A}_{1},\ldots,\mathbf{A}_{m}\\},C,B=\\{\mathbf{B}_{1},\ldots,\mathbf{B}_{m}\\})$
be a partition, $M^{\prime}$ be a perfect matching of $C$, define

$p_{\mathcal{M},T}(M^{\prime}):=\Pr_{M\sim\mathcal{M}_{\mathrm{all}}(T,M^{\prime})}[M\in\mathcal{M}]$

where
$\mathcal{M}_{\mathrm{all}}(T,M^{\prime}):=\\{M\in\mathcal{M}_{\mathrm{all}}(T):M_{C}=M^{\prime}\\}$,
as the probability that a uniform matching $M$ among all matchings w.r.t. $T$
whose restriction on $C$ is $M^{\prime}$ lies in $\mathcal{M}$. Similarly, for
any labeling $L^{\prime}$ of $C$, define

$p_{\mathcal{L},T}(L^{\prime}):=\Pr_{L\sim\mathcal{L}_{\mathrm{all}}(T,L^{\prime})}[L\in\mathcal{L}]$

where
$\mathcal{L}_{\mathrm{all}}(T,L^{\prime}):=\\{L\in\mathcal{L}_{\mathrm{all}}(T):L_{C}=L^{\prime}\\}$,
as the probability that a uniform labeling $L$ among all labelings w.r.t. $T$
whose restriction on $C$ is $L^{\prime}$ lies in $\mathcal{L}$.

To generate $\mu_{3}$, we first sample a uniform partition $T$. Then we
uniformly select three pairs of vertices from $C$. We call this unordered set
$H$. Afterwards, we order the remaining $4k$ pairs of vertices uniformly at
random to get $\mathbf{D}=\mathbf{D}_{1}\sqcup\mathbf{D}_{2}$, where
$\mathbf{D}_{1}$ is an ordered set of the first $2k$ pairs of vertices in
$\mathbf{D}$ and $\mathbf{D}_{2}$ is an ordered set of the last $2k$ pairs.
Since $T,H,\mathbf{D}$ will appear very frequently in the rest of the section,
we use $\mathcal{T}$ to denote the set of all the potential triples
$(T,H,\mathbf{D})$ generated at this stage.

Let $M_{3}(H)$ be a perfect matching of $H$ where vertices in each pair are
connected by a red edge and $L_{3}(H)$ be a labeling of $H$ where all the
vertices of $H$ in $U$ are labeled with $1$ and those in $V$ are labeled with
$0$. Note that all the edges in $M_{3}(H)$ violate $L_{3}(H)$.

Then we can generate $(M,L)$ according to a product distribution. Sample
$M\sim\mathcal{M}_{\mathrm{all}}(T,M_{3}(H\cup\mathbf{D}))$, and
$L\sim\mathcal{M}_{\mathrm{all}}(T,L_{3}(H\cup\mathbf{D}))$ uniformly and
independently, where $M_{3}(H\cup\mathbf{D}):=M_{3}(H)\cup M_{A}(\mathbf{D})$
and $L_{3}(H\cup\mathbf{D}):=L_{3}(H)\cup L_{B}(\mathbf{D})$. Any potential
outcome $(M,L)$ is a $3$-violation pair since the violations only occur in
$H$.

Quantitatively, $\mu_{3}(\mathcal{R})$ can be expressed as

$\mu_{3}(\mathcal{R})=\mathbb{E}_{T}[\mathbb{E}_{H,\mathbf{D}}[p_{\mathcal{M},T}(M_{3}(H\cup\mathbf{D}))\cdot
p_{\mathcal{L},T}(L_{3}(H\cup\mathbf{D}))]].$ (4.3)

On the other hand, to generate $\mu_{4k+3}$, we first sample a uniform
partition $T$. Then we uniformly order the pairs of vertices in $C$. Let
$\mathbf{C}=\mathbf{F}\sqcup\mathbf{D}_{2}$ denote the obtained ordered set,
where $\mathbf{F}$ is the ordered set of the first $2k+3$ pairs of vertices
and $\mathbf{D}_{2}$ is the ordered set of the last $2k$ pairs.

Similar to what we did for $\mu_{3}$, we can then sample $(M,L)$ according to
a product distribution. Let $\mathbf{C}=((u_{-2},v_{-2}),\ldots$,
$(u_{4k},v_{4k}))$, where $(u_{j},v_{j})$ is the $(j+3)$-th pair of
$\mathbf{C}$. Let $M_{4k+3}(\mathbf{C})$ be a perfect matching of $\mathbf{C}$
defined as

$M_{4k+3}(\mathbf{C}):=\\{e=(u_{j},v_{j},\mathrm{red}):-2\leq j\leq 4k\\}.$

We also let $L_{4k+3}(\mathbf{C})$ be a labeling of $\mathbf{C}$, where

  * •

for every $-2\leq j\leq 2k$, $L_{4k+3}(\mathbf{C})(u_{j})=1$,
$L_{4k+3}(\mathbf{C})(v_{j})=0$;

  * •

for every $2k+1\leq j\leq 4k$, $L_{4k+3}(\mathbf{C})(u_{2k+j})=0$,
$L_{4k+3}(\mathbf{C})(v_{2k+j})=1$.

$M_{4k+3}(\mathbf{C})$$H$$\sigma_{\mathrm{pos}(H,\mathbf{F})}(\mathbf{F}\setminus
H)=\mathbf{D}_{1}$$\mathbf{D}_{2}$$\mathbf{D}$

$1$$1$$0$$0$$0$$0$$1$$1$$1$$1$$0$$0$$0$$0$$1$$1$$1$$0$$1$$0$$1$$0$$L_{4k+3}(\mathbf{C})$

Figure 4: The matching $M_{4k+3}(\mathbf{C})$ and the labeling
$L_{4k+3}(\mathbf{C})$. We also show the breakdown of
$\mathbf{C}=\mathbf{F}\cup\mathbf{D}_{2}$ in the triple $(T,H,\mathbf{D})$.

Then we sample $M\sim\mathcal{M}_{\mathrm{all}}(T,M_{4k+3}(\mathbf{C}))$ and
$L\sim\mathcal{L}_{\mathrm{all}}(T,L_{4k+3}(\mathbf{C}))$ uniformly and
independently. Any potential outcome $(M,L)$ is a $(4k+3)$-violation pair
since all the edges in $M_{\mathbf{C}}$ violate the labeling and all the
matching edges in $A$ and $B$ are consistent with the labeling.

$\mu_{4k+3}(\mathcal{R})$ can also be quantitatively expressed as

$\mu_{4k+3}(\mathcal{R})=\mathbb{E}_{T}[\mathbb{E}_{\mathbf{C}=\mathbf{F}\sqcup\mathbf{D}_{2}}[p_{\mathcal{M},T}(M_{4k+3}(\mathbf{C}))\cdot
p_{\mathcal{L},T}(L_{4k+3}(\mathbf{C}))]].$

###  4.4 Classification of Triples

In this section, we classify triples $(T,H,\mathbf{D})\in\mathcal{T}$ into
three categories: good, bad, or small w.r.t. the rectangle
$\mathcal{R}=\mathcal{M}\times\mathcal{L}$. From now on, we fix
$0<\epsilon<\frac{1}{3}$ to be a constant.

Given a triple $(T,H,\mathbf{D})\in\mathcal{T}$, recall that
$T=(A=\\{\mathbf{A}_{1},\ldots,\mathbf{A}_{m}\\},C,B=\\{\mathbf{B}_{1},\ldots,\mathbf{B}_{m}\\})$
is a partition, $\mathbf{D}$ is a sequence of $4k$ pairs of vertices in $C$,
and $H$ is the set of the remaining $3$ pairs in $C$. We say
$(T,H,\mathbf{D})$ is $\mathcal{L}$-good if the distribution of
$L_{\mathbf{D}}$ obtained by sampling a uniform $L\in\mathcal{L}$ that
satisfies $L_{H}=L_{3}(H)$ is close to a uniform distribution over all
labelings consistent with $M_{A}(\mathbf{D})$. Below is the formal definition.

######  Definition 4.1 ($\mathcal{L}$-good)

A triple $(T,H,\mathbf{D})\in\mathcal{T}$ is said to be $\mathcal{L}$-good if
for any labeling of $\mathbf{D}$ consistent with $M_{A}(\mathbf{D})$, denoted
$L^{\prime}$,

$0<\frac{1}{1+\epsilon}p_{\mathcal{L},T}(L_{3}(H)\cup L^{\prime})\leq
p_{\mathcal{L},T}(L_{3}(H\cup\mathbf{D}))\leq(1+\epsilon)p_{\mathcal{L},T}(L_{3}(H)\cup
L^{\prime}).$

Likewise, we say a triple $(T,H,\mathbf{D})$ is $\mathcal{M}$-good if the
distribution of $M_{\mathbf{D}}$ obtained by sampling a uniform
$M\in\mathcal{M}$ that satisfies $M_{H}=M_{3}(H)$ is close to a uniform
distribution over all matchings consistent with $L_{B}(\mathbf{D})$.

######  Definition 4.2 ($\mathcal{M}$-good)

A triple $(T,H,\mathbf{D})\in\mathcal{T}$ is said to be $\mathcal{M}$-good if
for any perfect matching of $\mathbf{D}$ consistent with $L_{B}(\mathbf{D})$,
denoted $M^{\prime}$,

$0<\frac{1}{1+\epsilon}p_{\mathcal{M},T}(M_{3}(H)\cup M^{\prime})\leq
p_{\mathcal{M},T}(M_{3}(H\cup\mathbf{D}))\leq(1+\epsilon)p_{\mathcal{M},T}(M_{3}(H)\cup
M^{\prime}).$

We say $(T,H,\mathbf{D})$ is good if it is both $\mathcal{M}$-good and
$\mathcal{L}$-good.

If a triple $(T,H,\mathbf{D})$ is not good, it can be either bad or small. We
say a triple is small if after fixing $T$, $H$, and $\mathbf{D}$, the
intersection of $\mathcal{R}$ and the product distribution is exponentially
small. A triple is bad if it is neither good nor small. Below is the formal
definition.

###### Definition 4.3

A triple $(T,H,\mathbf{D})\in\mathcal{T}$ is small if either
$p_{\mathcal{M},T}(M_{3}(H\cup\mathbf{D}))\leq 2^{-\delta m}$ or
$p_{\mathcal{L},T}(L_{3}(H\cup\mathbf{D}))\leq 2^{-\delta m}$ for some
constant $\delta:=\delta(k)>0$, which will be determined later. If a triple is
neither good or small, then it is bad.

Let $\mathrm{GOOD}(T,H,\mathbf{D})$, $\mathrm{SMALL}(T,H,\mathbf{D})$, and
$\mathrm{BAD}(T,H,\mathbf{D})$ be the indicator functions of whether
$(T,H,\mathbf{D})$ is good, small, or bad, respectively. We will get the
following bounds for each type of triple of the right-hand side of (4.3):

$\displaystyle\mathbb{E}_{T}[\mathbb{E}_{H,\mathbf{D}}[\mathrm{GOOD}(T,H,\mathbf{D})\cdot
p_{\mathcal{M},T}(M_{3}(H\cup\mathbf{D}))\cdot
p_{\mathcal{L},T}(L_{3}(H\cup\mathbf{D}))]]\leq\frac{20}{k^{2}}\mu_{4k+3}(\mathcal{R}),$
(4.4)
$\displaystyle\mathbb{E}_{T}[\mathbb{E}_{H,\mathbf{D}}[\mathrm{SMALL}(T,H,\mathbf{D})\cdot
p_{\mathcal{M},T}(M_{3}(H\cup\mathbf{D}))\cdot
p_{\mathcal{L},T}(L_{3}(H\cup\mathbf{D}))]]\leq 2^{-\delta m},$ (4.5)
$\displaystyle\mathbb{E}_{T}[\mathbb{E}_{H,\mathbf{D}}[\mathrm{BAD}(T,H,\mathbf{D})\cdot
p_{\mathcal{M},T}(M_{3}(H\cup\mathbf{D}))\cdot
p_{\mathcal{L},T}(L_{3}(H\cup\mathbf{D}))]]\leq\epsilon\cdot\mu_{3}(\mathcal{R})+2^{-\eta
m},$ (4.6)

where $\eta:=\eta(k)>0$ is some constant which will be determined later.
Summing up (4.4),(4.5),and (4.6), we obtain

$\mu_{3}(R)\leq\frac{20}{k^{2}}\mu_{4k+3}(\mathcal{R})+2^{-\delta
m}+\epsilon\cdot\mu_{3}(\mathcal{R})+2^{-\eta m}.$

By choosing $\gamma=\min\\{\delta,\eta\\}/2$, we directly obtain Lemma 4.2.

In fact, (4.5) can be proved in one line. For any triple $(T,H,\mathbf{D})$,
the product in the expectation is upper bounded by $2^{-\delta m}$. Note that
the expectation is always no larger than the maximum.

In the rest of this section we will prove (4.4) and (4.6).

###  4.5 Contributions of Good Triples

In this section, we prove (4.4). That is,

$\mathbb{E}_{T}[\mathbb{E}_{H,\mathbf{D}}[\mathrm{GOOD}(T,H,\mathbf{D})\cdot
p_{\mathcal{M},T}(M_{3}(H\cup\mathbf{D}))\cdot
p_{\mathcal{L},T}(L_{3}(H\cup\mathbf{D}))]]\leq\frac{20}{k^{2}}\mu_{4k+3}(\mathcal{R})\,.$

In the above expectation, we first select uniformly at random a partition
$T=(A=\\{\mathbf{A}_{1},\ldots,\mathbf{A}_{m}\\},C,B=\\{\mathbf{B}_{1},\ldots,\mathbf{B}_{m}\\})$.
Then $H$ is selected to be three uniformly at random pairs of vertices from
$C$, and finally we order the remaining $4k$ vertices uniformly at random to
get $\mathbf{D}$.

We describe an alternative but equivalent viewpoint of selecting
$T,H,\mathbf{D}$. While this alternative viewpoint is more cumbersome, it will
allow us to relate the above expectation to $\mu_{4k+3}$. In this description
we will use a family
$\\{\sigma_{\mathrm{pos}(H,\mathbf{F})}\\}_{\mathrm{pos}(H,\mathbf{F})\in\binom{[2k+3]}{3}}$
of permutations. We later show, using the probabilistic method, that there is
a family with nice properties that allows us to prove (4.4) (see Lemma 4.4).
The alternative way of selecting $T,H,\mathbf{D}$ proceeds as follows. As
before, we first uniformly sample the partition $T$. But now we first
uniformly at random permute all the $4k+3$ vertices in $C$ to get
$\mathbf{C}=\mathbf{F}\sqcup\mathbf{D}_{2}$, where we let $\mathbf{F}$ denote
the ordered set of the first $2k+3$ pairs of vertices and $\mathbf{D}_{2}$
denote the ordered set of the remaining $2k$ pairs. Then we uniformly sample 3
pairs from $\mathbf{F}$. Call this unordered set $H$. We let
$\mathrm{pos}(H,\mathbf{F})\in\binom{[2k+3]}{3}$ denote the set of three
indices representing the positions of $H$ in $\mathbf{F}$. Then we apply
permutation $\sigma_{\mathrm{pos}(H,\mathbf{F})}$ to $\mathbf{F}\setminus H$
to get $\mathbf{D}_{1}=\sigma_{\mathrm{pos}(H,\mathbf{F})}(\mathbf{F}\setminus
H)$, where $\mathbf{F}\setminus H$ is an ordered set obtained by removing $H$
from $\mathbf{F}$ without changing the order of the other pairs. Finally, we
concatenate $\mathbf{D}_{2}$ to the end of $\mathbf{D}_{1}$ and get
$\mathbf{D}=\mathbf{D}_{1}\sqcup\mathbf{D}_{2}$. We remark that any three
pairs of $\mathbf{F}$ is a uniformly random sample of three pairs of $C$ due
to the random permutation of $C$. So $H$ is three uniformly random pairs of
$C$. Similarly, we have that $\mathbf{D}$ is a uniformly random permutation of
the remaining $4k$ pairs in $C$ no matter what
$\sigma_{\mathrm{pos}(H,\mathbf{F})}$ is because the pairs in
$\mathbf{F}\setminus H\cup\mathbf{D}_{2}$ are a random permutation of the $4k$
pairs in $C\setminus H$ (independent of
$\sigma_{\mathrm{pos}(H,\mathbf{F})}$). It follows that this alternative
viewpoint is equivalent and so we can express the left-hand side of (4.4) by

$\displaystyle\mathbb{E}_{T}[\mathbb{E}_{H,\mathbf{D}}[\mathrm{GOOD}(T,H,\mathbf{D})\cdot
p_{\mathcal{M},T}(M_{3}(H\cup\mathbf{D}))\cdot
p_{\mathcal{L},T}(L_{3}(H\cup\mathbf{D}))]]$ $\displaystyle=$
$\displaystyle\mathbb{E}_{T}[\mathbb{E}_{\mathbf{C}=\mathbf{F}\sqcup\mathbf{D}_{2}}[\mathbb{E}_{H\sim\binom{\mathbf{F}}{3},\mathbf{D}_{1}=\sigma_{\mathrm{pos}(H,\mathbf{F})}(\mathbf{F}\setminus
H),\mathbf{D}=\mathbf{D}_{1}\sqcup\mathbf{D}_{2}}[\mathrm{GOOD}(T,H,\mathbf{D})\cdot
p_{\mathcal{M},T}(M_{3}(H\cup\mathbf{D}))\cdot
p_{\mathcal{L},T}(L_{3}(H\cup\mathbf{D}))]]].$

We further have that this expectation is upper bounded by

$\displaystyle
2\cdot\mathbb{E}_{T}[\mathbb{E}_{\mathbf{C}=\mathbf{F}\sqcup\mathbf{D}_{2}}[p_{\mathcal{M},T}(M_{4k+3}(\mathbf{C}))\cdot
p_{\mathcal{L},T}(L_{4k+3}(\mathbf{C}))\cdot\mathbb{E}_{H\sim\binom{\mathbf{F}}{3},\mathbf{D}_{1}=\sigma_{\mathrm{pos}(H,\mathbf{F})}(\mathbf{F}\setminus
H),\mathbf{D}=\mathbf{D}_{1}\sqcup\mathbf{D}_{2}}[\mathrm{GOOD}(T,H,\mathbf{D})]]].$

This follows from the following observation: when $(T,H,\mathbf{D})$ is good,
$p_{\mathcal{M},T}(M_{3}(H\cup\mathbf{D}))\leq(1+\epsilon)p_{\mathcal{M},T}(M_{4k+3}(\mathbf{C}))$
since $(M_{4k+3}(\mathbf{C}))_{H}=M_{3}(H)$ and
$(M_{4k+3}(\mathbf{C}))_{\mathbf{D}}$ is consistent with $L_{B}(\mathbf{D})$.
Similarly,
$p_{\mathcal{L},T}(L_{3}(H\cup\mathbf{D}))\leq(1+\epsilon)p_{\mathcal{L},T}(L_{4k+3}(\mathbf{C}))$
since $(L_{4k+3}(\mathbf{C}))_{H}=L_{3}(H)$ and
$(L_{4k+3}(\mathbf{C}))_{\mathbf{D}}$ is consistent with $M_{A}(\mathbf{D})$.

Now recall that
$\mu_{4k+3}(\mathcal{R})=\mathbb{E}_{T}[\mathbb{E}_{\mathbf{C}=\mathbf{F}\sqcup\mathbf{D}_{2}}[p_{\mathcal{M},T}(M_{4k+3}(\mathbf{C}))\cdot
p_{\mathcal{L},T}(L_{4k+3}(\mathbf{C}))]]$ and so by combining the above
inequalities,

$\displaystyle\mathbb{E}_{T}[\mathbb{E}_{H,\mathbf{D}}[\mathrm{GOOD}(T,H,\mathbf{D})\cdot
p_{\mathcal{M},T}(M_{3}(H\cup\mathbf{D}))\cdot
p_{\mathcal{L},T}(L_{3}(H\cup\mathbf{D}))]]$ $\displaystyle\leq$
$\displaystyle
2\mu_{4k+3}(\mathcal{R})\cdot\max_{T,\mathbf{C}=\mathbf{F}\sqcup\mathbf{D}_{2}}\\{\mathbb{E}_{H\sim\binom{\mathbf{F}}{3},\mathbf{D}_{1}=\sigma_{\mathrm{pos}(H,\mathbf{F})}(\mathbf{F}\setminus
H),\mathbf{D}=\mathbf{D}_{1}\sqcup\mathbf{D}_{2}}[\mathrm{GOOD}(T,H,\mathbf{D})]\\}.$

The remainder of this section will be devoted to showing that for any
partition $T$ and any ordering $\mathbf{C}=\mathbf{F}\sqcup\mathbf{D}_{2}$,

$\mathbb{E}_{H\sim\binom{\mathbf{F}}{3},\mathbf{D}_{1}=\sigma_{\mathrm{pos}(H,\mathbf{F})}(\mathbf{F}\setminus
H),\mathbf{D}=\mathbf{D}_{1}\sqcup\mathbf{D}_{2}}[\mathrm{GOOD}(T,H,\mathbf{D})]\leq\frac{10}{k^{2}}.$
(4.7)

Then (4.4) directly follows.

Our main technical ingredient is the following. Let $H$ and $H^{\prime}$ be
two sets intersecting on at most one pair of vertices. Then under a technical
assumption, at least one of $(T,H,\mathbf{D})$ and
$(T,H^{\prime},\mathbf{D}^{\prime})$ is not good. We remark that this
technical assumption is one of the key differences between our proof and that
of Rothvoss’s proof for general matchings. Indeed, the analogous statement in
that paper always guarantees that at least one of $(T,H,\mathbf{D})$ and
$(T,H^{\prime},\mathbf{D}^{\prime})$ is not good. Moreover, this is also the
reason why we use the family of permutations
$\\{\sigma_{\mathrm{pos}(H,\mathbf{F})}\\}_{\mathrm{pos}(H,\mathbf{F})\in\binom{[2k+3]}{3}}$
with certain properties.

###### Lemma 4.3

Let $(T,H,\mathbf{D}=\mathbf{D}_{1}\sqcup\mathbf{D}_{2})$ and
$(T^{\prime},H^{\prime},\mathbf{D}^{\prime}=\mathbf{D}^{\prime}_{1}\sqcup\mathbf{D}^{\prime}_{2})$
be two triples such that $T=T^{\prime}$,
$\mathbf{D}_{2}=\mathbf{D}^{\prime}_{2}$, and $|H\cap H^{\prime}|\leq 1$. If
$(u_{1},v_{1})$ and $(u_{2},v_{2})$ are two pairs belonging to
$H^{\prime}\setminus H$ and $L_{B}(\mathbf{D})(v_{1})\neq
L_{B}(\mathbf{D})(v_{2})$, then $(T,H,\mathbf{D})$ and
$(T^{\prime},H^{\prime},\mathbf{D}^{\prime})$ cannot both be good.

  * Proof.

The goal of the proof is to find a 1-violation pair
$(M,L)\in\mathcal{R}=\mathcal{M}\times\mathcal{L}$ that contradicts the
assumption that $\mathcal{R}$ contains no such entry. This is conditioned on
$(T,H,\mathbf{D})$ and $(T,H^{\prime},\mathbf{D}^{\prime})$ both being good
and the existence of two pairs $(u_{1},v_{1}),(u_{2},v_{2})\in
H^{\prime}\setminus H$ such that $L_{B}(\mathbf{D})(v_{1})\neq
L_{B}(\mathbf{D})(v_{2})$. We now give five conditions that are necessary and
sufficient to construct an auxiliary pair $(M^{\prime},L^{\prime})$ that
proves the existence of the 1-violation pair.

Recall the definitions of $C$, $H$, and $D$ as shown in Figure 4, of $A$ and
$B$ as shown in Figure 2, and of $M_{A}(\mathbf{D}),L_{B}(\mathbf{D})$ as
shown in Figure 3. To prove the existence of a $1$-violation pair
$(M,L)\in\mathcal{R}$, it suffices to find a perfect matching $M^{\prime}$ and
a labeling $L^{\prime}$ of $C$ such that

  * (i)

$L^{\prime}_{H^{\prime}}=L_{3}(H^{\prime})$

  * (ii)

$L^{\prime}_{\mathbf{D}^{\prime}}$ is consistent with
$M_{A}(\mathbf{D}^{\prime})$

  * (iii)

$M^{\prime}_{H}=M_{3}(H)$

  * (iv)

$M^{\prime}_{\mathbf{D}}$ is consistent with $L_{B}(\mathbf{D})$

  * (v)

There is exactly one edge in $M^{\prime}$ that violates $L^{\prime}$.

Now we explain more explicitly how the goodness assumption together with these
five conditions imply we can find a 1-violation. If we can find such a pair
$(M^{\prime},L^{\prime})$, then by (i), (ii), and that
$(T,H^{\prime},\mathbf{D}^{\prime})$ is $\mathcal{L}$-good,
$p_{\mathcal{L},T}(L^{\prime})>0$, which implies that
$\mathcal{L}\cap\mathcal{L}_{\mathrm{all}}(T,L^{\prime})\neq\emptyset$. Let
$L$ be an arbitrary labeling in
$\mathcal{L}\cap\mathcal{L}_{\mathrm{all}}(T,L^{\prime})$. Similarly, by
(iii), (iv), and that $(T,H,\mathbf{D})$ is $\mathcal{M}$-good,
$p_{\mathcal{M},T}(M^{\prime})>0$. This implies
$\mathcal{M}\cap\mathcal{M}_{\mathrm{all}}(T,M^{\prime})\neq\emptyset$. Let
$M$ be an arbitrary matching in
$\mathcal{M}\cap\mathcal{M}_{\mathrm{all}}(T,M^{\prime})$. Since
$M\in\mathcal{M}_{\mathrm{all}}(T)$ and $L\in\mathcal{L}_{\mathrm{all}}(T)$
are sampled from the same partition $T$, $L$ is consistent with $M$ on $A$ and
$B$. Together with (v), we conclude that $(M,L)$ is a $1$-violation pair and
$(M,L)\in\mathcal{R}$ because $M\in\mathcal{M}$ and $L\in\mathcal{L}$.

Next, we exhibit a pair $(M^{\prime},L^{\prime})$ that satisfies (i)-(v). We
first give a simple construction of $L^{\prime}$:

$L^{\prime}(v)=\left\\{\begin{matrix}1&v\notin C\setminus(H^{\prime}\cap V)\\\
0&v\in H^{\prime}\cap V\end{matrix}\right..$ (4.8)

Let us verify that $L^{\prime}$ satisfies (i) and (ii). Recall that $L_{3}(H)$
assigns $1$s to vertices in $H^{\prime}\cap U$ and $0$s to vertices in
$H^{\prime}\cap V$. Hence $L^{\prime}_{H^{\prime}}=L_{3}(H^{\prime})$, i.e.
(i) holds. Moreover, since $L^{\prime}_{\mathbf{D}^{\prime}}$ is the
constant-1 function and $M_{A}(\mathbf{D}^{\prime})$ contains only red edges,
$L^{\prime}_{\mathbf{D}^{\prime}}$ is consistent with
$M_{A}(\mathbf{D}^{\prime})$, i.e. (ii) holds.

Next, we construct $M^{\prime}$ as follows:

$M^{\prime}=\\{(u,v,\text{red}),(u,v)\in
C\setminus\\{(u_{1},v_{1}),(u_{2},v_{2})\\}\\}\cup\\{(u_{1},v_{2},\text{blue}),(u_{2},v_{1},\text{blue})\\}.$

Now let us verify that $M^{\prime}$ satisfies (iii) and (iv). Recall that
$M_{3}(H)$ is the set of three red edges that connect pairs in $H$. Since
$H\subseteq C\setminus\\{(u_{1},v_{1}),(u_{2},v_{2})\\}$,
$M^{\prime}_{H}=M_{3}(H)$, i.e. (iii) holds. For (iv), note that for any
$(u,v)\in\mathbf{D}$, $L_{B}(\mathbf{D})(u)=L_{B}(\mathbf{D})(v)$, thus all
the red edges in $M^{\prime}_{\mathbf{D}}$ are consistent w.r.t.
$L_{B}(\mathbf{D})$. Moreover, by the assumption of the lemma
$L_{B}(\mathbf{D})(v_{1})\neq L_{B}(\mathbf{D})(v_{2})$, which implies
$L_{B}(\mathbf{D})(u_{1})\neq
L_{B}(\mathbf{D})(v_{2}),L_{B}(\mathbf{D})(u_{2})\neq
L_{B}(\mathbf{D})(v_{1})$ since
$L_{B}(\mathbf{D})(u_{1})=L_{B}(\mathbf{D})(v_{1})$ and
$L_{B}(\mathbf{D})(u_{2})=L_{B}(\mathbf{D})(v_{2})$. Thus the two blue edges
are also consistent. Hence (iv) holds.

Finally, let us verify that $M^{\prime}$ along with $L^{\prime}$ satisfies
(v). Since for any $(u,v)\in C\setminus H^{\prime}$,
$L^{\prime}(u)=L^{\prime}(v)=1$, the $4k$ red edges in $M^{\prime}$ that
connect pairs in $C\setminus H^{\prime}$ are consistent w.r.t. $L^{\prime}$.
Let $(u_{3},v_{3})$ denote the other pair in $H^{\prime}$ other than
$(u_{1},v_{1})$ and $(u_{2},v_{2})$. Note that
$L^{\prime}(u_{1})=L^{\prime}(u_{2})=L^{\prime}(u_{3})=1,L^{\prime}(v_{1})=L^{\prime}(v_{2})=L^{\prime}(v_{3})=0$.
Thus the two blue edges $(u_{1},v_{2}),(u_{2},v_{1})$ are consistent w.r.t.
$L^{\prime}$ while the red edge $(u_{3},v_{3})$ is the only violating edge.
Therefore, (v) holds.

In summary, we can find $(M^{\prime},L^{\prime})$ that satisfies (i)-(v),
which implies the existence of $1$-violation entry $(M,L)\in\mathcal{R}$,
leading to a contradiction.

$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0$$u_{1}$$u_{2}$$v_{1}$$v_{2}$$u_{3}$$v_{3}$$H$$H^{\prime}$

$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0$$u_{1}$$u_{2}$$v_{1}$$v_{2}$$u_{3}$$v_{3}$$H$$H^{\prime}$

Figure 5: The above two figures show how $M^{\prime}$ and $L^{\prime}$ are
constructed when $k=2$. The left one shows the case when $|H\cap
H^{\prime}|=1$ while the right one shows the case when $|H\cap H^{\prime}|=0$.
The red labeling is $L^{\prime}$ and the blue one is $L_{B}(\mathbf{D})$. The
squiggly line is the only violating edge in both figures.

Finally, we show that there exists a set of permutations
$\\{\sigma_{t}:t\in[2k+3]^{3}\\}$ such that (4.7) holds. The proof is by the
probabilistic method.

###### Lemma 4.4

There is a family $\\{\sigma_{t}:t\in\binom{[2k+3]}{3}\\}$ of bijections
$\sigma_{t}:[2k+3]\setminus t\rightarrow[2k]$ such that the following holds.
For any subset $S$ of $\binom{[2k+3]}{3}$ with $|S|\geq 10k$, there are
$t,t^{\prime}\in S$ and two elements $v_{1},v_{2}\in t^{\prime}\setminus t$
satisfying $1\leq\sigma_{t}(v_{1})\leq k<\sigma_{t}(v_{2})\leq 2k$.

Before proving this lemma, let us argue that it implies (4.7). Let
$\\{\sigma_{\mathrm{pos}(H,\mathbf{F})}:\mathrm{pos}(H,\mathbf{F})\in\binom{[2k+3]}{3}\\}$
be the family guaranteed by the lemma. Fix any partition $T$ and any ordering
$\mathbf{C}=\mathbf{F}\sqcup\mathbf{D}_{2}$. Suppose toward a contradiction
that

$\mathbb{E}_{H\sim\binom{\mathbf{F}}{3},\mathbf{D}_{1}=\sigma_{\mathrm{pos}(H,\mathbf{F})}(\mathbf{F}\setminus
H),\mathbf{D}=\mathbf{D}_{1}\sqcup\mathbf{D}_{2}}[\mathrm{GOOD}(T,H,\mathbf{D})]>\frac{10}{k^{2}}.$

As there are $\binom{2k+3}{3}\geq k^{3}$ many choices of $H$, this implies
that there are at most $10k$ choices of $H$ such that $(T,H,\mathbf{D})$ is
good. By the above lemma, two of these choices, say $H$ and $H^{\prime}$ with
corresponding triples $(T,H,\mathbf{D})$ and
$(T,H^{\prime},\mathbf{D}^{\prime})$, must be such that there exist two pairs
$(u_{1},v_{1}),(u_{2},v_{2})\in H^{\prime}\setminus H$ satisfying
$1\leq\sigma_{\mathrm{pos}(H,\mathbf{F})}(v_{1})\leq
k<\sigma_{\mathrm{pos}(H,\mathbf{F})}(v_{2})\leq 2k$. By the definition of
$L_{B}(\mathbf{D})$, this means that $L_{B}(\mathbf{D})(v_{1})\neq
L_{B}(\mathbf{D})(v_{2})$. Lemma 4.3 now gives the contradiction that not both
$(T,H,\mathbf{D})$ and $(T,H^{\prime},\mathbf{D}^{\prime})$ can be good.

It remains to prove that there is a family of “good” permutations.

  * Proof.

[Proof of Lemma 4.4] The proof is by the probabilistic method: we show that a
random family is likely to satisfy the statement.

Given two $t,t^{\prime}\in\binom{[2k+3]}{3}$, let $E(t,t^{\prime})$ denote the
event that either $|t\cap t^{\prime}|\geq 2$, or for any two elements $v_{1}$
and $v_{2}$ belonging to $t^{\prime}\setminus t$, either
$1\leq\sigma_{t}(v_{1}),\sigma_{t}(v_{2})\leq k$ or
$k+1\leq\sigma_{t}(v_{1}),\sigma_{t}(v_{2})\leq 2k$. Note that if
$E(t,t^{\prime})$ is false then there must be $v_{1},v_{2}\in
t^{\prime}\setminus t$ such that $1\leq\sigma_{t}(v_{1})\leq
k<\sigma_{t}(v_{2})\leq 2k$.

Now fix a subset $S$ of $\binom{[2k+3]}{3}$ such that $|S|=10k$. We let
$E(t,S)$ denote the event that $E(t,t^{\prime})$ happens for all
$t^{\prime}\in S$ and $E(S)$ denote the event that $E(t,S)$ happens for all
$t\in S$. We will prove that $\Pr[E(S)]\leq 2^{-\Omega(k^{4/3})}$. There are

$\binom{\binom{2k+3}{3}}{10k}=k^{O(k)}$

different subsets $S$ of cardinality $10k$. Thus by the union bound, the event
$E(S)$ is false for all subsets $S$ of cardinality $10k$ with probability
$1-o_{k}(1)$. This implies the lemma. Indeed, a random family is likely to
satisfy the statement of the lemma.

It remains to show that $E(S)$ happens with probability at most
$2^{-\Omega(k^{4/3})}$ for a subset $S$ of cardinality $10k$. Each bijection
$\sigma_{t}$ is chosen independently uniformly at random. Moreover, the only
randomness that impacts the event $E(t,S)$ is the choice of $\sigma_{t}$. It
follows that the events in $\\{E(t,S):t\in S\\}$ are mutually independent. So
to prove that $\Pr[E(S)]\leq 2^{-\Omega(k^{4/3})}$, it suffices to show that
$\Pr[E(t,S)]=2^{-\Omega(k^{1/3})}$ for $t\in S$.

There are at most $3k$ different triples $t^{\prime}$ such that $|t\cap
t^{\prime}|\geq 2$. Since $E(t,t^{\prime})$ is always true in this case, we
can remove such $t^{\prime}$ and obtain $S^{\prime}\subseteq S$ such that
$|S^{\prime}|\geq 7k$ and every $t^{\prime}\in S^{\prime}$ satisfies $|t\cap
t^{\prime}|\leq 1$. Name the elements of
$S^{\prime}=\\{t_{1},t_{2},\ldots,t_{\ell}\\}$ where $\ell=|S^{\prime}|\geq
7k$.

We say that $t_{i}$ is special if $t_{i}\setminus(t_{1}\cup\cdots\cup
t_{i-1})\neq\emptyset$. Let $s_{i}$ denote the number of special elements in
$t_{1},\ldots,t_{i}$. Then

$r_{i}:=|t_{1}\cup\cdots\cup t_{i}|\leq 3s_{i}.$

For a special $t_{i}$, consider an arbitrary element $x$ in
$t_{i}\setminus(t_{1}\cup\cdots\cup t_{i-1})$. If we condition on the events
$E(t,t_{1})$, $E(t,t_{2}),\ldots,E(t,t_{i-1})$ happening, the probability that
$1\leq\sigma_{t}(x)\leq k$ (or $k+1\leq\sigma_{t}(x)\leq 2k$) is at most
$\frac{k}{2k-r_{i}}\leq\frac{k}{2k-3s_{i}}$. Moreover, since a set of size $r$
can have at most $\binom{r}{3}$ different subsets of size $3$, we have
$7k\leq\ell\leq\binom{r_{i}}{3}\leq\binom{3s_{\ell}}{3}$, which implies that
$s_{\ell}=\Omega\left(k^{1/3}\right)$. Finally, we apply the chain rule and
obtain that

$\displaystyle\Pr[E(t,S)]$ $\displaystyle=\Pr[E(t,t_{1})\land\cdots\land
E(t,t_{\ell})]$
$\displaystyle=\prod_{i=1}^{\ell}\Pr[E(t,t_{i})|E(t,t_{1})\land\cdots\land
E(t,t_{i-1})]$ $\displaystyle\leq\prod_{1\leq i\leq\ell,i\text{
special}}\Pr[E(t,t_{i})|E(t,t_{1})\land\cdots\land E(t,t_{i-1})]$
$\displaystyle\leq\prod_{0\leq i\leq\min(s_{\ell},k/4)}\frac{k}{2k-3i}$
$\displaystyle=2^{-\Omega(k^{1/3})}.$

As aforementioned, this implies that $\Pr[E(S)]\leq 2^{-\Omega(k^{4/3})}$,
which in turn implies the lemma by taking the union bound over all $S$ with
$|S|=10k$.

###  4.6 Contributions of Bad Triples

Finally, let us bound the contribution of bad triples. We restate the desired
inequality here.

$\mathbb{E}_{T}[\mathbb{E}_{H,\mathbf{D}}[\mathrm{BAD}(T,H,\mathbf{D})\cdot
p_{\mathcal{M},T}(M_{3}(H\cup\mathbf{D}))\cdot
p_{\mathcal{L},T}(L_{3}(H\cup\mathbf{D}))]]\leq\epsilon\cdot\mu_{3}(\mathcal{R})+2^{-\eta
m}.$ (4.6)

We need the following lemma from [19], which was implicitly stated in [18] to
prove the set disjointness lower bound, and has been widely used in various
forms in other works as well. The lemma is essentially based on an entropy
counting argument.

######  Lemma 4.5 ([19])

For every $\alpha,\beta>0$ and $q\in\mathbb{N}$, there is a constant
$\delta:=\delta(\alpha,\beta,q)$ such that the following holds. Let
$X_{1},\ldots,X_{m}$ be sets of size $|X_{i}|\leq q$, and denote
$X:=X_{1}\times\cdots\times X_{m}$. Let $Y\subseteq X$ be a subset of size
$|Y|\geq 2^{-\delta m}|X|$. We say an index $i\in[m]$ is $\alpha$-unbiased, if

$\frac{1}{1+\alpha}\Pr_{y\in X}[y\in Y]\leq\Pr_{y\in X}[y\in
Y:y_{i}=j]\leq(1+\alpha)\Pr_{y\in X}[y\in Y].$

for every $j\in X_{i}$. Then at most $\beta m$ indices are $\alpha$-biased.

To prove (4.6), we use the same framework as that in Rothvoss’s paper. The
rough idea is as follows. First, we swap the order of the expectations in the
left-hand side of (4.6). For each fixed $3$-violation entry $(M,L)$, we sample
the uniform distribution over the set of all triples $(T,H,\mathbf{D})$ that
generate $(M,L)$. Let $J$ denote the set of indices $i\in[m]$ such that
$L_{\mathbf{A}_{i}}=L_{B}(\mathbf{A}_{i})$. Then we pick a uniformly random
$i\in J\cup\\{0\\}$, and exchange $\mathbf{D}$ with $\mathbf{A}_{j}$ (we let
$\mathbf{A}_{0}:=\mathbf{D}$). Observe that we still obtain a uniform
distribution over tuples that generate $(M,L)$. If $(T,H,\mathbf{D})$ is bad,
then it is not small, so by Lemma 4.5, at most $\epsilon^{\prime}m$ indices
are biased. The ideal situation is that
$|J|\geq\frac{\epsilon^{\prime}}{\epsilon}{m}$ so that at most an
$\epsilon$-fraction of triples are bad. However, it is possible that $|J|$ is
small, say $o(m)$. In that case, we cannot bound the contribution since we
only have an $O(m)$ upper bound on the number of biased indices. To get around
this, we need the notions of balanced matchings and balanced labelings.

Given a partition $T$, we say a matching $M\in\mathcal{M}_{\mathrm{all}}(T)$
is balanced w.r.t. $T$ if $M_{\mathbf{B}_{i}}=M_{A}(\mathbf{B}_{i})$ for at
least a $\frac{1}{2c_{k}}$-fraction of indices $i\in[m]$, where
$c_{k}:=(4k)!$. Let
$\mathrm{Bal_{M}}(T):=\\{M\in\mathcal{M}_{\mathrm{all}}(T):|\\{i\in[m]:M_{\mathbf{B}_{i}}=M_{A}(\mathbf{B}_{i})\\}|\geq\frac{m}{2c_{k}}\\}$
denote the set of all such matchings. Likewise, we say a labeling
$L\in\mathcal{L}_{\mathrm{all}}(T)$ is balanced w.r.t. $T$ if
$L_{\mathbf{A}_{i}}=L_{B}(\mathbf{A}_{i})$ for at least a
$\frac{1}{2c_{k}}$-fraction of $i\in[m]$. Let
$\mathrm{Bal_{L}}(T):=\\{L\in\mathcal{L}_{\mathrm{all}}(T):|\\{i\in[m]:L_{\mathbf{A}_{i}}=L_{B}(\mathbf{A}_{i})\\}|\geq\frac{m}{2c_{k}}\\}$
denote the set of all such labelings. Note that the number of perfect
matchings consistent with some particular labeling on a block of size $4k$ is
exactly $c_{k}$ and the number of labelings consistent with some particular
perfect matching on a block of size $4k$ is $2^{4k}<c_{k}$. Recall the process
that generates $\mu_{3}$. We first sample the triple $(T,H,\mathbf{D})$, and
then we sample $(M,L)$ according to a product distribution:
$M\sim\mathcal{M}_{\mathrm{all}}(T,M_{3}(H\cup\mathbf{D})),L\sim\mathcal{L}_{\mathrm{all}}(T,L_{3}(H\cup\mathbf{D}))$.
Observe that
$M_{\mathbf{A}_{1}},\ldots,M_{\mathbf{A}_{m}},L_{\mathbf{B}_{1}},\ldots,L_{\mathbf{B}_{m}}$
are independent. Moreover,
$\mathbb{E}[|\\{i\in[m]:L_{\mathbf{A}_{i}}=L_{B}(\mathbf{A}_{i})\\}|]>\mathbb{E}[|\\{i\in[m]:M_{\mathbf{B}_{i}}=M_{A}(\mathbf{B}_{i})\\}|]=\frac{m}{c_{k}}$.
By the Chernoff bound and union bound, for sufficiently large $m$, we thus
have

$\mathbb{E}_{M\sim\mathcal{M}_{\mathrm{all}}(T,M_{3}(H\cup\mathbf{D})),L\sim\mathcal{L}_{\mathrm{all}}(T,L_{3}(H\cup\mathbf{D}))}\left[\mathbf{1}_{M\notin\mathrm{Bal_{M}}(T)\lor
L\notin\mathrm{Bal_{L}}(T)}\right]\leq 2e^{-\frac{m}{8c_{k}}}<2^{-\eta m},$

where $\eta:=\eta(k)=\frac{1}{16c_{k}}$. In other words, for any fixed
partition $T$, the contribution of unbalanced entries is tiny. Thus we only
need to bound the contribution of balanced entries:

$\displaystyle\mathbb{E}_{T,H,\mathbf{D}}\left[\mathbb{E}_{M\sim\mathcal{M}_{\mathrm{all}}(T,M_{3}(H\cup\mathbf{D})),L\sim\mathcal{L}_{\mathrm{all}}(T,L_{3}(H\cup\mathbf{D}))}\left[\mathrm{BAD}(T,H,D)\cdot\mathbf{1}_{(M,L)\in\mathcal{R}\land
M\in\mathrm{Bal_{M}}(T)\land L\in\mathrm{Bal_{L}}(T)}\right]\right]$
$\displaystyle\leq\epsilon\cdot\mu_{3}(\mathcal{R}).$ (4.9)

By swapping the order of expectations, we get

$\text{L.H.S. of
}\eqref{eqn:ctrbtn_balanced}=\mathbb{E}_{(M,L)\sim\mu_{3}}\left[\mathbf{1}_{(M,L)\in\mathcal{R}}\cdot\mathbb{E}_{(T,H,\mathbf{D})\sim\mathcal{P}(M,L)}[\mathrm{BAD}(T,H,\mathbf{D})\cdot\mathbf{1}_{M\in\mathrm{Bal_{M}}(T)}\cdot\mathbf{1}_{L\in\mathrm{Bal_{L}}(T)}]\right],$
(4.10)

where $\mathcal{P}(M,L)$ is defined as the set of triples $(T,H,\mathbf{D})$
that could generate $(M,L)$, i.e.

$\mathcal{P}(M,L):=\\{(T,H,\mathbf{D}):M\in\mathcal{M}_{\mathrm{all}}(T,M_{3}(H\cup\mathbf{D})),L\in\mathcal{L}_{\mathrm{all}}(T,L_{3}(H\cup\mathbf{D}))\\}.$

The reason why the inner expectation of the right-hand side of (4.10) is
taking the uniform distribution is given by Bayes’ rule and the fact that we
sample the triples $(T,H,\mathbf{D})$ with equal probability when we generate
$\mu_{3}$:

$\Pr[(T,H,\mathbf{D})\mid(M,L)]=\frac{\Pr[(T,H,\mathbf{D})]\Pr[(M,L)\mid(T,H,\mathbf{D})]}{\Pr[(M,L)]}=\frac{\Pr[(T,H,\mathbf{D})]}{((4k)!2^{4k})^{m}\mu_{3}(M,L)}.$

To complete the proof of (4.6), it suffices to bound the proportion of bad
triples for each pair $(M,L)$:

$\mathbb{E}_{(T,H,\mathbf{D})\sim\mathcal{P}(M,L)}[\mathrm{BAD}(T,H,\mathbf{D})\cdot\mathbf{1}_{M\in\mathrm{Bal_{M}}(T)}\cdot\mathbf{1}_{L\in\mathrm{Bal_{L}}(T)}]\leq\epsilon.$
(4.11)

Indeed, (4.6) directly follows from (4.11) since

$\eqref{eqn:swap_expect}\leq\mathbb{E}_{(M,L)\sim\mu_{3}}\left[\mathbf{1}_{(M,L)\in\mathcal{R}}\cdot\epsilon\right]=\epsilon\cdot\mu_{3}(\mathcal{R}).$

Given a triple $(T,H,\mathbf{D})\in\mathcal{T}$, we say $(T,H,\mathbf{D})$ is
$\mathcal{M}-$bad (resp. $\mathcal{L}-$bad), if $(T,H,\mathbf{D})$ is neither
small nor $\mathcal{M}-$good (resp. $\mathcal{L}-$good). Let
$\mathcal{M}-\mathrm{BAD}(T,H,\mathbf{D})$ (resp.
$\mathcal{L}-\mathrm{BAD}(T,H,\mathbf{D})$) denote its corresponding indicator
function. Note that if $(T,H,\mathbf{D})$ is bad, it is either
$\mathcal{M}-$bad or $\mathcal{L}-$bad. Then we have

$\displaystyle\text{L.H.S. of }\eqref{eqn:tbc_of_entry}$
$\displaystyle\leq\mathbb{E}_{(T,H,\mathbf{D})\sim\mathcal{P}(M,L)}[\mathcal{M}-\mathrm{BAD}(T,H,\mathbf{D})\cdot\mathbf{1}_{M\in\mathrm{Bal_{M}}(T)}]$
$\displaystyle+\mathbb{E}_{(T,H,\mathbf{D})\sim\mathcal{P}(M,L)}[\mathcal{L}-\mathrm{BAD}(T,H,\mathbf{D})\cdot\mathbf{1}_{L\in\mathrm{Bal_{L}}(T)}].$

We will bound the contribution of $\mathcal{M}$-bad triples and
$\mathcal{L}$-bad triples separately.

###### Lemma 4.6

Let $(M,L)$ be a $3$-violation entry in the support of $\mu_{3}$. Then

$\mathbb{E}_{(T,H,\mathbf{D})\sim\mathcal{P}(M,L)}[\mathcal{L}-\mathrm{BAD}(T,H,\mathbf{D})\cdot\mathbf{1}_{L\in\mathrm{Bal_{L}}(T)}]\leq\frac{\epsilon}{2}.$

###### Lemma 4.7

Let $(M,L)$ be a $3$-violation entry in the support of $\mu_{3}$. Then

$\mathbb{E}_{(T,H,\mathbf{D})\sim\mathcal{P}(M,L)}[\mathcal{M}-\mathrm{BAD}(T,H,\mathbf{D})\cdot\mathbf{1}_{M\in\mathrm{Bal_{M}}(T)}]\leq\frac{\epsilon}{2}.$

Here we will only present the proof for Lemma 4.6. Lemma 4.7 can be proved
analogously.

  * Proof.

[Proof of Lemma 4.6] We first sample a uniform triple
$(T,H,\mathbf{D})\sim\mathcal{P}(M,L)$. In order to show the desired bound, we
introduce one more step, which yields the same uniform distribution. Let
$J(T,L)=\\{0\leq i\leq m:L_{\mathbf{A}_{i}}=L_{B}(\mathbf{A}_{i})\\}$ (we
define $\mathbf{A}_{0}:=\mathbf{D}$ so $0$ is guaranteed to be in $J(T,L)$).
Then we pick $i\in J(T,L)$ uniformly at random. Finally, we exchange
$\mathbf{A}_{i}$ with $\mathbf{D}$ (if $i=0$, nothing happens) and get a new
triple $(T^{\prime},H,\mathbf{D}^{\prime}=\mathbf{A}_{i})$. We claim that the
distribution of $(T^{\prime},H,\mathbf{D}^{\prime})$ is still uniform over
$\mathcal{P}(M,L)$. In fact, for any
$(T^{\prime},H,\mathbf{D}^{\prime})\in\mathcal{P}(M,L)$, there are exactly
$|J(T^{\prime},L)|$ many triples $(T,H,\mathbf{D})\in\mathcal{P}(M,L)$ that
could generate $(T^{\prime},H,\mathbf{D}^{\prime})$ by following the above
exchange process, and for each of those triples, the probability that
$(T^{\prime},H,\mathbf{D}^{\prime})$ is sampled is exactly
$\frac{1}{|J(T^{\prime},L)|}$.

Then we can deduce that

$\displaystyle\mathbb{E}_{(T,H,\mathbf{D})\sim\mathcal{P}(M,L)}[\mathcal{L}-\mathrm{BAD}(T,H,\mathbf{D})\cdot\mathbf{1}_{L\in\mathrm{Bal_{L}}(T)}]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{(T,H,\mathbf{D})\sim\mathcal{P}(M,L)}\left[\mathbb{E}_{i\in
J(T,L)}\left[\mathcal{L}-\mathrm{BAD}(T^{i},H,\mathbf{D}^{i})\cdot\mathbf{1}_{L\in\mathrm{Bal_{L}}(T^{i})}\right]\right],$

where $(T^{i},H,\mathbf{D}^{i})$ is the triple induced by swapping the role of
$\mathbf{D}$ and $\mathbf{A}_{i}$ in $(T,H,\mathbf{D})$.

It suffices to show for any fixed $(T,H,\mathbf{D})\in\mathcal{P}(M,L)$,

$\mathbb{E}_{i\in
J(T,L)}[\mathcal{L}-\mathrm{BAD}(T^{i},H,\mathbf{D}^{i})\cdot\mathbf{1}_{L\in\mathrm{Bal_{L}}(T^{i})}]\leq\epsilon/2.$
(4.12)

If $|J(T,L)|<\frac{m}{2c_{k}}$, then $L\notin\mathrm{Bal_{L}}(T^{i})$ for all
$i\in J(T,L)$. We can then conclude that the left-hand side of (4.12) is $0$,
as desired.

On the other hand, if $|J(T,L)|\geq\frac{m}{2c_{k}}$, we can assume that
$(T^{j},H,\mathbf{D}^{j})$ is bad for some $j\in J(T,L)$ because otherwise,
the left-hand side of (4.12) is again $0$. Define $X_{i}:=\\{\text{all
labelings on }\mathbf{A}_{i}$ consistent with $M_{A}(\mathbf{A}_{i})\\}$, and
$X:=X_{0}\times\cdots\times X_{m}$. Let

$Y:=\\{L_{\mathbf{A}_{0}\cup\cdots\cup\mathbf{A}_{m}}:L\in\mathcal{L}_{\mathrm{all}}(T^{j},L_{3}(H\sqcup\mathbf{D}^{j}))\cap\mathcal{L}\\}\subseteq
X$

be the set of labelings $L$’s restrictions on $\mathbf{D}$ and A-blocks, where
$L$ is sampled w.r.t. $(T,H,\mathbf{D})$ when generating $\mu_{3}$ and
$L\in\mathcal{L}$ (recall $\mathcal{L}$ is the set of columns of the fixed
rectangle $\mathcal{R}=\mathcal{M}\times\mathcal{L}$). Then we have

$|Y|\geq 2^{-\delta m}\prod_{i\neq j}|X_{i}|\geq 2^{-1.1\delta m}|X|,$

where the first inequality follows from the assumption that
$(T^{j},H,\mathbf{D}^{j})$ is not small, and the second inequality follows
from the simple observation that $2^{0.1\delta m}>c_{k}\geq|X_{j}|$ when $m$
is sufficiently large.

Choosing $\delta:=0.9\delta(\frac{\epsilon}{3},\frac{\epsilon}{4c_{k}},c_{k})$
in Lemma 4.5, the number of $\frac{\epsilon}{3}$-biased indices is bounded by
$\frac{\epsilon m}{4c_{k}}$, which implies that at most an
$\frac{\epsilon}{2}$-fraction of indices $i\in J(T,L)$ are
$\frac{\epsilon}{3}$-biased.

To complete the proof, we only need to show that for any
$\frac{\epsilon}{3}$-unbiased index $i$, $(T^{i},H,\mathbf{D}^{i})$ is
$\mathcal{L}$-good. Indeed, if $i$ is $\frac{\epsilon}{3}$-unbiased, for any
labeling $L^{\prime}$ on $G_{\mathbf{A}_{i}}$ consistent with
$M_{A}(\mathbf{A}_{i})$, we have $p_{\mathcal{L},T^{i}}(L_{3}(H)\cup
L^{\prime})\geq\frac{1}{1+\epsilon/3}\Pr_{y\sim X}[y\in Y]$ and
$p_{\mathcal{L},T^{i}}(L_{3}(H\cup\mathbf{D}^{i}))\leq(1+\epsilon/3)\Pr_{y\sim
X}[y\in Y]$. Thus

$p_{\mathcal{L},T^{i}}(L_{3}(H\cup\mathbf{D}^{i}))\leq(1+\epsilon)p_{\mathcal{L},T^{i}}(L_{3}(H)\cup
L^{\prime})$ (4.13)

since $(1+\epsilon/3)^{2}\leq 1+\epsilon$.

Therefore, for at most an $\frac{\epsilon}{2}$-fraction of indices $i\in
J(T,L)$, $(T^{i},H,\mathbf{D}^{i})$ is $\mathcal{L}$-bad, which directly
implies (4.12).

In conclusion, no matter the size of $J(T,L)$, (4.12) always holds. So the
lemma follows.

##  5 Polytope Feasibility

In this section we prove that our relaxation is infeasible if and only if the
bipartite graph $G$ has no perfect matching with an odd number of red edges
(called an odd-red PM). Recall that the feasibility linear program we used is
the following.

$\displaystyle\sum_{e\in\delta(u)}x_{e}$ $\displaystyle=1\quad\mbox{for all
}u\in U\cup V$ $\displaystyle\sum_{e\in E_{L}}x_{e}$ $\displaystyle\geq
1\quad\mbox{for all }L\in\mathcal{L}_{\mathrm{all}}(G)$ $\displaystyle x_{e}$
$\displaystyle\geq 0\quad\mbox{for all $e\in E$}.$

Here, labelings $\mathcal{L}_{\mathrm{all}}(G)$ are as defined in Section 3.
In other words, we will prove that $G$ has no odd-red PM if and only if there
is a labeling such that all edges of $G$ that are in some perfect matching
(let us call them the relevant edges) are consistent with this labeling,
proving the following.

###### Theorem 5.1

The above LP is feasible if and only if $G$ has an odd-red perfect matching.

  * Proof.

By Claim 3.1, if $G$ has an odd-red PM then there is no labeling such that all
matching edges are consistent and so the indicator vector of this odd-red PM
satisfies the above constraints. It remains to prove that if $G$ has no odd-
red PM then the above polytope is empty. We will do this by showing that if
$G$ has no odd-red PM then there is a labeling consistent with all relevant
edges. This is sufficient because any feasible point in the above LP is a
convex combination of perfect matchings since the bipartite matching polytope
is integral, but all the edges in these perfect matchings will be consistent
with some labeling so the polytope is indeed empty. To this end, fix a perfect
matching of $G$ that has an even number of red edges. We show that if we
cannot find a labeling consistent on all the relevant edges, then we can find
an odd-red perfect matching.

Consider the edge-induced subgraph of relevant edges and take some connected
component. We direct the edges: direct $e$ from the left partition to the
right partition if $e$ is in the perfect matching and right to left otherwise.

###### Claim 5.1

This component is strongly connected unless it is a single edge.

    * Proof.

For any edge in this component, it is either in every perfect matching that
exists in $G$, or not. In the former case, the component is just the single
edge since no edges adjacent to either endpoint can be in any perfect
matching.

In the latter case, since the edge is relevant, it must be in an alternating
cycle of the perfect matching we fixed at the beginning. In fact, then every
edge in the component has this property since an edge cannot be in every
perfect matching if it has an adjacent edge that is in some perfect matching.
Now that every edge is in an alternating cycle, we have that the component is
strongly connected.

Now it suffices to either consistently label this strongly connected component
or find an odd-red alternating cycle. Note that by rotating the matching on a
single odd-red alternating cycle we change the parity of the red edges in the
perfect matching. To this end, start at some vertex in the left partition and
build a tree using breadth-first search (depth-first search works the same).
Let the root node be at depth zero. We have that even-depth vertices in the
tree have a single out-going edge that is a matching edge and odd-depth
vertices can have multiple out-going edges that are all non-matching since we
started in the left partition.

Fix some labeling consistent with the edges of the tree, which is possible
because there are no cycles. However, there are non-tree edges that could
violate this labeling. In particular, a non-tree edge is a non-matching edge
and directs from an odd-depth vertex to an even-degree one, and is either a
back-edge (directs to a lower-depth vertex on the same root-leaf path), a
forward-edge (directs to a higher-depth vertex on the same root-leaf path), or
a cross-edge.

Consider first the case of a back-edge $(u,v)$, as seen in Figure 6. Then we
have an alternating cycle starting from $v$ that uses tree edges until $u$,
and then uses the violating edge $(u,v)$, so it has exactly one violating
edge.

$u$$v$ Figure 6: Back-edge along same root-leaf path, with the green edge
violating the labeling.

###### Claim 5.2

An even cycle has an odd number of red edges if and only if for every labeling
there are an odd number of violating edges.

  * Proof.

Note that the parity of blue edges is the same as the parity of red edges in
an even cycle. If we start with an arbitrary label at an arbitrary vertex and
label the vertices consistently with the edge colors by walking around the
cycle, then each blue edge flips the sign of the last labelled vertex. Hence,
an odd number of blue edges results in one violating edge and an even number
of blue edges results in all edges being consistently labelled. Now if we
start flipping some labels, each flipped label can either add two violating
edges if the two incident edges to the flipped vertex were originally
consistent, subtract two violating edges if the incident edges were originally
violating, or maintain the number of violating edges if one incident edge was
violating and the other was consistent. Hence, the parity of number of
violating edges is preserved for any labeling.

With this claim, we have that the alternating cycle in Figure 6 has an odd
number of red edges so we have an odd-red matching.

$u$$v$lca$(u,v)$ Figure 7: Forward edge $uv$. The dotted curve in blue shows
some path from $v$ to $u$.

Now suppose that the violating non-tree edge $(u,v)$ is a forward edge, as in
Figure 7. Since the component is strongly connected by Claim 5.1 there must be
an alternating path from $v$ to the lowest common ancestor of $u$ and $v$,
lca$(u,v)$ (which in this case is just $u$). If there are an odd number of
violating edges in this path then complete a circuit by going from lca$(u,v)$
to $v$ by only taking tree-edges. Otherwise, the completed circuit by going
from lca$(u,v)$ to $v$ using the violating edge $(u,v)$ has an odd number of
violating edges. In either case, this circuit enters and exits every vertex
the same number of times so the edges traversed form an Eulerian circuit. A
basic fact in graph theory says that an Eulerian circuit can be decomposed
into edge-disjoint cycles. Since the original circuit had an odd number of
violating edges it cannot be that every cycle in the decomposition has an even
number of violating edges. Taking a cycle with an odd number of violating
edges, by Claim 5.2 it is an odd-red alternating cycle.

Actually the case of a cross non-tree edge $(u,v)$ is the same. It can look
like either tree in Figure 8, depending on the relative depths of $u$ and $v$,
but we have the same argument as for forward edges. This concludes the proof
of Theorem 5.1.

$u$$v$lca$(u,v)$

$u$$v$lca$(u,v)$

Figure 8: Cross-edges. The dotted curves in blue show some path from $v$ to
lca$(u,v)$.

## References

  * [1] Jacobi’s bound.  https://www.lix.polytechnique.fr/~ollivier/JACOBI/jacobiEngl.htm.  Accessed: 2022-07-13.
  * [2] Stephan Artmann, Robert Weismantel, and Rico Zenklusen.  A strongly polynomial algorithm for bimodular integer linear programming.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, page 1206–1219, New York, NY, USA, 2017. Association for Computing Machinery.  doi:10.1145/3055399.3055473.
  * [3] Egon Balas.  Disjunctive programming: Properties of the convex hull of feasible points.  Discrete Applied Mathematics, 89(1):3–44, 1998.  URL: https://www.sciencedirect.com/science/article/pii/S0166218X9800136X, doi:https://doi.org/10.1016/S0166-218X(98)00136-X.
  * [4] Gábor Braun and Sebastian Pokutta.  The matching problem has no fully polynomial size linear programming relaxation schemes.  IEEE Transactions on Information Theory, 61(10):5754–5764, 2015\.  doi:10.1109/TIT.2015.2465864.
  * [5] Alfonso Cevallos, Stefan Weltge, and Rico Zenklusen.  Lifting linear extension complexity bounds to the mixed-integer setting.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 788–807. Society for Industrial and Applied Mathematics, jan 2018.  URL: https://doi.org/10.1137%2F1.9781611975031.51, doi:10.1137/1.9781611975031.51.
  * [6] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  CoRR, abs/2203.00671, 2022.
  * [7] Jack Edmonds.  Maximum matching and a polyhedron with $0,1$ vertices.  Journal of Research of the National Bureau of Standards, 69:125–130, 1965.
  * [8] Jack Edmonds.  Paths, trees, and flowers.  Canadian Journal of Mathematics, 17:449–467, 1965.
  * [9] Nicolas ElMaalouly.  Exact matching: Algorithms and related problems, 2022.  URL: https://arxiv.org/abs/2203.13899, doi:10.48550/ARXIV.2203.13899.
  * [10] Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf.  Bipartite perfect matching is in quasi-NC.  In STOC, pages 754–763, 2016.
  * [11] Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf.  Linear vs. semidefinite extended formulations: Exponential separation and strong lower bounds.  In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, page 95–106, New York, NY, USA, 2012. Association for Computing Machinery.  doi:10.1145/2213977.2213988.
  * [12] Rohit Gurjar, Arpita Korwar, Jochen Messner, and Thomas Thierauf.  Exact perfect matching in complete graphs.  ACM Trans. Comput. Theory, 9(2), apr 2017.  doi:10.1145/3041402.
  * [13] Rohit Gurjar and Thomas Thierauf.  Linear matroid intersection is in quasi-NC.  In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 821–830, 2017.
  * [14] Rohit Gurjar, Thomas Thierauf, and Nisheeth K. Vishnoi.  Isolating a vertex via lattices: Polytopes with totally unimodular faces.  In ICALP, pages 74:1–74:14, 2018.
  * [15] Russell Impagliazzo and Avi Wigderson.  _P = BPP_ if _E_ requires exponential circuits: Derandomizing the XOR lemma.  In STOC, pages 220–229, 1997.
  * [16] Nicolas El Maalouly and Raphael Steiner.  Exact matching in graphs of bounded independence number, 2022.  URL: https://arxiv.org/abs/2202.11988, doi:10.48550/ARXIV.2202.11988.
  * [17] Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani.  Matching is as easy as matrix inversion.  In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC ’87, page 345–354, New York, NY, USA, 1987. Association for Computing Machinery.  doi:10.1145/28395.383347.
  * [18] A.A. Razborov.  On the distributional complexity of disjointness.  Theoretical Computer Science, 106(2):385–390, 1992.  URL: https://www.sciencedirect.com/science/article/pii/030439759290260M, doi:https://doi.org/10.1016/0304-3975(92)90260-M.
  * [19] Thomas Rothvoss.  The matching polytope has exponential extension complexity.  J. ACM, 64(6), sep 2017.  doi:10.1145/3127497.
  * [20] Makrand Sinha.  Lower bounds for approximating the matching polytope.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18, page 1585–1604, USA, 2018. Society for Industrial and Applied Mathematics.
  * [21] Ola Svensson and Jakub Tarnawski.  The matching problem in general graphs is in quasi-nc.  In FOCS, pages 696–707, 2017.
  * [22] Mihalis Yannakakis.  Expressing combinatorial optimization problems by linear programs.  In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, page 223–228, New York, NY, USA, 1988. Association for Computing Machinery.  doi:10.1145/62212.62232.