# Matroid-Based TSP Rounding for Half-Integral Solutions

Anupam Gupta Carnegie Mellon University, Pittsburgh PA 15217. Euiwoong Lee
University of Michigan, Ann Arbor MI 48109. Most of this work was done when
the author was a postdoc at NYU and supported in part by the Simons
Collaboration on Algorithms and Geometry.  Jason Li Simons Institute for the
Theory of Computing and UC Berkeley, Berkeley CA 94720. Marcin Mucha
University of Warsaw, Warsaw, Poland. Heather Newman∗ Sherry Sarkar∗

###### Abstract

We show how to round any half-integral solution to the subtour-elimination
relaxation for the TSP, while losing a less-than-1.5 factor. Such a rounding
algorithm was recently given by Karlin, Klein, and Oveis Gharan based on
sampling from max-entropy distributions. We build on an approach of Haddadan
and Newman to show how sampling from the matroid intersection polytope, and a
new use of max-entropy sampling, can give better guarantees.

##  1 Introduction

The (symmetric) traveling salesman problem asks: given an graph $G=(V,E)$ with
edge-lengths $c_{e}\geq 0$, find the shortest tour that visits all vertices at
least once. The Christofides-Serdyukov algorithm [Chr76, Ser78] gives a
$\nicefrac{{3}}{{2}}$-approximation to this APX-hard problem; this was
recently improved to a $(\nicefrac{{3}}{{2}}-\varepsilon)$-approximation by
the breakthrough work of Karlin, Klein, and Oveis Gharan, where
$\varepsilon>0$ [KKO20b]. A related question is: _what is the integrality gap
of the subtour-elimination polytope relaxation for the TSP_? Wolsey had
adapted the Christofides-Serdyukov analysis to show an upper bound of
$\nicefrac{{3}}{{2}}$ [Wol80] (also [SW90]), and there exists a lower bound of
$\nicefrac{{4}}{{3}}$. Building on their above-mentioned work, Karlin, Klein,
and Oveis Gharan gave an integrality gap of $1.5-\varepsilon^{\prime}$ for
another small constant $\varepsilon^{\prime}>0$ [KKO21], thereby making the
first progress towards the conjectured optimal value of $\nicefrac{{4}}{{3}}$
in nearly half a century.

Both these recent results are based on a randomized version of the
Christofides-Serdyukov algorithm proposed by Oveis Gharan, Saberi, and Singh
[OSS11]. This algorithm first samples a spanning tree (plus perhaps one edge)
from the _max-entropy distribution_ with marginals matching the LP solution,
and adds an $O$-join on the odd-degree vertices $O$ in it, thereby getting an
Eulerian spanning subgraph. Since the first step has expected cost equal to
that of the LP solution, these works then bound the cost of this $O$-join by
strictly less than half the optimal value, or the LP value. The proof uses a
cactus-like decomposition of the min-cuts of the graph with respect to the
values $x_{e}$, like in [OSS11].

Given the $\nicefrac{{3}}{{2}}$ barrier has been broken, we can ask: what
other techniques can be effective here? How can we make further progress?
These questions are interesting even for cases where the LP has additional
structure. The half-integral cases are particularly interesting due to the
Schalekamp, Williamson, and van Zuylen conjecture, which says that the
integrality gap is achieved on instances where the LP has optimal half-
integral solutions [SWvZ14]. The team of Karlin, Klein, and Oveis Gharan first
used their max-entropy approach to get an integrality gap of $1.4998$ for
half-integral LP solutions [KKO20a], before they moved on to the general case
in [KKO20b] and obtained an integrality gap of $1.5-\varepsilon$; the latter
improvement is considerably smaller than in the half-integral case. It is
natural to ask: can we do better for half-integral instances?

In this paper, we answer this question affirmatively. We show how to get tours
of expected cost at most $1.4983$ times the linear program value using an
algorithm based on matroid intersection. Moreover, some of these ideas can be
used to strengthen the max-entropy sampling approach in the half-integral
case. The matroid intersection approach and the strengthened max-entropy
approach each yield improvements over the bound in [KKO20a]. Combining the
techniques gives our final quantitative improvement:

######  Theorem 1.1.

Let $x$ be a half-integral solution to the subtour elimination polytope with
cost $c(x)$. There is a randomized algorithm that rounds $x$ to an integral
solution whose cost is at most ${(1.5-\varepsilon)\cdot c(x)}$, where
$\varepsilon=0.001695$.

We view our work as showing a proof-of-concept of the efficacy of
combinatorial techniques (matroid intersection, and flow-based charging
arguments) in getting an improvement for the half-integral case. We hope that
these techniques, ideally combined with max-entropy sampling techniques, can
give further progress on this central problem.

##### Our Techniques

The algorithm is again in the Christofides-Serdyukov framework. It is easiest
to explain for the case where the graph (a) has an even number of vertices,
and (b) has no (non-trivial) proper min-cuts with respect to the LP solution
values $x_{e}$—specifically, the only sets for which $x(\partial S)=2$
correspond to the singleton cuts. Here, our goal is that each edge is “even”
with some probability: i.e., both of its endpoints have even degree with
probability $p>0$. In this case we use an idea due to Haddadan and Newman
[HN19]: we _shift_ and get a $\\{\nicefrac{{1}}{{3}},1\\}$-valued solution $y$
to the subtour elimination polytope $K_{TSP}$. Specifically, we find a random
perfect matching $M$ in the support of $x$, and set $y_{e}=1$ for $e\in M$,
and $\nicefrac{{1}}{{3}}$ otherwise, thereby ensuring $\mathbb{E}[y]=x$. To
pick a random tree from this shifted distribution $y$, we do one of the
following:

  1. 1.

We pick a random “independent” set $M^{\prime}$ of matching edges (so that no
edge in $E$ is incident to two edges of $M^{\prime}$). For each $e^{\prime}\in
M^{\prime}$, we place partition matroid constraints enforcing that exactly one
edge is picked at each endpoint—which, along with $e^{\prime}$ itself, gives
degree $2$ and thereby makes the edge even as desired. Finding spanning trees
subject to another matroid constraint can be implemented using matroid
intersection.

  2. 2.

Or, instead we sample a random spanning tree from the max-entropy
distribution, with marginals being the shifted value $y$. (In contrast,
[KKO20a] sample trees from $x$ itself; our shifting allows us to get stronger
notions of evenness than they do: e.g., we can show that every edge is “even-
at-last” with constant probability, as opposed to having at least one even-at-
last edge in each tight cut with some probabiltiy.)

(Our algorithm randomizes between the two samplers to achieve the best
guarantees.) For the $O$-join step, it suffices to give fractional values
$z_{e}$ to edges so that for every odd cut in $T$, the $z$-mass leaving the
cut is at least 1. In the special case we consider, each edge only
participates in two min-cuts—those corresponding to its two endpoints. So set
$z_{e}=\nicefrac{{x_{e}}}{{3}}$ if $e$ is even, and $\nicefrac{{x_{e}}}{{2}}$
if not; the only cuts with $z(\partial S)<1$ are minimum cuts, and these cuts
will not show up as $O$-join constraints, due to evenness. For this setting,
if an edge is even with probability $p$, we get a
$(\nicefrac{{3}}{{2}}-\nicefrac{{p}}{{6}})$-approximation!

It remains to get rid of the two simplifying assumptions. To sample trees when
$|V|$ is odd (an open question from [HN19]), we add a new vertex to fix the
parity, and perform local surgery on the solution to get a new TSP solution
and reduce to the even case. The challenge here is to show that the losses
incurred are small, and hence each edge is still even with constant
probability.

Finally, what if there are proper tight sets $S$, i.e., where $x(\partial
S)=2$? We use the cactus decomposition of a graph (also used in [OSS11,
KKO20a]) to sample spanning trees from pieces of $G$ with no proper min-cuts,
and stitch these trees together. These pieces are formed by contracting sets
of vertices in $G$, and have a hierachical structure. Moreover, each such
piece is either of the form above (a graph with no proper min-cuts) for which
we have already seen samplers, or else it is a double-edged cycle (which is
easily sampled from). Since each edge may now lie in many min-cuts, we no
longer just want an edge to have both endpoints be even. Instead, we use an
idea from [KKO20a] that uses the hierarchical structure on the pieces
considered above. Every edge of the graph is “settled” at exactly one of these
pieces, and we ask for both of its endpoints to have even degree _in the piece
at which it is settled_. The $z_{e}$ value of such an edge may be lowered in
the $O$-join without affecting constraints corresponding to cuts _in the piece
at which it is settled_.

Since cuts at other levels of the hierarchy may now be deficient because of
the lower values of $z_{e}$, we may need to increase the $z_{f}$ values for
other “lower” edges $f$ to satisfy these deficient cuts. This last part
requires a charging argument, showing that each edge $e$ has $z_{e}$ that is
strictly smaller than $\nicefrac{{x_{e}}}{{2}}$ in expectation. For our
samplers, the naïve approach of distributing charge uniformly as in [KKO20a]
does not work, so we instead formulate this charging as a flow problem.

##  2 Notation and Preliminaries

Given a multigraph $G=(V,E)$, and a set $S\subseteq V$, let $\partial S$
denote the cut consisting of the edges connecting $S$ to $V\setminus S$; $S$
and $\bar{S}\coloneqq V\setminus S$ are called _shores_ of the cut. (For a
singleton set $\\{v\\}$, we write $\partial v$ instead of $\partial\\{v\\}$.)
A subset $S\subseteq V$ is _proper_ if $1<|S|<|V|-1$; a cut $\partial S$ is
called _proper_ if the set $S$ is a proper subset. A set $S$ is _tight_ if
$|\partial S|$ equals the size of the minimum edge-cut in $G$. Two sets $S$
and $S^{\prime}$ are _crossing_ if $S\cap S^{\prime}$, $S\setminus
S^{\prime}$, $S^{\prime}\setminus S$, and $V\setminus(S\cup S^{\prime})$ are
all non-empty.

Define the _subtour elimination polytope_
$K_{TSP}(G)\subseteq\mathbb{R}^{|E|}$:

$\displaystyle x(\partial v)$ $\displaystyle=2\qquad\qquad\forall v\in V$ (LP-
TSP) $\displaystyle x(\partial S)$ $\displaystyle\geq
2\qquad\qquad\forall\;\text{proper $S$}$ $\displaystyle x\geq 0.$

Let $x$ be half-integral and feasible for (LP-TSP). W.l.o.g. we can focus on
solutions with $x_{e}=\nicefrac{{1}}{{2}}$ for each $e\in E$, doubling edges
if necessary. The support graph $G$ is then a $4$-regular $4$-edge-connected
(henceforth 4EC) multigraph.

The _spanning tree polytope_ $K_{spT}(G)\subseteq\mathbb{R}^{|E(G)|}$ for a
multigraph $G$ is:

$\displaystyle x(E(S))$ $\displaystyle\leq|S|-1\qquad\qquad\forall S\subseteq
V(G)$ (LP-spT) $\displaystyle x(E(V(G)))$ $\displaystyle=|V(G)|-1$
$\displaystyle x$ $\displaystyle\geq 0.$

where $E(S)$ is the set of edges with both endpoints in $S$. This is the
graphic matroid polytope, and the convex hull of the spanning trees.

######  Definition 2.1 ($r$-Trees).

Given a multigraph $G$ and “root” vertex $r\in V(G)$, an _$r$ -tree_ $T$ is a
connected subgraph with $n$ edges: the vertex $r$ has degree exactly $2$, and
the subgraph restricted to the other vertices $V(G)\setminus\\{r\\}$ is a
spanning tree on them. This is a matroid, though we do not use this fact.

The (integral) _perfect matching polytope_
$K_{PM}\subseteq\mathbb{R}^{|E(G)|}$ is defined as follows:

$\displaystyle x(\partial v)$ $\displaystyle=1\qquad\qquad\forall v\in V$ (LP-
PM) $\displaystyle x(\partial S)$ $\displaystyle\geq
1\qquad\qquad\forall\text{$S$ with $|S|$ odd}$ $\displaystyle x\geq 0.$

The (integral) _$O$ -join dominator polytope_ $K_{join}(G,O)$ is defined as
follows. Let $O\subseteq V$, $|O|$ even.

$\displaystyle z(\partial(S))$ $\displaystyle\geq 1\qquad\qquad\forall
S\subseteq V,|S\cap O|\text{ odd}$ $\displaystyle z$ $\displaystyle\geq 0$

######  Fact 2.2.

For any solution $x\in K_{TSP}(G)$, it holds that
$x|_{E(V(G)\setminus\\{r\\})}\in K_{spT}(G[V(G)\setminus\\{r\\}])$,
$\nicefrac{{x}}{{2}}\in K_{PM}(G)$ (when $|V(G)|$ is even), and
$\nicefrac{{x}}{{2}}\in K_{join}(G,O)$ for $O\subseteq V(G)$, $|O|$ even.

######  Lemma 2.3.

Consider a sub-partition $\mathcal{P}=\\{P_{1},P_{2},\ldots,P_{t}\\}$ of the
edge set of $G$. Let $x$ be a fractional solution to (LP-spT) that satisfies
$x(P_{i})\leq 1$ for all $i\in[t]$. Then we can efficiently sample from a
probability distribution $\mathcal{D}$ over spanning trees which contain at
most one edge from each of the parts $P_{i}$, such that
$\Pr_{T\leftarrow\mathcal{D}}[e\in T]=x_{e}$.

###### Proof.

This follows from the integrality of the matroid intersection polytope. ∎

###  2.1 The Max-Entropy Distribution over Spanning Trees

######  Definition 2.4 (Strong Rayleigh Distributions, [BBL09]).

Let $\mu$ be a probability distribution on spanning trees. The generating
polynomial for $\mu$ is $p(z)=\sum_{T\in\mathcal{T}}\mathbb{P}(e\in
T)\prod_{e\in T}z_{e}$. We say $\mu$ is _strongly Rayleigh (SR)_ if $p$ is a
real stable polynomial (i.e., $p(z)\neq 0$ if $z$ lies in the upper half
plane).

A distribution $\mu$ over spanning trees is called $\lambda\textit{-uniform}$
or weighted uniform if there exist non-negative weights
$\lambda:E\rightarrow\mathbb{R}$ such that $\mathbb{P}(T)\propto\prod_{e\in
T}\lambda(e)$. Borcea et al. [BBL09] showed that $\lambda$-uniform spanning
tree distributions are SR.

######  Theorem 2.5 ([OSS11]).

There exists a $\lambda$-uniform distribution $\mu$ over spanning trees such
that given $z$ in the spanning tree polytope of $G=(V,E)$,

$\sum_{T\ni e}\mathbb{P}_{\mu}(T)=z_{e}.$

The _max-entropy distribution_ , which is the distribution $\mu$ on spanning
trees maximizing the entropy of $\mu$ subject to preserving the marginals
$z_{e}$ (that is, $\mathbb{P}_{\mu}(e\in T)=z_{e}$), is one such distribution.

Asadpour et al [AGM+17] showed that we can find weights
$\tilde{\lambda}:E\rightarrow\mathbb{R}^{+}$ which approximately respect the
marginals given by a vector $z$ in the spanning tree polytope in polynomial
time.

######  Theorem 2.6 ([AGM+17]).

Given $z$ in the spanning tree polytope of $G=(V,E)$ and some $\varepsilon>0$,
values $\tilde{\lambda}_{e}$ for $e\in E$ can be found such that, for all
$e\in E$ , the $\tilde{\lambda}$-uniform distribution $\mu$ satisfies

$\sum_{T\ni e}\mathbb{P}_{\mu}(T)\leq(1+\varepsilon)z_{e}.$

The running time is polynomial in $|V|,\log\nicefrac{{1}}{{\min_{e}z_{e}}}$
and $\log\nicefrac{{1}}{{\varepsilon}}$.

######  Fact 2.7 ([BBL09]).

Let $\mu$ be an SR distribution. Let $F\subset E$ be a subset of edges. Then
the projection of $\mu$ onto $F$, i.e., $\mu_{|F}(A)=\sum_{S:S\cap
F=A}\mu(S)$, is also SR. Moreover, for any edge $e\in E$, conditioning on
$e\in T$ or on $e\not\in T$ preserves the SR property.

######  Theorem 2.8 (Negative Correlation, [OSS11]).

Let $\mu$ be an SR distribution on spanning trees.

  1. 1.

Let $S$ be a set of edges and $X_{S}=|S\cap T|$, where $T\sim\mu$. Then,
$X_{S}\sim\sum_{i=1}^{|S|}Y_{i}$, where the $Y_{i}$ are independent Bernoulli
random variables with success probabilities $p_{i}$ and
$\sum_{i}p_{i}=\mathbb{E}[X_{S}]$ .

  2. 2.

For any set of edges $S$ and $e\not\in S$,

     * (i)

$\mathbb{E}_{\mu}[X_{S}]\leq\mathbb{E}_{\mu}[X_{S}\mid
X_{e}=0]\leq\mathbb{E}_{\mu}[X_{S}]+\mathbb{P}_{\mu}(e\in T)$, and

     * (ii)

$\mathbb{E}_{\mu}[X_{S}]-1+\mathbb{P}_{\mu}(e\in
T)\leq\mathbb{E}_{\mu}[X_{S}\mid X_{e}=1]\leq\mathbb{E}_{\mu}[X_{S}]$.

######  Theorem 2.9 ([Hoe56], Corollary 2.1).

Let $g:\\{1,\ldots,m\\}\rightarrow\mathbb{R}$ and let $0\leq p\leq m$. Let
$B_{1},\ldots,B_{m}$ be Bernoulli random variables with probabilities
$p_{1}^{*},\ldots,p_{m}^{*}$ that maximize (or minimize)
${\mathbb{E}[g(B_{1}+\cdots+B_{m})]}$ over all possible success probabilities
$p_{i}$ for $B_{i}$ for which $p_{1}+\cdots+p_{m}=p$. Then
$\\{p_{1}^{*},\ldots,p_{m}^{*}\\}\in\\{0,x,1\\}$ for some $x\in(0,1)$.

##  3 Samplers

In this section, we describe the MaxEnt and MatInt samplers for graphs that
contain no proper min-cuts. We give bounds on certain correlations between
edges that will be used in §5 to prove that every edge is “even” with constant
probability. The samplers for the case where the graph has an odd number of
vertices are more technical and are deferred to Appendix B.

Suppose the graph $H=(V,E)$ is 4-regular and 4-edge-connected (4EC), contains
at least four vertices, and has no proper min-cuts.111This implies that $H$ is
a simple graph: since parallel edges between $u,v$ means that
$\partial(\\{u,v\\})$ is a proper min-cut; we use this simplicity of the graph
often in the arguments of this section. This means all proper cuts have six or
more edges. We are given a dedicated _external_ vertex $r\in V(H)$; the
vertices $I:=V\setminus\\{r\\}$ that are not external are called _internal_.
(In future sections, this vertex $r$ will be given by a cut hierarchy.) Call
the edges in $\partial r$ _external edges_ ; all other edges are _internal_.
An internal vertex is called a _boundary vertex_ if it is adjacent to $r$. An
edge is said to be _special_ if both of its endpoints are non-boundary
vertices.

We show two ways to sample a spanning tree on $H[I]$, the graph induced on the
internal vertices, being faithful to the marginals $x_{e}$, i.e.,
$\mathbb{P}_{T}(e\in T)=x_{e}$ for all $e\in E(H)\setminus\partial r$.
Moreover, we want that for each internal edge, both its endpoints have even
degree in $T$ with constant probability. This property will allow us to lower
the cost of the $O$-join in §6. While both samplers will satisfy this
property, each will do better in certain cases. The MatInt sampler targets
special edges; it allows us to randomly “hand-pick” edges of this form and
enforce that both of its endpoints have degree 2 in the tree. The MaxEnt
sampler, on the other hand, relies on maximizing the randomness of the
spanning tree sampled (subject to being faithful to the marginals); negative
correlation properties allow us to obtain the evenness property, and in
particular, better probabilities than MatInt for non-special edges, and a
worse probability for the special edges.

Our samplers will depend on the parity of $|V|$: when $|V|$ is even, the
MatInt sampler is the one given by [HN19, Theorem 13], which we describe in
§3.1. They left the case of odd $|V|$ as an open problem, and in Appendix B we
extend their procedure to the odd case.

###  3.1 Samplers for Even $|V(H)|$

Since $H$ is $4$-regular and 4EC and $|V(H)|$ is even, setting a value of
$\nicefrac{{1}}{{4}}=\nicefrac{{x_{e}}}{{2}}$ on each edge gives a solution to
the perfect matching polytope $K_{PM}(H)$ by Fact 2.2.

  1. 1.

Sample a perfect matching $M$ such that $\mathbb{P}(e\in
M)=\nicefrac{{1}}{{4}}=x_{e}/2$ for all $e\in E(H)$.

  2. 2.

(Shift) Define a new fractional solution $y$ (that depends on $M$): set
$y_{e}=1$ for $e\in M$, and $y_{e}=\nicefrac{{1}}{{3}}$ otherwise. We have
$y\in K_{TSP}(H)$ (and hence $y|_{I}\in K_{spT}(H[I])$ by Fact 2.2): indeed,
each vertex has $y(\partial v)=1+3\cdot\nicefrac{{1}}{{3}}=2$ because $M$ is a
perfect matching. Moreover, every proper cut $U$ in $H$ has at least six
edges, so $y(\partial U)\geq|\partial U|\cdot\nicefrac{{1}}{{3}}\geq 2$.
Furthermore,

$\displaystyle\mathbb{E}_{M}[y_{e}]=\nicefrac{{1}}{{4}}\cdot
1+\nicefrac{{3}}{{4}}\cdot\nicefrac{{1}}{{3}}=\nicefrac{{1}}{{2}}=x_{e}.$ (1)

  3. 3.

Sample a spanning tree faithful to the marginals $y$, using one of two
samplers:

    1. (a)

MaxEnt Sampler: Sample from the max-entropy distribution on spanning trees
with marginals $y$.

    2. (b)

MatInt Sampler:

      1. i.

Color the edges of $M$ using $7$ colors such that no edge of $H$ is adjacent
to two edges of $M$ having the same color; e.g., by greedily $7$-coloring the
$6$-regular graph $H/M$. Let $M^{\prime}$ be one of these color classes picked
uniformly at random. Hence, $\mathbb{P}(e\in
M^{\prime})=\nicefrac{{1}}{{28}}$, and $\mathbb{P}(\partial v\cap
M^{\prime}\neq\varnothing)=\nicefrac{{1}}{{7}}$.

      2. ii.

For each edge $e=uv\in M^{\prime}$, let $L_{uv}$ and $R_{uv}$ be the sets of
edges incident at $u$ and $v$ other than $e$. Note that $|L_{uv}|=|R_{uv}|=3$.
Place partition matroid constraints $y(L_{uv})\leq 1$ and $y(R_{uv})\leq 1$ on
each of these sets. Finally, restrict the partition constraints to the
internal edges of $H$; this means some of these constraints are no longer
tight for the solution $y$.

    3. (c)

Given the sub-matching $M^{\prime}\subseteq M$, and the partition matroid
$\mathcal{M}$ on the internal edges defined using $M^{\prime}$, use Lemma 2.3
to sample a tree on $H[V\setminus\\{r\\}]$ (i.e., on the internal vertices and
edges of $H$) with marginals $y_{e}$, subject to this partition matroid
$\mathcal{M}$.

Conditioned on the matching $M$, we have $\mathbb{P}(e\in T\mid M)=y_{e}$; now
using (1), we have $\mathbb{P}(e\in T)=x_{e}$ for all $e\in(E\setminus\partial
r)$.

Figure 1: The matching $M$ consists of all highlighted edges (both brown and
green), one possible choice of $M^{\prime}$ has edges $\\{a,c\\}$ highlighted
in brown, and the constraints are placed on the edges adjacent to those in
$M^{\prime}$ (marked in gray).

###  3.2 Correlation Properties of Samplers

Let $T$ be a tree sampled using either the MatInt or the MaxEnt sampler. The
following claims will be used to prove the evenness property in §5. Each table
gives lower bounds on the corresponding probabilities for each sampler. The
proofs for $|V(H)|$ odd are in Appendix B.

######  Lemma 3.1.

If $f,g$ are internal edges incident to a vertex $v$, then

Probability Statement | MatInt | MaxEnt
---|---|---
$\mathbb{P}(|T\cap\\{f,g\\}|=2)$ | $\nicefrac{{1}}{{9}}$ | $\nicefrac{{1}}{{9}}$
$\mathbb{P}(T\cap\\{f,g\\}=\\{f\\})$ | $\nicefrac{{1}}{{9}}$ | $\nicefrac{{12}}{{72}}$

######  Lemma 3.2.

If edges $e,f,g,h$ incident to a vertex $v$ are all internal, then

Probability Statement | MatInt | MaxEnt
---|---|---
$\mathbb{P}(|T\cap\\{e,f,g,h\\}|=2)$ | $\nicefrac{{2}}{{21}}$ | $\nicefrac{{8}}{{27}}$
$\mathbb{P}(|T\cap\\{e,f\\}|=|T\cap\\{g,h\\}|=1)$ | $\nicefrac{{4}}{{63}}$ | $\nicefrac{{16}}{{81}}$

######  Lemma 3.3.

For an internal edge $e=uv$:

  * (a)

if both endpoints are non-boundary vertices, then

Probability Statement | MatInt | MaxEnt
---|---|---
$\mathbb{P}(|\partial_{T}(u)|=|\partial_{T}(v)|=2)$ | $\nicefrac{{1}}{{36}}$ | $\nicefrac{{128}}{{6561}}$
  * (b)

if both $u,v$ are boundary vertices, then

Probability Statement | MatInt | MaxEnt
---|---|---
$\mathbb{P}($exactly one of $u,v$ has odd degree in $T)$ | $\nicefrac{{1}}{{9}}$ | $\nicefrac{{5}}{{18}}$

####  3.2.1 Correlation Properties: $|V(H)|$ even

We now prove the correlation properties for the even case: the numerical
bounds for the even case are better than those claimed above (which will be
dictated by the proofs of the odd case; see Appendix B).

###### Proof of Lemma 3.1, Even Case.

To prove $\mathbb{P}(|T\cap\\{f,g\\}|=2)\geq\nicefrac{{1}}{{9}}$, we need only
knowledge of the marginals and not the specific sampler. If one of $f,g$ lies
in $M$ (which happens w.p. $\nicefrac{{1}}{{2}}$), then its $y$-value equals
$1$ and it belongs to $T$ w.p. $1$, and the other edge is chosen w.p.
$\nicefrac{{1}}{{3}}$, making the unconditional probability
$\nicefrac{{1}}{{2}}\cdot\nicefrac{{1}}{{3}}=\nicefrac{{1}}{{6}}\geq\nicefrac{{1}}{{9}}$.
Similarly, conditioned on $f$ lying in $M$ and hence belonging to $T$, edge
$g$ is not chosen w.p. $1-y_{e}=\nicefrac{{2}}{{3}}$, so
$\mathbb{P}(T\cap\\{f,g\\}=\\{f\\})\geq\nicefrac{{1}}{{4}}\cdot\nicefrac{{2}}{{3}}=\nicefrac{{1}}{{6}}\geq\nicefrac{{1}}{{9}}$.

_The MaxEnt claim: _ It remains to show that
$\mathbb{P}(T\cap\\{f,g\\}=\\{f\\})\geq\nicefrac{{12}}{{72}}$. Conditioned on
$f\in M$, we have $g\not\in T$ w.p. $\nicefrac{{2}}{{3}}$. Now condition on
neither $f$ nor $g$ in $M$ (happens w.p. $\nicefrac{{1}}{{2}}$). By Theorem
2.8,

$\nicefrac{{1}}{{3}}\leq\mathbb{E}[f\in T\mid g\not\in T]$

By Theorem 2.9, $\mathbb{P}(f\in T\mid g\not\in T)\geq\nicefrac{{1}}{{3}}$, so
$\mathbb{P}(f\in T\land g\not\in
T)\geq\nicefrac{{1}}{{3}}\cdot\nicefrac{{2}}{{3}}=\nicefrac{{2}}{{9}}$.
Putting all of this together, we get

$\mathbb{P}(f\in T\land g\not\in
T)\geq\nicefrac{{1}}{{4}}\cdot\nicefrac{{2}}{{3}}+\nicefrac{{1}}{{2}}\cdot\nicefrac{{2}}{{9}}=\nicefrac{{5}}{{18}}\geq\nicefrac{{12}}{{72}}.\qed$

###### Proof of Lemma 3.2, Even Case.

_The MatInt claims:_ Each perfect matching $M$ contains one of these four
edges in $\partial v$. Say that edge is $e$. If $e$ also belongs to
$M^{\prime}$ (w.p. $\nicefrac{{1}}{{7}}$), then $T$ contains exactly one of
$\\{f,g,h\\}$. Since $\nicefrac{{1}}{{7}}\geq\nicefrac{{2}}{{21}}$, this gives
us the first bound in Lemma 3.2. Moreover, the probability of this edge in $T$
belonging to the other pair (in this case, $\\{g,h\\}$) is
$\nicefrac{{2}}{{3}}$. Hence
$\mathbb{P}(|T\cap\\{e,f\\}|=1\land|T\cap\\{g,h\\}|=1)\geq\nicefrac{{2}}{{21}}>\nicefrac{{4}}{{63}}$,
giving us the other bound in Lemma 3.2 for the MatInt sampler.

_The MaxEnt claims:_ For the first bound in Lemma 3.2, we have that one of the
four edges must be in $M$ and have $y$-value 1. W.l.o.g., call that edge $e$.
The other three, $f,g,h$, will be $\nicefrac{{1}}{{3}}$-valued edges. Since
$\mathbb{E}[X_{f,g,h}]=1$, we may apply Theorem 2.9 and obtain a lower bound
of

$\mathbb{P}(X_{f,g,h}=1)\geq
3\cdot\nicefrac{{1}}{{3}}\cdot(\nicefrac{{2}}{{3}})^{2}=\nicefrac{{4}}{{9}}\geq\nicefrac{{8}}{{27}}.$

For the second bound in Lemma 3.2, call $S_{1}=\\{e,f\\}$ and
$S_{2}=\\{g,h\\}$. W.l.o.g., we once again label $e\in M$. Then,
$\mathbb{P}(f\not\in T)=\nicefrac{{2}}{{3}}$. So for $S_{2}$, we condition on
$f\not\in T$. Then by Theorem 2.8,

$\nicefrac{{2}}{{3}}\leq\mathbb{E}[X_{S_{2}}\mid f\not\in
T]\leq\nicefrac{{2}}{{3}}+\nicefrac{{1}}{{3}}=1.$

Hence, we use Theorem 2.9 again and obtain $\mathbb{P}(X_{S_{2}}=1\mid
f\not\in T)\geq
2\cdot\nicefrac{{1}}{{3}}\cdot\nicefrac{{2}}{{3}}=\nicefrac{{4}}{{9}}$. In
total, we obtain

$\mathbb{P}(|T\cap\\{e,f\\}|=|T\cap\\{g,h\\}|=1)\geq\nicefrac{{2}}{{3}}\cdot\nicefrac{{4}}{{9}}=\nicefrac{{8}}{{27}}\geq\nicefrac{{16}}{{81}}.\qed$

###### Proof of Lemma 3.3a, Even Case.

_The MatInt claims:_ The event happens when $e\in M^{\prime}$, which happens
w.p. $\nicefrac{{1}}{{28}}$, which is at least $\nicefrac{{1}}{{36}}$.

_The MaxEnt claims:_ Condition on $e\in M$. Let $S_{1}=\partial(u)\setminus e$
and $S_{2}=\partial(v)\setminus e$. Denote $S_{1}=\\{a,b,c\\}$. Lower bound
$\mathbb{P}(|S_{1}\cap T|=1)$ using Theorem 2.9: $\mathbb{E}[|S_{1}\cap
T|]=3\cdot\nicefrac{{1}}{{3}}=1$, so $\mathbb{P}(|S_{1}\cap T|=1)\geq
3\cdot\nicefrac{{1}}{{3}}\cdot\left(\nicefrac{{2}}{{3}}\right)^{2/3}=\nicefrac{{4}}{{9}}.$
Consider the distribution over the edges in $S_{2}$ conditioned on $a\in T$;
this distribution is also SR. By Theorem 2.8,
$\nicefrac{{1}}{{3}}\leq\mathbb{E}[X_{S_{2}}\mid X_{a}=1]\leq 1.$ Applying
Theorem 2.8 twice more,

$\nicefrac{{1}}{{3}}\leq\mathbb{E}[X_{S_{2}}\mid X_{a}=1,X_{b,c}=0]\leq
1+\nicefrac{{1}}{{3}}+\nicefrac{{1}}{{3}}=\nicefrac{{5}}{{3}}.$

By Theorem 2.9, $\mathbb{P}(X_{S_{2}}=1\mid X_{a}=1,X_{b,c}=0)\geq
3\cdot\nicefrac{{1}}{{9}}\cdot\left(\nicefrac{{8}}{{9}}\right)^{2}=\nicefrac{{64}}{{243}}$.
Using symmetry, we obtain $\mathbb{P}(X_{S_{2}}=1\land X_{S_{1}}=1\land e\in
M)\geq\nicefrac{{64}}{{243}}\cdot\nicefrac{{4}}{{9}}\cdot\nicefrac{{1}}{{4}}\geq\nicefrac{{128}}{{6561}}.$
∎

###### Proof of Lemma 3.3b, Even Case.

_The MatInt claims:_ For part (b), suppose $e\in M$ (w.p.
$\nicefrac{{1}}{{4}}$), then each of $u,v$ have two other internal edges, each
with $y$-value $\nicefrac{{1}}{{3}}$. Let us say the good cases are when
exactly one of these four is chosen; exactly one of $u,v$ has degree $2$ and
the other has degree $1$ in these cases. We cannot choose zero of these four
edges, because of the connectivity of $T$, so all bad cases choose at least
two of these four. Given the $y$-values of $\nicefrac{{1}}{{3}}$ on all four
edges, the expected number of these edges chosen are $\nicefrac{{4}}{{3}}$, so
the the probability of a bad case at most $\nicefrac{{1}}{{3}}$. This means
that with probability at least
$\nicefrac{{1}}{{4}}\cdot(1-\nicefrac{{1}}{{3}})=\nicefrac{{1}}{{6}}$, exactly
one of $u,v$ has odd degree in $T$. Since
$\nicefrac{{1}}{{6}}\geq\nicefrac{{1}}{{9}}$, we have proven (b).

_The MaxEnt claims:_ Observe that the edge $e$ will always contribute either:
0 to both the degree of $u$ in $T$ and the degree of $v$ in $T$ OR 1 to both
of these degrees. Let $a,b$ be the two internal edges incident to $u$ and
$c,d$ be the two edges incident to $v$.

  1. 1.

_Case 1: $e\in M$._ This implies $a,b,c,d$ are all
$\nicefrac{{1}}{{3}}$-valued edges, so
$\mathbb{E}[X_{a,b,c,d}]=\nicefrac{{4}}{{3}}$. Note that we must have
$X_{a,b,c,d}\geq 1$. Therefore,
$\mathbb{P}(X_{a,b,c,d}=1)\geq\nicefrac{{2}}{{3}}$.

  2. 2.

_Case 2: $e\not\in M$, exactly two of $a,b,c,d$ are in $M$._ W.l.o.g., say
$a,c\in M$, so $a$ and $c$ are in $T$.
$\mathbb{E}[X_{b,d}]=\nicefrac{{2}}{{3}}$, which implies (by Theorem 2.9) that
$\mathbb{P}(X_{b,d}=1)\geq\nicefrac{{4}}{{9}}$.

  3. 3.

_Case 3: $e\not\in M$, exactly one of $a,b,c,d$ is in $M$._ W.l.o.g., say
$a\in M$, so we have $\mathbb{E}[X_{b,c,d}]=1$. We condition on $e\not\in T$,
which happens w.p. $\nicefrac{{2}}{{3}}$. Since we sample a spanning tree on
the internal vertices, this means that at least one of $c,d$ is in $T$.
W.l.o.g., say $c\in T$. So in order to bound the probability that the internal
parities of $u,v$ are different, equivalently we would like to bound
$\mathbb{P}(X_{b,d}=1\mid e\not\in T)$. Since
$\nicefrac{{2}}{{3}}\leq\mathbb{E}[X_{b,d}\mid e\not\in
T]\leq\nicefrac{{2}}{{3}}+\nicefrac{{1}}{{3}}$, Theorem 2.9 implies that
$\mathbb{P}(X_{b,d}=1\mid e\not\in T)\geq\nicefrac{{4}}{{9}}$. So removing the
conditioning on $e\not\in T$ gives a lower bound of
$\nicefrac{{2}}{{3}}\cdot\nicefrac{{4}}{{9}}=\nicefrac{{8}}{{27}}$.

Taking the minimum of the bounds $\nicefrac{{2}}{{3}},\nicefrac{{4}}{{9}}$,
and $\nicefrac{{8}}{{27}}$ in the three cases gives

$\mathbb{P}(\text{exactly one of }u,v\text{ has odd degree in
}T)\geq\nicefrac{{8}}{{27}}\geq\nicefrac{{5}}{{18}}.\qed$

##  4 Sampling Algorithm for General Solutions; and Cut Hierarchy

Now that we can sample a spanning tree from a graph with no proper min-cuts,
we introduce the algorithm to sample an $r_{0}$-tree from a 4-regular, 4EC
graph, perhaps with proper min-cuts.

###  4.1 The Algorithm

Assume that the graph $G=(V,E)$ has a set of three special vertices
$\\{r_{0},u_{0},v_{0}\\}$, with each pair $r_{0},u_{0}$ and $r_{0},v_{0}$
having a pair of edges between them. This is without loss of generality (used
in line 18). Define a _double cycle_ to be a cycle graph in which each edge is
replaced by a pair of parallel edges, and call each such pair _partner edges_.

Algorithm 1 Sampling Algorithm for a Half-Integral Solution

1:let $G$ be the support graph of a half-integral solution $x$.

2:let $T=\varnothing$.

3:while there exists a proper tight set of $G$ that is not crossed by another
proper tight set do

4: let $S$ be a minimal such set (and choose $S$ such that $r_{0}\not\in S$).

5: Define $G^{\prime}=G/(V\setminus S)$.

6: if $G^{\prime}$ is a double cycle then

7: Label $S$ a _cycle set_.

8: sample a random edge from each set of partner edges in $G[S]$; add these
edges to $T$.

9: else // $G^{\prime}$ has no proper min-cuts (Claim 4.2).

10: Label $S$ a _degree set_.

11: if $G^{\prime}=K_{5}$ then

12: sample a random path on $G[S]$

13: else

14: W.p. $\lambda$, let $\mu$ be the MaxEnt distribution over $E(S)$

15: W.p. $1-\lambda$, let $\mu$ be the MatInt distribution.

16: sample a spanning tree on $G[S]$ from $\mu$ and add its edges to $T$.

17: let $G=G/S$

18:Due to $r_{0},u_{0},v_{0}$, at this point $G$ is a double cycle (Claim
4.1). Sample one edge between each pair of adjacent vertices in $G$.

The sampling algorithm appears as Algorithm 1, and is very similar to that in
[KKO20a]: they refer to the sets in line 4 as critical sets. Since $G$ is a
4-regular, 4EC graph at every stage of the algorithm, if $|S|=2$ or 3, then
$S$ must be a cycle set, whereas if $|S|\geq 4$, then $S$ may be a degree or
cycle set. The following two claims are proved in Appendix A.1, and show that
Algorithm 1 is well-defined.

######  Claim 4.1.

The graph remaining at the end of the algorithm (line 18) is a double cycle.

######  Claim 4.2.

In every iteration in Algorithm 1, $G^{\prime}$ is either a double cycle or a
graph with no proper min-cuts.

We will prove the following theorem in §6. This in turn gives Theorem 1.1.

######  Theorem 4.3.

Let $T$ be the $r_{0}$-tree chosen from Algorithm 1, and $O$ be the set of odd
degree vertices in $T$. The expected cost of the minimum cost $O$-join for $T$
is at most $(\nicefrac{{1}}{{2}}-\varepsilon)\cdot c(x)$.

###  4.2 The Cut Hierarchy

Recall our ultimate goal is to create a low cost, feasible solution in the
$O$-join polytope, where $O$ is the set of odd degree vertices in our sampled
tree $T$. We start with the fractional solution $z=x/2$ and then reduce the
$z_{e}$ value of some edges. In the process, we may violate some constraints
corresponding to min-cuts. To fix these cuts, we need a complete description
of the min-cuts of a graph. This is achieved by the implicit hierarchy of
critical sets that Algorithm 1 induces.

The hierarchy is given by a rooted tree
$\mathcal{T}=(V_{\mathcal{T}},E_{\mathcal{T}})$.222Since there are several
graphs under consideration, the vertex set of $G$ is called $V_{G}$. Moreover,
for clarity, we refer to elements of $V_{G}$ as vertices, and elements of
$V_{\mathcal{T}}$ as nodes. The vertex set $V_{\mathcal{T}}$ corresponds to
all critical sets found by the algorithm, along with a root node and leaf
nodes representing the vertices in $V_{G}\setminus\\{r_{0}\\}$. If $S$ is a
critical set, we label the node in $V_{\mathcal{T}}$ with $S$, where we view
$S\subseteq V_{G}$ and not $V_{G^{\prime}}$. The root node is labelled
$V_{G}\setminus\\{r_{0}\\}$ and each leaf nodes is labelled by the vertex in
$V_{G}\setminus\\{r_{0}\\}$ corresponding to it. Now we define the edge set
$E_{\mathcal{T}}$. A node $S$ is a child of $S^{\prime}$ if $S\subset
S^{\prime}$ and $S^{\prime}$ is the first superset of $S$ contracted after $S$
in the algorithm. In addition, the root node is a parent of all nodes
corresponding to critical sets that are not strictly contained in any other
critical set (i.e., the critical sets corresponding to the vertices in the
graph $G$ from line 17 when the while loop terminates). Finally, each leaf
node is a child of the smallest critical set that contains it (or if no
critical set contains it, is a child of the root node). Thus by construction,
vertex sets labelling the children of a node are a partition of the vertex set
labelling that node. A node in $V_{\mathcal{T}}$ is a _cycle_ or _degree_ node
if the corresponding critical set labelling it is a cycle or degree set,
respectively. We say the root node is a cycle node (since the graph $G$ in
line 18 is a double cycle), and accordingly call $V_{G}\setminus\\{r_{0}\\}$ a
cycle set. (The leaf nodes are not labelled as degree or cycle nodes.)

Figure 2: A portion of the cut hierarchy $\mathcal{T}$ and the local
multigraph $G{\langle\\!\langle S\rangle\\!\rangle}$.

######  Definition 4.4 (Local multigraph).

Let $S\subseteq V_{G}$ be a set labelling a node in $\mathcal{T}$. Define the
_local multigraph_ $G{\langle\\!\langle S\rangle\\!\rangle}$ to be the
following graph: take $G$ and contract the subsets of $V_{G}$ labelling the
children of $S$ in $\mathcal{T}$ down to single vertices and contract
$\bar{S}$ to a single vertex $v_{\bar{S}}$. Remove any self-loops. The vertex
$v_{\bar{S}}$ is called the _external vertex_ ; all other vertices are called
_internal vertices._ An internal vertex is called a _boundary vertex_ if it is
adjacent to the external vertex. The edges in $G{\langle\\!\langle
S\rangle\\!\rangle}\setminus v_{\bar{S}}$ are called _internal edges_. Observe
that $G{\langle\\!\langle S\rangle\\!\rangle}$ is precisely the graph
$G^{\prime}$ in line 5 of Algorithm 1 when $S$ is a critical set, and is a
double cycle when $S=V_{G}\setminus\\{r_{0}\\}$.

Properties of $\mathcal{T}$:

  1. 1.

Let $G$ be a 4-regular, 4EC graph with associated hierarchy $\mathcal{T}$. Let
$S\subseteq V_{G}$ be a set labelling a node in $\mathcal{T}$. If $S$ is a
degree node in $\mathcal{T}$, then $G{\langle\\!\langle S\rangle\\!\rangle}$
has at least five vertices and no proper min-cuts, and hence every proper cut
in $G{\langle\\!\langle S\rangle\\!\rangle}$ has at least 6 edges. If $S$ is a
cycle node in $\mathcal{T}$, then $G{\langle\\!\langle S\rangle\\!\rangle}$ is
exactly a double cycle.

These follow from Claim 4.2 and the equivalence between $G^{\prime}$ and
$G{\langle\\!\langle S\rangle\\!\rangle}$.

  2. 2.

Algorithm 1 can be restated as follows: For each non-leaf and non-root node
$S$ in $\mathcal{T}$, sample a random path on $G{\langle\\!\langle
S\rangle\\!\rangle}\setminus v_{\bar{S}}$ if it is a double cycle or $K_{5}$,
and otherwise use the MaxEnt or MatInt samplers w.p. $\lambda$ and
$1-\lambda$, respectively, on $G{\langle\\!\langle
S\rangle\\!\rangle}\setminus v_{\bar{S}}$. Sample a uniformly random cycle on
the double cycle in line 18.

  3. 3.

For a degree set $S$, the graph $G{\langle\\!\langle S\rangle\\!\rangle}$
having no proper min-cuts implies that it has no parallel edges. In
particular, no vertex has parallel edges to the external vertex in
$G{\langle\\!\langle S\rangle\\!\rangle}$. Hence we get the following:

######  Corollary 4.5.

For a set $S$ labeling a non-leaf node in $\mathcal{T}$ and any internal
vertex $v\in G{\langle\\!\langle S\rangle\\!\rangle}$: if $S$ is a cycle set
then $|\partial v\cap\partial S|\in\\{0,2\\}$, and if $S$ is a degree set then
$|\partial v\cap\partial S|\in\\{0,1\\}$.

Finally, we show how the hierarchy $\mathcal{T}$ allows us to characterize the
min-cut structure of $G$. The cactus representation of min-cuts ([FF09]) is a
compact representation of the min-cuts of a graph, and it can be constructed
from the cut hierarchy; we defer the details to Appendix A.2. In turn we
obtain the following complete characterization of the min-cuts of $G$ in terms
of local multigraphs.

######  Claim 4.6.

Any min-cut in $G$ is either (a) $\partial S$ for some node $S$ in
$\mathcal{T}$, or (b) $\partial X$ where $X$ is obtained as follows: for some
cycle set $S$ in $\mathcal{T}$, $X$ is the union of vertices corresponding to
some contiguous segment of the cycle $G{\langle\\!\langle
S\rangle\\!\rangle}$.

##  5 Analysis Part I: The Even-at-Last Property

The proof of Theorem 4.3 proceeds in two parts:

  * (1)

In this section, we show that each edge $e$ is “even-at-last” with constant
probability. (This is an extension of the property that both of its endpoints
have even degree.)

  * (2)

Then we construct the fractional $O$-join. As always, $z=x/2$ is a feasible
join, but we show how to save a constant fraction of the LP value for an edge
when it is even-at-last. This savings causes other cuts to be deficient, so
other edges _raise_ their $z$ values in response. However, a charging argument
shows that the $z$-value for an edge does decrease by a constant factor, in
expectation. This argument appears in §6.

To address part (1), let us define a notion of evenness for every edge in $G$.
In the case where $G$ has no proper min-cuts, we called an edge _even_ if both
of its endpoints were even in $T$. Now, the general definition of evenness
will depend on where an edge belongs in the hierarchy $\mathcal{T}$.

######  Definition 5.1.

We say an edge $e\in E(G)$ is _settled_ at $S$ if $S$ is the (unique) set such
that $e$ is an internal edge of $G{\langle\\!\langle S\rangle\\!\rangle}$;
call $S$ the _last set_ of $e$. If $S$ is a degree or cycle set, we call $e$ a
_degree edge_ or _cycle edge_ , respectively.

######  Definition 5.2 (Even-at-Last).

Let $S$ be the last set of $e$, and $T{\langle\\!\langle S\rangle\\!\rangle}$
be the restriction of $T$ to $G{\langle\\!\langle S\rangle\\!\rangle}$.

  1. 1.

A degree edge $e$ is called _even-at-last (EAL)_ if both of its endpoints have
even degree in $T{\langle\\!\langle S\rangle\\!\rangle}$.

  2. 2.

For a cycle edge $e=uv$, the graph $G{\langle\\!\langle
S\rangle\\!\rangle}\setminus\\{v_{\bar{S}}\\}$ is a chain of vertices
$v_{\ell},\ldots,u,v,\ldots,v_{r}$, with consecutive vertices connected by two
parallel edges. Let $C:=\\{v_{\ell},\ldots,u\\}$, and
$C^{\prime}:=\\{v,\ldots,v_{r}\\}$ be the partition of this chain. The cuts
$\partial C$ and $\partial C^{\prime}$ are called the _canonical cuts_ for
$e$. Cycle edge $e$ is called _even-at-last (EAL)_ if both canonical cuts are
crossed an even number of times by $T{\langle\\!\langle S\rangle\\!\rangle}$;
in other words, if there is exactly one edge in $T{\langle\\!\langle
S\rangle\\!\rangle}$ from each of the two pairs of external partner edges
leaving $v_{\ell}$ and $v_{r}$.

Informally, a degree edge is EAL in the general case if it is even in the tree
at the level at which it is settled. Also note that _cycle_ edges settled at
the same (cycle) set are either all EAL or none are EAL.

######  Definition 5.3 (Special and Half-Special Edges).

Let $e$ be settled at a _degree_ set $S$. We say that $e$ is _special_ if both
of its endpoints are non-boundary vertices in $G\langle\\!\langle
S\rangle\\!\rangle$ and _half-special_ if exactly one of its endpoints is a
boundary vertex in $G\langle\\!\langle S\rangle\\!\rangle$.

We now prove a key property used in §6 to reduce the $z$-values of edges in
the fractional $O$-join.

######  Theorem 5.4 (The Even-at-Last Property).

The table below gives lower bounds on the probability that special, half-
special, and all other types of degree edges are EAL in each of the two
samplers.

| special | half-special | other degree edges
---|---|---|---
MatInt | $\nicefrac{{1}}{{36}}$ | $\nicefrac{{1}}{{21}}$ | $\nicefrac{{1}}{{18}}$
MaxEnt | $\nicefrac{{128}}{{6561}}$ | $\nicefrac{{4}}{{27}}$ | $\nicefrac{{1}}{{12}}$

Moreover, a cycle edge is EAL w.p. at least
$\lambda\cdot\nicefrac{{1}}{{12}}+(1-\lambda)\cdot\nicefrac{{1}}{{18}}$.

###### Proof.

Let $e$ be settled at $S$. Let $T_{S}$ be the spanning tree sampled on the
internal vertices of $G{\langle\\!\langle S\rangle\\!\rangle}$ (in the
notation of Algorithm 1, the spanning tree sampled on $G[S]$).

First, assume that $S$ is a degree set:

  1. 1.

If none of the endpoints of $e$ are boundary vertices in $G{\langle\\!\langle
S\rangle\\!\rangle}$ (i.e., $e$ is special), then it is EAL exactly when both
its endpoints have even degree in $T_{S}$. By Lemma 3.3(a), this happens w.p.
$\nicefrac{{1}}{{36}}$ for the MatInt sampler and w.p.
$\nicefrac{{128}}{{6561}}$ for the MaxEnt sampler.

  2. 2.

Now suppose that $e$ is half-special, so that exactly one of the endpoints of
$e=uv$ (say $u$) is a boundary vertex in $G{\langle\\!\langle
S\rangle\\!\rangle}$, with edge $f$ incident to $u$ leaving $S$. By Lemma 3.2,
the other endpoint $v$ is even in $T_{S}$ w.p. $\nicefrac{{2}}{{21}}$ for the
MatInt sampler and $\nicefrac{{8}}{{27}}$ for the MaxEnt sampler. Moreover,
the edge $f$ is chosen at a higher level than $S$ and is therefore independent
of $T_{S}$, and hence can make the degree of $u$ even w.p.
$\nicefrac{{1}}{{2}}$. Thus $e$ is EAL w.p. $\nicefrac{{1}}{{21}}$ for the
MatInt sampler and $\nicefrac{{4}}{{27}}$ for the MaxEnt sampler.

  3. 3.

Suppose both endpoints of $e$ are boundary vertices of $S$, with edges $f,g$
leaving $S$. Let $q_{=}$ be the probability that the degrees of vertices $u,v$
in the tree $T_{S}$ chosen within $S$ have the same parity, and
$q_{\neq}=1-q_{=}$. Now, when $S$ is contracted and we choose a $r_{0}$-tree
$T^{\prime}$ on the graph $G/S$ consistent with the marginals, let $p_{=}$ be
the probability that either both or neither of $f,g$ are chosen in
$T^{\prime}$, and $p_{\neq}=1-p_{=}$. Hence

$\displaystyle\Pr[e\;EAL]=q_{oo}p_{11}+q_{oe}p_{10}+q_{eo}p_{01}+q_{ee}p_{00}=\nicefrac{{1}}{{2}}(p_{=}q_{=}+p_{\neq}q_{\neq}),$
(2)

where $q_{oo},q_{oe},q_{eo}$ and $q_{ee}$ correspond to different parity
combinations of $u$ and $v$ in $T_{S}$ and $p_{00},p_{01},p_{10},p_{11}$
correspond to whether $f$ and $g$ are chosen in $T^{\prime}$. The second
inequality follows from Claim D.1 applied to the random $r_{0}$-tree
$T^{\prime}$.

    1. (a)

If $f,g$ are settled at different levels, then they are independent. This
gives $p_{=}=p_{\neq}=\nicefrac{{1}}{{2}}$, and hence
$\Pr[e\;EAL]=\nicefrac{{1}}{{4}}$ regardless of the sampler.

    2. (b)

If $f,g$ have the same last set which is a degree set, then by Lemma 3.1 each
of the quantities $p_{11},p_{01},p_{10}\geq\nicefrac{{1}}{{9}}$. By Claim D.1,
$p_{00}\geq\nicefrac{{1}}{{9}}$ as well. Hence, (2) gives
$\Pr[e\;EAL]\geq\nicefrac{{1}}{{9}}$.

    3. (c)

If $f,g$ have the same last set which is a cycle set, then first consider the
case where $f,g$ are partners, in which case $p_{\neq}=1$. Now (2) implies
that $\Pr[e\;EAL]=\nicefrac{{q_{\neq}}}{{2}}$, which by Lemma 3.3(b) is
$\geq\nicefrac{{1}}{{2}}\cdot\nicefrac{{1}}{{9}}=\nicefrac{{1}}{{18}}$ in the
MatInt sampler, and
$\nicefrac{{1}}{{2}}\cdot\nicefrac{{5}}{{18}}=\nicefrac{{5}}{{36}}$ in the
MaxEnt sampler.

If $f,g$ are not partners, then they are chosen independently, in which case
again $p_{=}=p_{\neq}=\nicefrac{{1}}{{2}}$, and hence
$\Pr[e\;EAL]=\nicefrac{{1}}{{4}}$.

Next, let $S$ be a cycle set. Let $e=uv$ be an edge inside the cycle, and let
$\\{a,b\\},\\{c,d\\}$ be the four edges crossing $\partial S$. Let $v_{S}$ be
the vertex obtained by contracting down $S$ (whose incident edges are then
$\\{a,b,c,d\\}$). Now in order for $e$ to be EAL, one each of $\\{a,b\\}$ and
$\\{c,d\\}$ must belong to $T$; call this event $\mathcal{E}$. We again
consider cases based on where these edges are settled. Let node $P$ be the
parent of node $S$, and let $v_{S}$ be the vertex in $G{\langle\\!\langle
P\rangle\\!\rangle}$ obtained from contracting $S$.

  1. 1.

If all four edges are settled at $P$, and $P$ is a degree set, then Lemma 3.2
says that for the MatInt sampler, we have
$\Pr[\mathcal{E}]\geq\nicefrac{{4}}{{63}}$. In contrast, the MaxEnt sampler
gives us $\Pr[\mathcal{E}]\geq\nicefrac{{16}}{{81}}$.

  2. 2.

If all four edges are settled at $P$, and $P$ is a cycle set, then no matter
how these four edges are distributed, $\Pr[\mathcal{E}]\geq\frac{1}{2}$.

  3. 3.

If three of them $\\{a,b,c\\}$ are settled at $P$, and the fourth (say $d$) at
a higher level, then since $P$ has a vertex $v_{S}$ with a single edge leaving
it, $P$ must be a degree set. Now exactly one of $\\{a,b\\}$ is chosen in $T$
w.p. at least $\nicefrac{{1}}{{9}}$ in the MatInt sampler and
$\nicefrac{{12}}{{72}}$ in the MaxEnt sampler, by Lemma 3.1. And since $d$ is
independently picked at a different level, exactly one of $\\{c,d\\}$ is
chosen in $T$ w.p. $\nicefrac{{1}}{{2}}$, giving an overall probability of
$\nicefrac{{1}}{{18}}$ in the MatInt sampler and $\nicefrac{{1}}{{12}}$ in the
MaxEnt sampler.

  4. 4.

Finally, if only two edges are settled at $P$, and two others go to higher
levels, then $P$ is a cycle set by Corollary 4.5. In this case, exactly one of
the two edges that are settled in $P$ is chosen. Now we want a specific one of
the edges going to a higher level to be chosen into $T$ (and the other to not
be chosen), which in the worst case happens w.p. at least
$\nicefrac{{1}}{{9}}$, due to Lemma 3.1.

∎

##  6 Analysis Part II: The $O$-Join and Charging

To prove Theorem 4.3 and thereby finish the proof, we construct an $O$-join
for the random tree $T$, and bound its expected cost via a charging argument.
The structure here is similar to [KKO20a]; however, we use a flow-based
argument to perform the charging instead of the naive one, and also use our
stronger notion of evenness (EAL).

Let $O$ denote the (random set of) odd-degree vertices in $T$. The dominant of
the $O$-join polytope $K_{join}(G,O)$ is given by

$x(\partial S)\geq 1\qquad\qquad\forall S\subseteq V,|S\cap O|\text{ odd}.$

This polytope is integral, so it suffices to exhibit a fractional $O$-join
solution $z\in K_{join}(G,O)$, with low expected cost. (The expectation is
taken over $O$.) Note that $|S\cap O|\text{ odd}$ if and only if $|\partial
S\cap T|\text{ odd}$.

Now Theorem 4.3 follows from the claim below, which we will prove in this
section.

######  Lemma 6.1.

There is an $\varepsilon>0$ such that if the $r_{0}$-tree $T$ is sampled using
the procedure described in Algorithm 1, and $O$ is the set of odd-degree
vertices in $T$, then there is a fractional solution $z\in K_{join}(G,O)$
where $\mathbb{E}[z_{e}]\leq(\nicefrac{{1}}{{2}}-\varepsilon)x_{e}$ for all
edges $e\in E(G)$.

###  6.1 Construction of the Fractional $O$-join

The construction of the fractional $O$-join $z$ goes as follows: We start with
the solution $z=\nicefrac{{x}}{{2}}$. Notice that $z(\partial S)\geq 1$ is a
tight constraint in this initial solution when $S$ is a min-cut. Now we
describe how to reduce the $z_{e}$ values.

Define

$p_{sp}^{MI}\coloneqq\nicefrac{{1}}{{36}},p_{hs}^{MI}\coloneqq\nicefrac{{1}}{{21}},p^{MI}\coloneqq\nicefrac{{1}}{{18}},p_{sp}^{ME}\coloneqq\nicefrac{{128}}{{6561}},p^{ME}\coloneqq\nicefrac{{1}}{{12}}$
$p_{sp}\coloneqq\lambda
p_{sp}^{ME}+(1-\lambda)p_{sp}^{MI},p_{hs}\coloneqq\lambda
p^{ME}+(1-\lambda)p_{hs}^{MI},p\coloneqq\lambda p^{ME}+(1-\lambda)p^{MI}.$

Let $p_{sp}(e),p_{hs}(e),$ and $p_{d}(e)$ denote the probabilities that $e$ is
EAL if $e$ is a special degree edge, half-special degree edge, or other degree
edge, respectively. Let $p_{c}(e)$ denote the probability that a cycle edge
$e$ is EAL. By Theorem 5.4,

$p_{sp}(e)\geq p_{sp},\ p_{hs}(e)\geq p_{hs},\ p_{d}(e)\geq p,\ p_{c}(e)\geq
p.$

(We do not distinguish the half-special case in the MaxEnt sampler, as the
half-special bound of $\nicefrac{{4}}{{27}}$ in Theorem 5.4 is greater than
$p^{ME}$.) Call an edge $e$ a _$K_{5}$ degree edge_ if $e$ is settled at a
degree set $S$ where $G{\langle\\!\langle S\rangle\\!\rangle}$ is a $K_{5}$.
By the inequalities above, the random variables below are well-defined.

  1. 1.

Define a Bernoulli random variable for each edge $e$:

    1. (a)

If $e$ is a special degree edge, set
$B_{e}\sim\operatorname{Ber}(\nicefrac{{p_{sp}}}{{p_{sp}(e)}})$.

    2. (b)

If $e$ is a half-special degree edge, set
$B_{e}\sim\operatorname{Ber}(\nicefrac{{p_{hs}}}{{p_{hs}(e)}})$.

    3. (c)

If $e$ is any other degree edge, set
$B_{e}\sim\operatorname{Ber}(\nicefrac{{p}}{{p_{d}(e)}})$.

    4. (d)

If $e$ is a cycle edge, set
$B_{e}\sim\operatorname{Ber}(\nicefrac{{p}}{{p_{c}(e)}})$. Further, if $e$ and
$f$ are partners, perfectly correlate their coin flips, i.e., set
$B_{e}=B_{f}$.

  2. 2.

If $e$ is EAL _and_ $B_{e}=1$, reduce $z_{e}$ by

    1. (a)

$\tau$ if $e$ is a non-$K_{5}$ degree edge.

    2. (b)

$\gamma$ if $e$ is a $K_{5}$ degree edge.

    3. (c)

$\beta$ if $e$ is a cycle edge.

  3. 3.

We enforce that $\tau\leq\gamma\leq\beta\leq\nicefrac{{1}}{{12}}$, $\beta\geq
2\tau$, and $\beta\geq 2\gamma$. We will optimize $\tau,\gamma,$ and $\beta$
via a linear program later.

The purpose of the Bernoulli coin flips is to flatten the probability that an
edge is reduced down to the lower bound on the probability that it is EAL from
Theorem 5.4:

######  Observation 6.2.

If $e$ is a special, half-special, other degree, or cycle edge, then $z_{e}$
is reduced with probability exactly $p_{sp}$, $p_{hs}$, $p$, or $p$,
respectively.

This reduction scheme may make $z$ infeasible for the $O$-join polytope. We
now discuss how to maintain feasiblity.

###  6.2 Maintaining Feasibility of the Fractional $O$-join via Charging

Suppose $f$ is EAL and that we reduce edge $z_{f}$ (per its coin flip
$B_{f}$). Say $f$ is settled at $S$. If $S$ is a degree set, then the only
min-cuts of $G\langle\\!\langle S\rangle\\!\rangle$ are the degree cuts. So
the only min-cuts that the edge $f$ is part of in $G\langle\\!\langle
S\rangle\\!\rangle$ are the degree cuts of its endpoints, call them $U,V$, in
$G\langle\\!\langle S\rangle\\!\rangle$ ($U$ and $V$ are vertices in
$G\langle\\!\langle S\rangle\\!\rangle$ representing sets $U$ and $V$ in $G$).
But since $|\partial U\cap T|$ and $|\partial V\cap T|$ are both even by
definition of EAL, we need not worry that reducing $z_{f}$ causes $z(\partial
U)\geq 1$ and $z(\partial V)\geq 1$ to be violated. Likewise, if $S$ is a
cycle set, then by definition of EAL all min-cuts $S^{\prime}$ in
$G\langle\\!\langle S\rangle\\!\rangle$ containing $e$ have $|\partial
S^{\prime}\cap T|$ even, so again we need not worry.

Since $f$ is only an internal edge for its last set $S$, the only cuts
$S^{\prime}$ for which the constraint $z(\partial S^{\prime})\geq 1$,
$|\partial S^{\prime}\cap T|$ odd, may be violated as a result of reducing
$z_{f}$ are cuts represented in lower levels of the hierarchy. Specifically,
lef $f$ be an external edge for some $G{\langle\\!\langle X\rangle\\!\rangle}$
(meaning $X$ is lower in the hierarchy $\mathcal{T}$ than $S$) and
$S^{\prime}$ be a min-cut of $G{\langle\\!\langle X\rangle\\!\rangle}$ (either
a degree cut or a canonical cut). By Claim 4.6, cuts of the form $S^{\prime}$
are the only cuts that may be deficient as a result of reducing $z_{f}$. Call
the internal edges of $\partial S^{\prime}$ _lower edges_. When $z_{f}$ is
reduced and $|\partial S^{\prime}\cap T|$ is odd, we must distribute an
increase (charge) over the lower edges totalling the amount by which $z_{f}$
is reduced, so that $z(\partial S^{\prime})=1$. We say these lower edges
receive a _charge_ from $f$. How the charge is distributed will depend on
whether the lower edges are degree edges or cycle edges (see §6.3 and §6.4
below).

We claim that this procedure maintains feasibility of the $O$-join solution
$z$. Indeed, by Claim 4.6, no constraint corresponding to a _min-cut_ in the
$O$-join polytope is violated. Further, by capping the amount an edge can be
reduced at $\nicefrac{{1}}{{4}}-\nicefrac{{1}}{{6}}=\nicefrac{{1}}{{12}}$, we
will ensure that _none_ of the constraints are violated, since every other cut
has at least 6 edges.

To prove Lemma 6.1, we will lower bound the expected decrease to $z_{e}$,
using different strategies for charging $e$ when $e$ is a cycle edge versus a
degree edge. In particular, when $e$ is a cycle edge, we distribute charge
from an external edge evenly between $e$ and its partner. When $e$ is a degree
edge, charge will be distributed according to a maximum-flow solution.

###  6.3 Charging of Cycle Edges

We now analyze the expected net decrease for each edge, starting with cycle
edges. The expected decrease for a cycle edge starts off as exactly
$p\cdot\beta$ by Observation 6.2. However, we need to control the amount of
charge the edge receives from edges settled at higher levels. Note that in the
calculations, we assume the worst-case scenario that such edges settled at
higher levels are reduced w.p. exactly $p$. The special/half-special edges are
reduced with lower probability, which is only better for us because the
expected amount of charge will be lower in these cases. Note also that
throughout the calculations we may assume that an edge settled at a higher
level is a cycle edge. This will follow from the assumption that $\beta\geq
2\tau,2\gamma$.

Consider a cycle edge $e$ that is settled at set $S$. Let its partner on the
cycle be $e^{\prime}$, and let the four external edges for $S$ be $\\{a,b\\}$
(leaving the vertex $u$) and $\\{c,d\\}$ (leaving vertex $v$). When $S$ is
contracted, vertex $v_{S}$ has these four edges $\\{a,b,c,d\\}$ incident to
it. Let $P$ be $S$’s parent node in $\mathcal{T}$. Moreover, let $C$ and
$C^{\prime}$ be the canonical cuts, as in the figure below. We consider the
following cases as in [KKO20a].

Figure 3: Case (i)

Figure 4: Case (ii)

  1. (i)

Two of the four edges incident to $v_{S}$ also leave $P$—and therefore $P$ is
a cycle set by Corollary 4.5. Of the two edges leaving $P$, one must be from
$\\{a,b\\}$ and one from $\\{c,d\\}$. To see this, say both $c$ and $d$
(leaving node $u$) both did not leave $P$. Consider the set of vertices
$S^{\prime}$ which $c$ and $d$ lead to. $S^{\prime}\cup u$ is a proper min cut
which crosses $S$; however, this contradicts the fact that $S$ is a critical
set (namely $S$ is not supposed to be crossed by another proper min cut).

Suppose $\\{a,d\\}$ are the external edges for $P$, and $\\{b,c\\}$ are
internal (and hence partners in this cycle set).

Now, consider the event that $b$ is reduced; the important observation is that
$c$ is also reduced, because both are EAL at the same time and their coins are
perfectly correlated. Not only that, the event that $b$ is reduced implies
that $|\delta(S)\cap T|$ is even. This means that both cuts $C,C^{\prime}$ are
deficient by the same amount and at the same time, due to this event of
reducing $b,c$, and raising $e$ helps both of them. This means the net
expected charge to $e$ is at most

$p\frac{\beta}{2}\big{(}\Pr[C\text{ odd}\mid b\text{ reduced}]+\Pr[C\text{
odd}\mid a\text{ reduced}]+\Pr[C^{\prime}\text{ odd}\mid d\text{
reduced}]\big{)}.$

(Note that there is no term for $c$ here because of the discussion above;
moreover, the $\nicefrac{{\beta}}{{2}}$ term reflects that the charge of
$\beta$ is split between $e,e^{\prime}$.)

Since $a$ and $b$ are settled at different levels, the parity of cut $C$ is
unbiased, even either conditioned on choices within $P$, or else conditioned
on choices outside $P$. The same holds for the parity of $C^{\prime}$, so each
of the probabilities above is at most $\nicefrac{{1}}{{2}}$, making the net
expected decrease

$\displaystyle p(\beta-\nicefrac{{\beta}}{{2}}\cdot
3\cdot\nicefrac{{1}}{{2}})=\boxed{p\nicefrac{{\beta}}{{4}}}.$ (3)

  2. (ii)

Only one of the edges incident to $v_{S}$, say edge $a$, is external for $P$.
By Corollary 4.5, $P$ is a degree set, and in the worst case, a $K_{5}$ degree
set since $\gamma\geq\tau$. The charge is maximized when $a$ is a cycle edge,
in which case the expected charge to $e$ is at most

$p\big{(}\nicefrac{{\beta}}{{2}}\Pr[C\text{ odd}\mid a\text{
reduced}]+\nicefrac{{\gamma}}{{2}}\Pr[C\text{ odd}\mid b\text{
reduced}]+2\cdot\nicefrac{{\gamma}}{{2}}\big{)}.$

Since $a$ and $b$ are settled at different levels, the parity of the cut $C$
is unbiased, either conditioning on the process inside $P$ or else outside
$P$, which makes the above expression
$p(\nicefrac{{\beta}}{{4}}+\nicefrac{{5\gamma}}{{4}})$, and the net expected
decrease to be

$\displaystyle
p(\beta-\nicefrac{{\beta}}{{4}}-\nicefrac{{5\gamma}}{{4}})=\boxed{p(\nicefrac{{3\beta}}{{4}}-\nicefrac{{5\gamma}}{{4}})}.$
(4)

Figure 5: Case (iii)

Figure 6: Case (iv)

  3. (iii)

All four of the edges are internal to $P$, which is a cycle set. The partners
must now be one edge from each of the two pairs $\\{a,b\\}$ and
$\\{c,d\\}$—let’s say $\\{a,d\\}$ and $\\{b,c\\}$ are partners (using an
argument similar to that in (i)). The cut $C$ is odd in $S$ if and only if
$C^{\prime}$ is odd; indeed, $C$ is odd means we choose both or neither of
$\\{a,b\\}$, and since $\\{c,d\\}$ are the partners of $\\{a,b\\}$, we choose
both or neither of them. Hence, increasing $e$ fixes both cuts at the same
time, similar to the argument in (i), so we focus only on the increase due to
cut $C$. Since $a$ and $b$ belong to different pairs and are chosen
independently into the tree $T$, $\Pr[C\text{ odd}]=\nicefrac{{1}}{{2}}$. This
means both $a$ and $b$ can give a expected charge of
$p(\nicefrac{{\beta}}{{2}})\cdot\nicefrac{{1}}{{2}}$ to $e$. The net expected
decrease is
$p(\beta-2\cdot\nicefrac{{\beta}}{{2}}\cdot\nicefrac{{1}}{{2}})=p\nicefrac{{\beta}}{{2}}$,
which is no worse than (3).

  4. (iv)

All four of the edges are internal to $P$, and $P$ is a degree set. Note that
$G{\langle\\!\langle P\rangle\\!\rangle}$ cannot be a $K_{5}$ since the vertex
$v_{S}$ has four internal edges incident to it. We simply bound the charge due
to each edge by $\tau/2$, and hence get net expected decrease of

$\displaystyle p(\beta-4\cdot\nicefrac{{\tau}}{{2}})=\boxed{p(\beta-2\tau)},$
(5)

###  6.4 Charging Degree Edges: Max-Flow Formulation

So far we have shown that no cycle edge will receive too much charge. We did
this by considering four different configurations for the external edges of
$S$, and distributing charge evenly between a cycle edge and its partner.
Before showing that no degree edge receives too much charge, we will define a
charging scheme for degree edges that achieves better bounds than distributing
charge uniformly.

Let $G\langle\\!\langle S\rangle\\!\rangle$ be the local multigraph for some
degree set $S$, so $G\langle\\!\langle S\rangle\\!\rangle$ is 4-regular and
has no proper min-cuts. For an external edge $e$, let $u_{e}$ denote the
internal boundary vertex to which $e$ is incident. We create a bipartite graph
$H=(B,F,E)$ from $G\langle\\!\langle S\rangle\\!\rangle$ as follows. The
vertices of $B$ are labelled with the external edges of $G\langle\\!\langle
S\rangle\\!\rangle$. The vertices of $F$ are labelled with the internal edges
of $G\langle\\!\langle S\rangle\\!\rangle$. So $|B|=4$. Place an edge between
$e\in B$ and $f\in F$ in the edge set $E$ if $e$ and $f$ share $u_{e}$ as an
endpoint. Set $b_{e}=1$ for all $e\in B$. We call $H$ the _bipartization_ of
$G\langle\\!\langle S\rangle\\!\rangle$.

The following lemma follows from the Max-Flow Min-Cut theorem:

######  Lemma 6.3.

Given a bipartite graph $G=(B,F,E)$ with positive integers $b_{u}$ for each
$u\in B$, and $c\geq 0$, there exists $x:B\times F\rightarrow\mathbb{R}_{+}$
satisfying

$\displaystyle\textstyle\sum_{f\in\partial u}x(u,f)$
$\displaystyle=b_{u}\text{ for all }u\in B,$ (6)
$\displaystyle\textstyle\sum_{u\in\partial f}x(u,f)$ $\displaystyle\leq
c\text{ for all }f\in F$ (7)

if and only if

$\textstyle|N(R)|\geq\frac{b(R)}{c}\text{ for all }R\subseteq B$ (8)

where $b(R)=\sum_{u\in R}b_{u}$.

Lemma 6.3 now gives the following result, which follows from straightforward
casework.

######  Lemma 6.4.

Let $H=(B,F,E)$ be the bipartization of $G\langle\\!\langle
S\rangle\\!\rangle$, as described above. If $G\langle\\!\langle
S\rangle\\!\rangle$ is not a $K_{5}$, then the smallest $c$ satisfying (8) is
given by $c=\nicefrac{{1}}{{2}}$. If $G\langle\\!\langle S\rangle\\!\rangle$
is a $K_{5}$, then the smallest $c$ satisfying (8) is given by
$c=\nicefrac{{2}}{{3}}$.

The fact that we may achieve a value of $c=\nicefrac{{1}}{{2}}$ instead of
$c=\nicefrac{{2}}{{3}}$ as long as $G\langle\\!\langle S\rangle\\!\rangle$ is
not a $K_{5}$ motivates why we utilize a different sampler for $K_{5}$. In
fact, $c=\nicefrac{{2}}{{3}}$ on $K_{5}$ is achieved by distributing uniform
charge over internal edges.

###  6.5 Charging of non-$K_{5}$ Degree Edges

We now analyze the expected net decrease for degree edges. By Observation 6.2,
the expected decrease for a non-special degree edge starts off as at least
$p_{hs}\cdot\tau$ or $p_{hs}\cdot\gamma$, since $p_{hs}\leq p$. We will
analyze the charge on non-$K_{5}$ degree and $K_{5}$ degree edges separately,
as a different sampler is used when $G{\langle\\!\langle
S\rangle\\!\rangle}=K_{5}$. We begin with the former.

####  6.5.1 Charging of non-special edges

  1. 1.

Case 1: All external edges are non-$K_{5}$ degree edges. Let $x:B\times
F\rightarrow\mathbb{R}_{+}$ be any function satisfying the constraints in
Lemma 6.3 for $c=\nicefrac{{1}}{{2}}$ (by Lemma 6.4 such an $x$ exists, and
can be found efficiently using max-flow min-cut). The charging scheme is as
follows: for each external edge $e$ and boundary vertex $u_{e}$, if the cut
$\delta(u)$ is odd and the edge $e$ is reduced, charge each internal edge $f$
incident to $u_{e}$ by $\tau\cdot x(e,f)$. The constraint (6) ensures that the
charge neutralizes the reduction of $e$ by $\tau$. For any internal edge $f$,
let $\delta(f)$ denote the external edges with which $f$ shares an endpoint,
i.e., the neighbors of $f$ in the bipartization $H=(B,F,E)$. We have

$\displaystyle\mathbb{E}[\text{charge to }f]$
$\displaystyle=\sum_{e\in\delta(f)}\tau\cdot x(e,f)\cdot\mathbb{P}(u_{e}\text{
odd}\wedge e\text{ reduced})$ $\displaystyle\leq\tau\cdot
c\cdot\mathbb{P}(u_{e}\text{ odd}\mid e\text{ reduced})\cdot\mathbb{P}(e\text{
reduced})$ (9)

Using the naive bound that $\mathbb{P}(u_{e}\text{ odd}\mid e\text{
reduced})\leq 1$, we obtain that the the expected decrease is at least
$\boxed{p_{hs}\tau-\frac{\tau}{2}\cdot p.}$

  2. 2.

Case 2: All external edges are $K_{5}$ degree edges. An analogous argument
shows that the expected decrease is at least
$\boxed{p_{hs}\tau-\frac{\gamma}{2}\cdot p.}$

  3. 3.

Case 3: All external edges are cycle edges. We have that
$\mathbb{P}(u_{e}\text{ odd}\mid e\text{ reduced})=\frac{1}{2}$ in this case,
since $f\in T$ is independent of whether $f$ is reduced since $f$ has a
partner edge. So the expected decrease is at least
$\boxed{p_{hs}\tau-\frac{\beta}{2}\cdot\frac{1}{2}\cdot p.}$

  4. 4.

Case 4: The external edges are a combination of non-$K_{5}$ degree edges,
$K_{5}$ degree edges, and cycle edges. In this case, we use an averaging
argument to show that the expected charge is no worse than
$p\cdot\max\\{\frac{\tau}{2},\frac{\gamma}{2},\frac{\beta}{4}\\}.$ See
Appendix C for details.

####  6.5.2 Charging of special edges

These edges are never charged, as their endpoints are both non-boundary. Also,
these cannot be $K_{5}$ degree edges by definition. So the expected decrease
is equal to the expected reduction, which is at least
$\boxed{p_{sp}\tau=\frac{\tau}{36}.}$

###  6.6 Charging of $K_{5}$ Degree Edges

$K_{5}$ degree edges have an initial decrease of exactly $p\gamma$, as they
are neither special nor half-special. We will use the following lemma, whose
proof is straightforward.

######  Lemma 6.5.

Let $G{\langle\\!\langle S\rangle\\!\rangle}=K_{5}$. Let $f$ be an external
edge and $u$ be the boundary vertex that is one of its endpoints. Then

$Pr(u\text{ odd}\mid f\text{ reduced})=\frac{1}{2}.$

We will factor in this probability into the charging of $K_{5}$ degree edges
below.

  1. 1.

All external edges are non-$K_{5}$ degree edges. Since the edge being charged
is a $K_{5}$ edge, Lemma 6.4 gives us a worst-case expected charge of
$p\cdot\frac{2\tau}{3}$. However, factoring in $Pr(u\text{ odd}\mid f\text{
reduced})=\frac{1}{2}$ for every external edge $f$, we have a worst-case
expected charge of $p\cdot\frac{2\tau}{3}\cdot\frac{1}{2}$, which by (9) gives
us an expected net decrease of at least

$\boxed{p\gamma-p\frac{\tau}{3}.}$

  2. 2.

All external edges are $K_{5}$ degree edges. Using similar reasoning as above,
we have a worst-case expected charge of
$p\cdot\frac{2\gamma}{3}\cdot\frac{1}{2}$, which gives us an expected net
decrease of at least

$\boxed{p\gamma-p\frac{\gamma}{3}.}$

  3. 3.

All external edges are cycle edges.  Using the same reasoning as above, we get
an expected net decrease of at least

$\boxed{p\gamma-p\frac{\beta}{3}.}$

  4. 4.

The external edges are a combination of non-$K_{5}$ degree edges, $K_{5}$
degree edges, and cycle edges. An averaging argument as in the previous
section shows that the three cases above are the only possible worst cases.

###  6.7 Setting the Parameters

For fixed $\lambda$, finding the optimal values of $\beta,\gamma,\tau$ can be
done with a linear program. In particular, we maximize the minimum expected
decrease $\delta$, which is the minimum of the boxed expressions in §6.3 and
§6.4. The additional constraints are that $\tau\leq\gamma\leq\beta$,
$\beta\leq\nicefrac{{1}}{{12}}$, $\beta\geq 2\tau$, and $\beta\geq 2\gamma$.
We then optimize over $\lambda$. This gives $\lambda=0.4715$,
$\beta=\nicefrac{{1}}{{12}}$, $\gamma=0.0401$, $\tau=0.0355$, and
$\delta=0.0008475$. We have $\varepsilon=2\delta=0.001695$, proving Theorem
4.3.

## References

  * [AGM+17] Arash Asadpour, Michel X. Goemans, Aleksander Mźdry, Shayan Oveis Gharan, and Amin Saberi.  An o(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem.  Oper. Res., 65(4):1043–1061, August 2017.
  * [BBL09] Julius Borcea, Petter Brändéd, and Thomas M. Liggett.  Negative dependence and the geometry of polynomials.  Journal of the American Mathematical Society, 22(2):521–567, 2009\.
  * [Chr76] Nicos Christofides.  Worst-case analysis of a new heuristic for the travelling salesman problem.  Technical Report 338, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976.
  * [FF09] Tamás Fleiner and András Frank.  A quick proof for the cactus representation of mincuts.  Technical Report Quick-proof No. 2009-03, EGRES, 2009.
  * [HN19] Arash Haddadan and Alantha Newman.  Towards improving Christofides algorithm for half-integer TSP.  In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, pages 56:1–56:12, 2019.
  * [Hoe56] Wassily Hoeffding.  On the distribution of the number of successes in independent trials.  The Annals of Mathematical Statistics, pages 713–721, 1956.
  * [KKO20a] Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan.  An improved approximation algorithm for TSP in the half integral case.  In STOC, pages 28–39. ACM, 2020.
  * [KKO20b] Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan.  A (slightly) improved approximation algorithm for metric TSP.  CoRR, abs/2007.01409, 2020.
  * [KKO21] Anna Karlin, Nathan Klein, and Shayan Oveis Gharan.  A (slightly) improved bound on the integrality gap of the subtour LP for TSP.  CoRR, abs/2105.10043, 2021.
  * [OSS11] Shayan Oveis Gharan, Amin Saberi, and Mohit Singh.  A randomized rounding approach to the traveling salesman problem.  In FOCS, pages 550–559. IEEE Computer Society, 2011.
  * [Ser78] Anatoliy Serdyukov.  O nekotorykh ekstremal’nykh obkhodakh v grafakh.  Upravlyaemye sistemy, 17:76–79, 1978.
  * [SW90] David B. Shmoys and David P. Williamson.  Analyzing the Held-Karp TSP bound: A monotonicity property with application.  Information Processing Letters, 35(6):281–285, 1990.
  * [SWvZ14] Frans Schalekamp, David P. Williamson, and Anke van Zuylen.  2-matchings, the traveling salesman problem, and the subtour LP: A proof of the boyd-carr conjecture.  Math. Oper. Res., 39(2):403–417, 2014.
  * [Wol80] Laurence A. Wolsey.  Heuristic analysis, linear programming and branch and bound.  In Combinatorial Optimization II, volume 13 of Mathematical Programming Studies, pages 121–134. Springer, 1980.

##  Appendix A Details of the Cut Hierarchy Construction

###  A.1 The Algorithm

######  Fact A.1 (Lemma 2 in [FF09]).

Let $k\geq 1$ be an integer, $H=(W,F)$ be a $4$-regular, $4$EC graph in which
there is a proper min-cut, and every proper min-cut is crossed by some proper
min-cut. Then $H$ is a double cycle.

###### Proof of Claim 4.1..

Let $G_{f}$ refer to the graph in the claim, and $G$ refer to the input to the
algorithm.

_Case 1: There is no proper tight set in $G_{f}$._ Let $u$ be the vertex in
$G_{f}$ such that the two edges that between $r_{0}$ and $u_{0}$ in $G$ are
between $r_{0}$ and $u$ in $G_{f}$. Then either $G_{f}$ is a graph on 2
vertices with four parallel edges (i.e., a double cycle on 2 vertices), or
$\\{r_{0},u\\}$ is a tight set in $G_{f}$. In the latter case, since
$\\{r_{0},u\\}$ is not proper, $G_{f}$ is a double cycle with 3 vertices.
_Case 2: There is a proper tight set in $G_{f}$, and every proper tight set is
crossed by another proper tight set._ By Fact A.1, $G_{f}$ is a double cycle.
∎

###### Proof of Claim 4.2..

Let $v_{\bar{S}}$ denote the vertex corresponding to the contraction of
$V\setminus S$ in $G^{\prime}$. Suppose $G^{\prime}$ has a proper min-cut. Let
$S^{\prime}$ be the shore of this min-cut not containing $v_{\bar{S}}$. Then
$S^{\prime}\subset S$. But by minimality of $S$, $S^{\prime}$ is crossed by
another proper tight set. Since this must be true for every proper min-cut
$S^{\prime}$ in $G^{\prime}$, by Fact A.1, $G^{\prime}$ must be a double
cycle. ∎

###  A.2 Cactus Representation of Min-Cuts

See 4.6

To prove the above claim, we recall the cactus representation of min-cuts
(see, for e.g., [FF09], for a full exposition). The key idea to prove Claim
4.6 is that Algorithm 1 implicitly constructs the cactus representation of
min-cuts.

######  Definition A.2.

A _cactus_ is a loopless, 2EC graph in which each edge belongs to exactly one
cycle.

Note that this includes cycles on two vertices, containing exactly two
parallel edges. The min-cuts of a cactus are obtained by cutting any two edges
belonging to the same cycle.

######  Theorem A.3 (Cactus Representation of Min-Cuts, [FF09], Theorem 7).

Let $G$ be a 4-regular, 4EC graph. There is a cactus $C=(U,F)$ and a mapping
$\phi:V\rightarrow U$ so that if $U_{1}$ and $\bar{U_{1}}$ are two shores of a
min-cut in $C$, then $\phi^{-1}(U_{1})$ and $\phi^{-1}(\bar{U_{1}})$ are two
shores of a min-cut in $G$. Further, every min-cut in $G$ can be obtained this
way for some $U_{1}$.

Figure 7: Construction of the cactus $C$ from the hierarchy $\mathcal{T}$ in
the proof of Claim 4.6.

###### Proof sketch of Claim 4.6..

Construct a cactus $C=(U,F)$ as follows. Create a vertex $u_{S}$ in $U$ for
every node $S$ in the hierarchy. If $S$ is a cycle node, make a cycle between
$u_{S}$ and the vertices $u_{T}$ for all nodes $T$ which are children of $S$.
If $S$ is a degree node, include two parallel edges from $u_{S}$ to each
$u_{T}$ for which $T$ is a child of $S$. See Figure 7. All of the terminal
vertices in $U$, except for $u_{V_{G}\setminus r_{0}}$, correspond to all of
the leaf nodes in $\mathcal{T}$, which in turn correspond to all of the
vertices in $V_{G}\setminus\\{r_{0}\\}$. We identify the vertex
$u_{V_{G}\setminus r_{0}}$ in $U$ with the vertex $r_{0}$ in $V_{G}$. In other
words, the mapping $\phi$ in Theorem A.3 can be defined as $\phi(v)=u_{v}$ for
all $v\in V_{G}\setminus r_{0}$, and $\phi(r_{0})=u_{V_{G}\setminus r_{0}}$.

Since the construction of the cactus in the proof of Theorem A.3 given in
[FF09] and the construction of $C$ above are equivalent, $\phi$ satisfies the
conclusions of Theorem A.3. Since the min-cuts of a cactus are obtained by
cutting any two edges belonging to the same cycle, Claim 4.6 follows. ∎

##  Appendix B Samplers for Odd $|V(H)|$

The main change from the case where $V(H)$ is even is that
$x=\nicefrac{{1}}{{2}}\cdot\mathbf{1}$ is not a point in the perfect matching
polytope: in fact, $H$ has no perfect matchings because it has an odd number
of vertices.

To fix this, split the external vertex $r$ into two external vertices
$r_{1},r_{2}$, each incident to some two of the edges in $\partial r$, and
then add two parallel edges between $r_{1},r_{2}$. Call this multigraph
$\widehat{H}$. Again, all vertices and edges between vertices in
$V\setminus\\{r_{1},r_{2}\\}$ are called internal, vertices in
$\\{r_{1},r_{2}\\}$ and edges in $\partial r_{1}\cup\partial r_{2}$ are
external, and internal vertices adjacent to external vertices are boundary
vertices.

######  Fact B.1.

The graph $\widehat{H}$ is also $4$-regular and 4EC; it has an even number of
vertices. However, it contains a single proper min-cut separating the internal
vertices $I:=V\setminus\\{r_{1},r_{2}\\}$ from the two external vertices. Any
perfect matching $M$ of $\widehat{H}$ contains either zero or two edges in
$\partial I$.

The sampling procedure for trees on $H[I]=\widehat{H}[I]$ is conceptually
similar to the one above, but with some crucial changes because of the proper
min-cut.

  1. 1.

Since $\widehat{H}$ is $4$-regular and 4EC, and $|V(\widehat{H})|$ is even,
setting $\nicefrac{{1}}{{4}}=\nicefrac{{x_{e}}}{{2}}$ on each edge gives a
solution $K_{PM}(\widehat{H})$ in the perfect matching polytope. Sample a
perfect matching $M$ such that for each edge $e$, we have $\Pr[e\in
M]=\nicefrac{{1}}{{4}}$. Again define the fractional solution

$y_{e}=\nicefrac{{1}}{{3}}+\mathbf{1}_{(e\in M)}\cdot\nicefrac{{2}}{{3}}.$

This ensures $\mathbb{E}[y]=x$, but $y|_{I}$ may no longer be in the spanning
tree polytope $K_{spT}(\widehat{H}[I])$. Indeed, $y(\partial
I)\in\\{\nicefrac{{4}}{{3}},\nicefrac{{8}}{{3}}\\}$ depending on whether $M$
has zero or two edges crossing the cut, so
$y(E(I))\in\\{|I|-\nicefrac{{2}}{{3}},|I|-\nicefrac{{4}}{{3}}\\}$ and not
$|I|-1$ as required. Hence we cannot directly sample a spanning tree on
$\widehat{H}[I]$, as we did above. We fix this in step 3 below.

  2. 2.

Pick a random induced sub-matching $M^{\prime}$ of $M$, and define partition
matroid constraints on the sets $L_{uv},R_{uv}$ incident on the endpoints of
edges $uv$ in this sub-matching $M^{\prime}$ exactly as in steps 3(b)i and
3(b)ii of the sampling procedure for the even-size case above.

  3. 3.

We now address that $y|_{I}$ is not in the spanning tree polytope by locally
changing the fractional solution as follows:

    1. (a)

(Local Decrease) If $M\cap\partial I=\varnothing$, then
$y(E(I))=|I|-\nicefrac{{2}}{{3}}$ and $y(\partial I)=\nicefrac{{4}}{{3}}$.
Hence $y|_{I}$ is not a solution to $K_{spT}(\widehat{H}[I])$. To fix this,
pick a random edge $e\in\partial I$, pick a random edge $f\in E(I)$ adjacent
to $e$, and reduce the $y$-value of $f$ by $\nicefrac{{1}}{{3}}$ to get
solution $\widehat{y}$. (Note this may reduce either a $1$-edge to
$\nicefrac{{2}}{{3}}$, or a $\nicefrac{{1}}{{3}}$-edge to zero.)

    2. (b)

(Local Increase) If $|M\cap\partial I|=2$, then
$y(E(I))=|I|-\nicefrac{{4}}{{3}}$, and hence $y|_{I}\not\in
K_{spT}(\widehat{H}[I])$. To fix this, pick a random edge $e$ from the two
matching edges in $M\cap\partial I$, pick a random edge $f\in E(I)$ adjacent
to $e$, and increase the $y$-value of $f$ by $\nicefrac{{1}}{{3}}$ to get
solution $\widehat{y}$. (Note this increases one $\nicefrac{{1}}{{3}}$ edge to
$\nicefrac{{2}}{{3}}$.)

Suppose this edge $f$ is contained in some matroid constraint, say on set $P$
of edges:

      1. i.

If all three edges $f,g,h$ of this constraint are in $E(I)$, pick a random one
of $\\{g,h\\}$, say $h$, and redefine $P\leftarrow\\{f,g\\}$. Note that
$\widehat{y}_{f}+\widehat{y}_{g}=1$ and the constraint is tight.

      2. ii.

If $f$ belongs to a constraint $P=\\{f,g\\}$, that used to be $\\{f,g,h\\}$
but the third edge $h$ was in $\partial I$ and hence was dropped, retain the
constraint $P=\\{f,g\\}$. Again $\widehat{y}_{f}+\widehat{y}_{g}=1$.

The following claims show that $\widehat{y}|_{I}$ has the right marginals, and
that it belongs to the spanning tree polytope. So now we can sample a spanning
tree $T$ from it (subject to the partition matroid $\mathcal{M}$). Then we
show, in §B.2, that this tree also satisfies negative correlation properties.

###  B.1 Feasibility of the Solution $\widehat{y}$

######  Claim B.2 (Marginal Preserving).

$\mathbb{E}[\widehat{y}_{e}]=x_{e}=\nicefrac{{1}}{{2}}$ for all $e\in E(I)$.

###### Proof.

Since $\mathbb{E}[y_{e}]=\nicefrac{{1}}{{2}}$ for all $e$, we focus on the
expected difference $\mathbb{E}[\widehat{y}_{e}-y_{e}]$. We only need to worry
about internal edges incident to boundary vertices, since those are the only
edges whose $y$-values are changed.

  * •

Let $e$ be an edge incident only on one boundary vertex $v$, that has a
boundary edge $f$. Now consider choosing $M$ randomly. When $M\cap\partial
I=\varnothing$, which happens w.p. $\nicefrac{{1}}{{2}}$, $e$ is decreased
w.p. $\nicefrac{{1}}{{12}}$, since the total internal degree of boundary
vertices is $12$. On the other hand, when $f\in M$ (w.p.
$\nicefrac{{1}}{{4}}$, and this implies the event $|M\cap\partial I|=2$), $e$
is increased with probability $\nicefrac{{1}}{{6}}$, since the total internal
degree of the boundary vertices incident to internal endpoints of $M$ is $6$.

  * •

Let $e=uv$ such that both $u,v$ are boundary vertices with edges
$f,g\in\partial I$ respectively. Now, when $M\cap\partial I=\varnothing$,
which happens w.p. $\nicefrac{{1}}{{2}}$, $e$ is decreased w.p.
$\nicefrac{{1}}{{6}}$ (since $e$ is counted from both ends). When $f\in M$
(w.p. $\nicefrac{{1}}{{4}}$, and this implies the event $|M\cap\partial
I|=2$), $e$ is increased with probability $\nicefrac{{1}}{{6}}$ “through $f$”.
And same happens for $g$. Therefore, regardless of how $f$ and $g$ are
correlated, $e$ is increased with probability
$2\cdot\nicefrac{{1}}{{4}}\cdot\nicefrac{{1}}{{6}}=\nicefrac{{1}}{{12}}$.

In both cases, the expected difference is zero, giving the proof. ∎

######  Claim B.3 (Feasible).

The solutions $\widehat{y}|_{I}$ belong to the spanning tree polytope.

###### Proof.

The equality constraint $\sum_{e\in I}\widehat{y}_{e}=|I|-1$ is satisfied by
design, so we need to check that $\sum_{e\in
E[S^{\prime}]}\widehat{y}_{e}\leq|S^{\prime}|-1$ for all proper subsets
$S^{\prime}\subsetneq I$. Recall that $\partial_{H}S^{\prime}$ has at least
six edges, including the edges leaving $I$. Let
$a:=|E_{H}(S^{\prime},I\setminus S^{\prime})|$ and
$b:=|E_{H}(S^{\prime},V\setminus I)|$ so that $a+b\geq 6$.

Observe that

$\displaystyle\sum_{e\in E[S^{\prime}]}y_{e}=\frac{1}{2}\bigg{(}\sum_{v\in
S^{\prime}}\sum_{e\in\partial_{H}v}y_{e}-\sum_{e\in\partial_{H}S^{\prime}}y_{e}\bigg{)}\leq\frac{1}{2}\Big{(}2|S^{\prime}|-(a+b)/3\Big{)}\leq|S^{\prime}|-1.$
(10)

  * •

In a local decrease, since we decrease $y$ to get $\widehat{y}$, the
constraint is still satisfied.

  * •

In a local increase, since we increase only one edge by $\nicefrac{{1}}{{3}}$,
we only need to consider the case when (10) is tight, which implies that every
edge going out of $S^{\prime}$ has value exactly $\nicefrac{{1}}{{3}}$. In
particular, every vertex in $S^{\prime}$ is matched inside $S^{\prime}$. By
construction, the edge whose $y$-value we increase must have a neighboring
edge matched by $M$ outside $I$. This $M$-edge cannot be incident to
$S^{\prime}$, so we are safe. ∎

###  B.2 Correlation Properties: $|V(H)|$ odd

To prove the correlation properties in the odd case, we observe that each of
the proofs from §3.2.1 focuses on a small set of edges. Hence, if we can show
that with constant probability the fractional solution for these edges is
unchanged, the proofs go through with small changes (and weaker constants). A
more careful case-analysis is likely to give better constants.

We will often make arguments that condition on certain sets of edges not being
perturbed by a local increase or decrease. The following lemma gives lower
bounds on the probabilities that these desired events occur.

######  Lemma B.4.

Let $f,g$ be internal edges incident to vertex $v$. Then, if $f$ or $g$ lies
in $M$, $y_{f}$ and $y_{g}$ remain untouched by a local increase or decrease
w.p. at least $\nicefrac{{2}}{{3}}$. Similarly, if $v$ is an internal vertex
with internal edges $e,f,g,h$, the four edges remain untouched with
probability at least $\nicefrac{{2}}{{3}}$

###### Proof.

If one of $f,g$ lies in $M$ (which happens w.p. $\nicefrac{{1}}{{2}}$), then
its $y$ value equals $1$ and it belongs to $T$ w.p. $1$. If there is a local
increase, then the increase can only affect the edge not in $M$ (through its
other endpoint), so the $y$-value remains unchanged w.p.
$\nicefrac{{2}}{{3}}$. If there is a local decrease, both edges $f,g$ may have
both endpoints that are boundary vertices in worst case, giving a
$\nicefrac{{4}}{{12}}$ chance of being decreased, and hence a
$\nicefrac{{8}}{{12}}=\nicefrac{{2}}{{3}}$ chance of $y$-values of these two
edges remaining unchanged.

The second statement follows from the fact that there are three internal edges
adjacent to an external edge. ∎

We move on to the proofs of the correlation properties. We restate the lemmas
here for convenience.

See 3.1

###### Proof of Lemma 3.1, Odd Case.

_The MatInt claims:_ As in the even case, to prove
$\mathbb{P}(|T\cap\\{f,g\\}|=2)\geq\nicefrac{{1}}{{9}}$, we need only
knowledge of the marginals and not the specific sampler. If one of $f,g$ lies
in $M$ (which happens w.p. $\nicefrac{{1}}{{2}}$) $y$-values of these two
edges remaining unchanged with probability at least $\nicefrac{{2}}{{3}}$, due
to Lemma B.4. Now, conditional on these $y$-values remaining unchanged, the
other edge (not in $M$) is chosen with probability $\nicefrac{{1}}{{3}}$,
making the unconditional probability
$\nicefrac{{1}}{{2}}\cdot\nicefrac{{2}}{{3}}\cdot\nicefrac{{1}}{{3}}=\nicefrac{{1}}{{9}}$,
as desired. Similarly, conditioned on $f$ lying in $M$ and hence belonging to
$T$, edge $g$ is not chosen w.p. $1-y_{e}=\nicefrac{{2}}{{3}}$, giving a
probability at least
$\nicefrac{{1}}{{4}}\cdot\nicefrac{{2}}{{3}}\cdot\nicefrac{{2}}{{3}}=\nicefrac{{1}}{{9}}$,
proving the second part of Lemma 3.1 for the MatInt sampler.

_The MaxEnt claim:_ It remains to show that
$\mathbb{P}(T\cap\\{f,g\\}=\\{f\\})\geq\nicefrac{{12}}{{72}}$. In the case
that $f\in M$, we once again have a probability of at least
$\nicefrac{{2}}{{3}}$ that $f$ and $g$ are untouched, due to Lemma B.4. Sincce
$\mathbb{P}(g\not\in T)=\nicefrac{{2}}{{3}}$ in this case, we have

$\mathbb{P}(T\cap\\{f,g\\}=\\{f\\}\wedge f\in
M)\geq\nicefrac{{1}}{{4}}\cdot\nicefrac{{2}}{{3}}\cdot\nicefrac{{2}}{{3}}=\nicefrac{{1}}{{9}}.$

In the case that neither $f$ nor $g$ is in $M$, the probability $f$ or $g$ is
chosen in a local decrease is at most $\nicefrac{{1}}{{3}}$ and the
probability $f$ or $g$ is chosen in a local increase is at most
$\nicefrac{{1}}{{2}}$. (For the first bound, the worst case is when each of
the three endpoints of $f,g$ is incident to an external edge. Then the
probability that neither $f$ nor $g$ is chosen for a local decrease is at
least
$\nicefrac{{1}}{{2}}\cdot\nicefrac{{2}}{{3}}+\nicefrac{{1}}{{4}}\cdot\nicefrac{{1}}{{3}}+\nicefrac{{1}}{{4}}=\nicefrac{{2}}{{3}}$.
For the second bound, the worst case is when each edge in $M\cap\partial I$ is
incident to an endpoint of $f$, w.l.o.g. Then the probability that neither $f$
nor $g$ is chosen for a local increase is at least
$\nicefrac{{1}}{{2}}\cdot\nicefrac{{2}}{{3}}+\nicefrac{{1}}{{2}}\cdot\nicefrac{{1}}{{3}}=\nicefrac{{1}}{{2}}$.)
Hence, the edges remain untouched with probability at least
$\nicefrac{{1}}{{2}}$. In total, this gives

$\mathbb{P}(T\cap\\{f,g\\}=\\{f\\}\wedge f,g\not\in
M)\geq\nicefrac{{1}}{{2}}\cdot\nicefrac{{1}}{{2}}\cdot\nicefrac{{2}}{{9}}=\nicefrac{{4}}{{72}}$

where the bound $\mathbb{P}(T\cap\\{f,g\\}=\\{f\\}\mid f,g\not\in
M)\geq\nicefrac{{1}}{{9}}$ was computed in the even case (3.2.1). Hence,

$\mathbb{P}(T\cap\\{f,g\\}=\\{f\\})\geq\nicefrac{{1}}{{9}}+\nicefrac{{4}}{{72}}=\nicefrac{{12}}{{72}}.\qed$

See 3.2

###### Proof of Lemma 3.2, Odd Case.

_The MatInt claims:_ Each perfect matching $M$ contains one of these four
edges in $\partial v$. Say that edge is $e$. The vertex $v$ has no external
edges, so regardless of whether we do a local increase or decrease, these four
edges remain untouched w.p. $\nicefrac{{2}}{{3}}$, due to Lemma B.4. If this
happens, and if $e$ also belongs to $M^{\prime}$ (w.p. $\nicefrac{{1}}{{7}}$),
tree $T$ contains exactly one of $\\{f,g,h\\}$, which gives us the bound
$\nicefrac{{2}}{{21}}$. Moreover, the probability of this edge in $T$
belonging to the other pair (in this case, $\\{g,h\\}$) is
$\nicefrac{{2}}{{3}}$, giving the bound $\nicefrac{{4}}{{63}}$.

_The MaxEnt claims:_ Since $v$ is not a boundary vertex, none of $e,f,g,h$ are
picked for a local increase or decrease w.p. at least $\nicefrac{{2}}{{3}}$,
due to Lemma B.4. Conditioning on $e,f,g,h$ remaining untouched, we have the
same analysis as that of the even case (3.2.1). Hence, we obtain

$\mathbb{P}(|T\cap\\{e,f,g,h\\}|=2)\geq\nicefrac{{2}}{{3}}\cdot\nicefrac{{4}}{{9}}=\nicefrac{{8}}{{27}}$

and

$\mathbb{P}(|T\cap\\{e,f\\}|=|T\cap\\{g,h\\}|=1)\geq\nicefrac{{2}}{{3}}\cdot\nicefrac{{8}}{{27}}=\nicefrac{{16}}{{81}}.\qed$

See 3.3

###### Proof of Lemma 3.3a, Odd Case.

_The MatInt claims:_ In this proof, we will often use that $G$ is a simple
graph. Suppose $e\in M^{\prime}$, which happens w.p. $\nicefrac{{1}}{{28}}$.
Call the edges $(\partial u\cup\partial v)\setminus\\{e\\}$ _interesting_
edges. Condition on the matching $M$ (which decides whether the change is a
local increase or a decrease), and the edge $f$ in $\partial I$ whose incident
internal edge is increased/decreased. At most two of the three internal edges
incident to $f$ can be interesting. Since $u,v$ are non-boundary vertices, the
value of $e$ is never changed by the alteration.

First suppose it is a local decrease, then with probability at least
$\nicefrac{{1}}{{3}}$ a non-interesting edges is reduced, and hence the
matroid constraint ensures we always succeed. With probability at most
$\nicefrac{{2}}{{3}}$ an interesting edge is reduced, in which case we still
have a $\nicefrac{{2}}{{3}}$ chance of getting degree $2$ at both $u$ and $v$.
So we have
$\nicefrac{{1}}{{3}}+\nicefrac{{2}}{{3}}\cdot\nicefrac{{2}}{{3}}=\nicefrac{{7}}{{9}}$
of success, conditioned on the choice of the edge.

Else, suppose it is a local increase; the argument is similar. With
probability at least $\nicefrac{{1}}{{3}}$ a non-interesting edges is
increased, and hence the matroid constraint ensures we always succeed. With
probability at most $\nicefrac{{2}}{{3}}$ an interesting edge is increased, in
which case we change the matroid constraint to drop one of the other
interesting edges. This dropped edge can be added in with its
$\widehat{y}$-value $\nicefrac{{1}}{{3}}$, and hence we have a
$\nicefrac{{2}}{{3}}$ probability of getting degree $2$ at both $u$ and $v$.
Again, the probability of success is
$\nicefrac{{1}}{{3}}+\nicefrac{{2}}{{3}}\cdot\nicefrac{{2}}{{3}}=\nicefrac{{7}}{{9}}$
of success. Removing the conditioning on $e\in M^{\prime}$, the net
probability of success is
$\nicefrac{{1}}{{28}}\cdot\nicefrac{{7}}{{9}}=\nicefrac{{1}}{{36}}$.

_The MaxEnt claims: _Let $U=\delta(u)\setminus\\{e\\}$ and
$V=\delta(v)\setminus\\{e\\}$. Condition on $e\in M$. Since $u,v$ are both
non-boundary vertices, the value of $e$ will remain unchanged regardless of
whether there is a local increase or decrease, so we will have $y_{e}=1$
always. Recall that $y$ is changed at a single edge when the local increase or
decrease is performed. We take cases on whether a local increase or local
decrease occurs.

  1. A local decrease occurs. Figure 8: The decrease case in Lemma 3.3a, labelled with $y$-values after the decrease is performed.

If none of the edges in $U\cup V$ are decreased, then (conditioned on $e\in
M$) the analysis from the even case (3.2.1) gives

$\mathbb{P}(X_{U}=1\wedge X_{V}=1)\geq\nicefrac{{256}}{{2187}}.$

Now consider the case that an edge in $U\cup V$ is decreased. Let $S_{1}=U$
and let $S_{2}=\\{a,b\\}$ denote the set of two nonzero edges in
$V\setminus\\{e\\}$ (see Figure 8). Applying Theorem 2.9 and the fact that
$\mathbb{E}(|S_{2}\cap T|)=\nicefrac{{2}}{{3}}$, we have
$\mathbb{P}(|S_{2}\cap T|=1)\geq
2\cdot\nicefrac{{2}}{{3}}\cdot\nicefrac{{1}}{{3}}=\nicefrac{{4}}{{9}}$. By
Theorem 2.8,

$\nicefrac{{1}}{{3}}=1-\nicefrac{{2}}{{3}}\leq\mathbb{E}(|S_{1}\cap T|\mid
a\in T,b\not\in T)\leq 1+\nicefrac{{1}}{{3}}=\nicefrac{{4}}{{3}}.$

We apply Theorem 2.9 again to lower bound $\mathbb{P}(|S_{1}\cap T|=1\mid a\in
T,b\not\in T)$ by

$\mathbb{P}(|S_{1}\cap T|=1\mid a\in T,b\not\in T)\geq
3\cdot\nicefrac{{1}}{{9}}\cdot(\nicefrac{{8}}{{9}})^{2}=\nicefrac{{64}}{{243}}.$

Since the same calculation may be repeated with $b\in T$ and $a\not\in T$ (as
$y_{a}=y_{b}$), we have

$\mathbb{P}(X_{U}=1\wedge
X_{V}=1)\geq\nicefrac{{4}}{{9}}\cdot\nicefrac{{64}}{{243}}=\nicefrac{{256}}{{2187}}.$

So comparing both cases, we have that conditioned on $e\in M$, if there is a
local decrease then

$\mathbb{P}(X_{U}=1\wedge
X_{V}=1)\geq\min\\{\nicefrac{{256}}{{2187}},\nicefrac{{256}}{{2187}}\\}=\nicefrac{{256}}{{2187}}.$

  2. A local increase occurs.

We first note that the probability of no edge in $U\cup V$ being increased is
at least $\nicefrac{{1}}{{3}}$, in which case the analysis from the even case
(3.2.1) gives

$\mathbb{P}(X_{U}=1\wedge X_{V}=1)\geq\nicefrac{{256}}{{2187}}.$

Now consider the case that an edge $c$, say in $U$, is increased from
$\nicefrac{{1}}{{3}}$ to $\nicefrac{{2}}{{3}}$. Let
$U\setminus\\{c\\}=\\{a,b\\}$. Since
$\mathbb{E}[X_{a,b}]=\nicefrac{{2}}{{3}}$, by Markov’s inequality we have
$\mathbb{P}(X_{a,b}=0)\geq\nicefrac{{1}}{{3}}$. Furthermore,
$\mathbb{E}[X_{c}\mid X_{a,b}=0]\geq\mathbb{E}[X_{c}]=\nicefrac{{2}}{{3}}$ by
Theorem 2.8. In total, $\mathbb{P}(c\in T,a,b\not\in
T)\geq\nicefrac{{1}}{{3}}\cdot\nicefrac{{2}}{{3}}=\nicefrac{{2}}{{9}}$.
Applying Theorem 2.8 thrice more, we obtain

$\nicefrac{{1}}{{3}}\leq\mathbb{E}(|S_{2}\cap T|\mid c\in T,a,b\not\in
T)\leq\nicefrac{{5}}{{3}}$

which by Theorem 2.9 gives us

$\mathbb{P}(|S_{2}\cap T|=1\mid c\in T,a,b\not\in
T)\geq\nicefrac{{64}}{{243}}.$

This yields, in the case that an edge in $U\cup V$ is increased,

$\mathbb{P}(X_{U}=1\land
X_{V}=1)\geq\nicefrac{{64}}{{243}}\cdot\nicefrac{{2}}{{9}}=\nicefrac{{128}}{{2187}}.$

Since the probability that no edge in $U\cup V$ is increased is at least
$\nicefrac{{1}}{{3}}$, and
$\nicefrac{{256}}{{2187}}>\nicefrac{{128}}{{2187}}$, in the worst case we have
that, conditioned on $e\in M$, if there is a local increase then

$\mathbb{P}(X_{U}=1\land
X_{V}=1)\geq\nicefrac{{1}}{{3}}\cdot\nicefrac{{256}}{{2187}}+\nicefrac{{2}}{{3}}\cdot\nicefrac{{128}}{{2187}}=\nicefrac{{512}}{{6561}}.$

Now comparing the cases of local increase and decrease and removing the
conditioning of $e\in M$, we obtain in the worst case

$\mathbb{P}(X_{U}=1\land
X_{V}=1)\geq\nicefrac{{1}}{{4}}\cdot\min\\{\nicefrac{{256}}{{2187}},\nicefrac{{512}}{{6561}}\\}=\nicefrac{{128}}{{6561}}$

which is the bound we sought. ∎

###### Proof of Lemma 3.3b, _Odd Case_..

_The MatInt claims._ Fix a matching $M$ such that $e\in M$ (w.p.
$\nicefrac{{1}}{{4}}$); each of $u,v$ have two other internal edges, each with
$y$-value $\nicefrac{{1}}{{3}}$. Call these four _interesting_ edges. Suppose
$M\cap\partial I$ has two edges, then we perform a local increase step.
Condition on the edge in $M\cap\partial I$ chosen as part of the local
increase: in the worst case it is incident to the endpoint of two of the
interesting edges.

  * •

Then w.p. $\nicefrac{{2}}{{3}}$ it increases one of the interesting edges from
$y_{f}=\nicefrac{{1}}{{3}}$ to $\widehat{y}_{f}=\nicefrac{{2}}{{3}}$. The
total $\widehat{y}$-value of interesting edges becomes $\nicefrac{{5}}{{3}}$.
By the same argument as for the even case, the tree $T$ contains exactly one
interesting edge with probability at least $\nicefrac{{1}}{{3}}$.

  * •

With the remaining probability $\nicefrac{{1}}{{3}}$, the increase is not to
an interesting edge, and hence we succeed with the original probability
$\nicefrac{{2}}{{3}}$.

The total probability of success is therefore
$\nicefrac{{2}}{{3}}\cdot\nicefrac{{1}}{{3}}+\nicefrac{{1}}{{3}}\cdot\nicefrac{{2}}{{3}}=\nicefrac{{4}}{{9}}$.

On the other hand, if $M\cap\partial I$ is empty, then we perform a local
decrease step. Condition on the boundary edge chosen in the first part of the
local decrease. In the worst case it is one of the boundary edges incident to
either $u$ or $v$. One of the interesting edges is reduced w.p.
$\nicefrac{{2}}{{3}}$, from $y_{f}=\nicefrac{{1}}{{3}}$ to
$\widehat{y}_{f}=0$. If that happens, the total $\widehat{y}$-value of
interesting edges sums to $1$. The connectivity of the spanning tree means
that every tree we sample with these marginals will have exactly one
interesting edge.

Hence, in either case, we have exactly one of these four internal edges and
satisfy the condition of the claim with probability $\nicefrac{{4}}{{9}}$,
conditioned on having $e\in M$. The overall probability is therefore at least
$\nicefrac{{1}}{{4}}\cdot\nicefrac{{4}}{{9}}=\nicefrac{{1}}{{9}}$.

_The MaxEnt claims._ Observe that the edge $e$ will always contribute either:
0 to both the degree of $u$ in $T$ and the degree of $v$ in $T$ OR 1 to both
the degree of $u$ in $T$ and the degree of $v$ in $T$. Thus, to lower bound
the probability that $u$ and $v$ have different parities in $T$, we will not
need to consider whether or not $e$ is in $T$.

Let $a,b$ be the two _internal_ edges in $\delta(u)\setminus\\{e\\}$ and $c,d$
be the two _internal_ edges in $\delta(v)\setminus\\{e\\}$. (We know each set
has exactly two edges because $u,v$ are each boundary vertices.) Let $f,g$ be
the two external edges incident to $u,v$, respectively. We take cases based on
(a) whether a local increase or decrease is performed, (b) whether or not any
of $a,b,c,d$ are changed by the local increase or decrease, and (c) whether or
not $e\in M$. Note that for (b), we do not take subcases on whether or not $e$
is changed, by the above paragraph. Also note that for (c), we consider
whether $e\in M$ in order to determine the marginals of $\\{a,b,c,d\\}$ prior
to a local increase or decrease.

  1. Case I.N.1: local increase occurs, $\\{a,b,c,d\\}$ not touched, $e\in M$.

In this case, we obtain the same bound from Case 1 of the even case in the
proof of Lemma 3.3b (see 3.2.1), that is,

$\mathbb{P}(\text{exactly one of $u,v$ has odd degree in
$T$})\geq\mathbb{P}(X_{a,b,c,d}=1)\geq\boxed{\nicefrac{{2}}{{3}}}.$

  2. Case I.N.2: local increase occurs, $\\{a,b,c,d\\}$ not touched, $e\not\in M$.

This case includes the two subcases $a,c\in M$ and $a\in M,c\not\in M$, which
are cases 2 and 3 in the proof of Lemma 3.3b (see 3.2.1) and yield lower
bounds on the desired probabilitiy of $\boxed{\nicefrac{{4}}{{9}}}$ and
$\boxed{\nicefrac{{8}}{{27}}}$, respectively. Finally, there is one more
subcase for the case where $|V(H)|$ is odd, namely, $a,c\not\in T$, since we
may have $f,g\in M$. Since in this subcase $a,b,c,d$ are all
$\nicefrac{{1}}{{3}}$-valued edges, we have the same bound from Case 1 of the
even case in the proof of Lemma 3.3, namely, $\boxed{\nicefrac{{2}}{{3}}}$.

  3. Case I.T.1: local increase occurs, $\\{a,b,c,d\\}$ touched, $e\in M$.

One of the edges $a,b,c,d$ is increased from $\nicefrac{{1}}{{3}}$ to
$\nicefrac{{2}}{{3}}$, while the rest are still $\nicefrac{{1}}{{3}}$-valued,
since $e\in M$. Hence, $\mathbb{E}[X_{a,b,c,d}]=\nicefrac{{5}}{{3}}$.
Furthermore, note that we must have $X_{a,b,c,d}\geq 1$. This gives

$\mathbb{P}(\text{exactly one of $u,v$ has odd degree in
$T$})\geq\mathbb{P}(X_{a,b,c,d}=1)\geq\boxed{\nicefrac{{1}}{{3}}}.$

  4. Case I.T.2: local increase occurs, $\\{a,b,c,d\\}$ touched, $e\not\in M$.

Just as in Case I.N.2., there are three subcases. First consider the subcase
of $a,c\in M$. In this subcase, $a,c$ cannot be increased, so we know
$\mathbb{E}[X_{b,d}]=\nicefrac{{1}}{{3}}$. By Theorem 2.9,
$\mathbb{P}(X_{b,d}=1)\geq\boxed{\nicefrac{{1}}{{2}}}$.

Next, consider the subcase that only $a\in M$. Then, we have
$\mathbb{E}(X_{b,c,d})=\nicefrac{{4}}{{3}}$ and hence by Theorem 2.9,
$\mathbb{P}(X_{b,c,d}=2)\geq
2\cdot\nicefrac{{1}}{{3}}\cdot\nicefrac{{1}}{{3}}\geq\boxed{\nicefrac{{5}}{{18}}}$.

For the final subcase that $f,g\in M$, we have
$\mathbb{E}[X_{a,b,c,d}]=\nicefrac{{5}}{{3}}$ and since $X_{a,b,c,d}\geq 1$,
we have $\mathbb{P}(X_{a,b,c,d}=1)\geq\boxed{\nicefrac{{1}}{{3}}}$.

This concludes the local increase cases. We move on to the local decrease
cases.

  1. Case D.N.1: local decrease occurs, $\\{a,b,c,d\\}$ not touched, $e\in M$.

This is the same case as I.N.1., giving a bound of
$\boxed{\nicefrac{{2}}{{3}}}$.

  2. Case D.N.2: local decrease occurs, $\\{a,b,c,d\\}$ not touched, $e\not\in M$.

This is the same case as I.N.2., taking only the first subcase ($a,c\in M$),
since $M\cap\partial I=\varnothing$ in a local decrease. Thus the lower bound
here is $\boxed{\nicefrac{{4}}{{9}}}$.

  3. Case D.T.1: local decrease occurs, $\\{a,b,c,d\\}$ touched, $e\in M$.

Since $e\in M$, we know $a,b,c,d$ start of as $\nicefrac{{1}}{{3}}$-valued.
Then, w.l.o.g., say $a$ is decreased to 0. Then, $\mathbb{E}[X_{b,c,d}]=1.$
But since $X_{b,c,d}\geq 1$, this gives $\mathbb{P}(X_{b,c,d}=1)=\boxed{1}.$

  4. Case D.T.2: local decrease occurs, $\\{a,b,c,d\\}$ touched, $e\not\in M$.

Since in a local decrease $M\cap\partial I=\varnothing$, we have w.l.o.g. that
$a,c\in M$ and that $a$ is not decreased. So
$\mathbb{E}(X_{b,c,d})=1+2\cdot\nicefrac{{1}}{{3}}-\nicefrac{{1}}{{3}}=\nicefrac{{4}}{{3}}.$
Since we know $a\in T$, we instead study $\mathbb{P}(X_{b,c,d}=2)$; by Theorem
2.9, we have $\mathbb{P}(X_{b,c,d}=2)\geq
2\cdot\nicefrac{{1}}{{6}}\cdot\nicefrac{{5}}{{6}}=\boxed{\nicefrac{{5}}{{18}}}$.

The minimum of all the boxed quantities is $\nicefrac{{5}}{{18}}$. Hence, for
the odd case of Lemma 3.3b, we obtain the desired bound

$\mathbb{P}(\text{exactly one of $u,v$ has odd degree in
$T$})\geq\nicefrac{{5}}{{18}}.\qed$

##  Appendix C Charging Proof Details

###### Proof of Averaging Argument, §6.5.1, Case 4.

We will use an averaging argument to show that the expected charge is no worse
than $p\cdot\max\\{\frac{\tau}{2},\frac{\gamma}{2},\frac{\beta}{4}\\}.$ We
construct a flow network as in the proof of Lemma 6.3 in order to show there
exists a function $x:B\times F\rightarrow\mathbb{R}_{+}$ satisfying constraint
(7) for $c=\max\\{\frac{\tau}{2},\frac{\gamma}{2},\frac{\beta}{4}\\}$. Then we
can apply a charging scheme like the one described in Case 1 using the
function $x$. The flow network is as follows: take the graph $H=(B,F)$ and add
a source node $s$ and a sink node $t$. Connect $s$ to every vertex $b$ in $B$,
and label $(s,b)$ with capacity $\tau,\gamma,$ or $\frac{\beta}{2}$ based on
whether $b$ corresponds to a non-$K_{5}$ degree, $K_{5}$ degree, or cycle
edge, respectively. To find $x$ satisfying the properties in the above
paragraph, by Lemma 1 we need to show that for each $T\subseteq B$,

$|N(T)|\geq\frac{\tau\cdot n_{\tau}+\gamma\cdot
n_{\gamma}+\frac{1}{2}\cdot\beta\cdot
n_{\beta}}{\max\\{\frac{\tau}{2},\frac{\gamma}{2},\frac{\beta}{4}\\}}$

where $n_{\tau},n_{\gamma},$ and $n_{\beta}$ are the numbers of vertices in
$T$ corresponding to non-$K_{5}$ degree, $K_{5}$ degree, and cycle edges,
respectively. Note $n_{\tau}+n_{\gamma}+n_{\beta}=|T|$.

Lemma 6.4 showed that

$\displaystyle|N(T)|$
$\displaystyle\geq\frac{\tau\cdot|T|}{\frac{\tau}{2}}\geq\frac{\tau\cdot|T|}{\max\\{\frac{\tau}{2},\frac{\gamma}{2},\frac{\beta}{4}\\}}$
$\displaystyle|N(T)|$
$\displaystyle\geq\frac{\gamma\cdot|T|}{\frac{\gamma}{2}}\geq\frac{\gamma\cdot|T|}{\max\\{\frac{\tau}{2},\frac{\gamma}{2},\frac{\beta}{4}\\}}$
$\displaystyle|N(T)|$
$\displaystyle\geq\frac{\frac{1}{2}\cdot\beta\cdot|T|}{\frac{\beta}{4}}\geq\frac{\frac{1}{2}\cdot\beta\cdot|T|}{\max\\{\frac{\tau}{2},\frac{\gamma}{2},\frac{\beta}{4}\\}}.$

Now taking a convex combination of the three inequalities above we obtain:

$\displaystyle|N(T)|$
$\displaystyle=\frac{n_{\tau}}{|T|}\cdot|N(T)|+\frac{n_{\gamma}}{|T|}\cdot|N(T)|+\frac{n_{\beta}}{|T|}\cdot|N(T)|$
$\displaystyle\geq\frac{\tau\cdot n_{\tau}+\gamma\cdot
n_{\gamma}+\frac{1}{2}\cdot\beta\cdot
n_{\beta}}{\max\\{\frac{\tau}{2},\frac{\gamma}{2},\frac{\beta}{4}\\}}$

which is precisely what we sought to show. This concludes Case 4. ∎

##  Appendix D Symmetry Lemma

######  Claim D.1 (Symmetry Lemma).

For any graph $H$ with each edge $e$ having $x_{e}=\nicefrac{{1}}{{2}}$, let
$T$ be a random set of edges faithful to the marginals, i.e., $\Pr[e\in
T]=x_{e}$. For any two edges $f,g$, let $p_{00},p_{10},p_{01},p_{11}$ denote
the probabilities of $T\cap\\{f,g\\}$ being
$\varnothing,\\{f\\},\\{g\\},\\{f,g\\}$ respectively. Then $p_{00}=p_{11}$ and
$p_{01}=p_{10}$.

###### Proof.

Observe that $p_{00}+p_{01}+p_{10}+p_{11}=1$. Moreover,
$p_{01}+p_{10}+2p_{11}=\mathbb{E}[|T\cap\\{f,g\\}|]=x_{f}+x_{g}=1$. Hence,
$p_{00}=p_{11}$, proving the first statement. Now,
$p_{10}+p_{11}=x_{f}=x_{g}=p_{01}+p_{11},$ giving $p_{10}=p_{01}$, proving the
second. ∎