multiple directions/.style=for tree=#1, phantom, for relative level=1no edge,
delay=!c.content/.pgfmath=content("!u"), before computing xy=l=0,s=0, multiple
directions/.default=, grow subtree/.style=for tree=grow=#1, grow’
subtree/.style=for tree=grow’=#1

# Optimal unimodular matchings

Nathanaël Enriquez, Mike Liu, Laurent Ménard and Vianney Perchet

###### Abstract

We consider sequences of finite weighted random graphs that converge locally
to unimodular i.i.d. weighted random trees. When the weights are atomless, we
prove that the matchings of maximal weight converge locally to a matching on
the limiting tree. For this purpose, we introduce and study unimodular
matchings on weighted unimodular random trees as well as a notion of
optimality for these objects. In this context, we prove that, in law, there is
a unique optimal unimodular matching for a given unimodular tree. We then
prove that this law is the local limit of the sequence of matchings of maximal
weight. Along the way, we also show that this law is characterised by an
equation derived from a message passing algorithm.

##### Keywords:

Optimal matchings, sparse random graphs, unimodularity, local convergence.

##### Mathematics Subjects Classification:

05C70, 05C82, 60C05, 60K35.

##  1 Introduction

Optimal matchings in random graphs is a problem with a long history dating
back to the paper by Karp and Sipser [8]. In this seminal paper, they obtain
the asymptotic size of a maximal matching in a sparse Erdős-Rényi random graph
with average degree $c\in(0,+\infty)$. Their method relies on the analysis of
a greedy algorithm that constructs a matching in a graph. It turns out that
the algorithm is very close to optimality when $c\leq e$, and less so when
$c>e$ (even if it is still asymptotically optimal), making the analysis
trickier in this regime.

More recently, Gamarnik, Nowick and Swirscsz [7] studied the edge-weighted
version of this maximal matching problem on the Erdős-Rényi random graph and
on regular random graphs. Their approach does not rely on the Karp–Sipser
algorithm, but on a local optimality ansatz inspired by the earlier
introduction of the so-called objective method by Aldous [1, 5, 2, 3].
Gamarnik, Nowick and Swirscsz were able to compute the asymptotic weight of
the optimal matching in Erdős-Rényi random graph when $c\leq e$ and in the
special case where the weights have exponential distribution. These
restrictions come from the fact that their method depends on the uniqueness of
the solution of a fixed point in a belief propagation equation.

Strikingly we realised that, under mild assumptions, this uniqueness is not
required for the convergence in law of the optimal matching on a locally tree-
like edge-weighted random graph. Informally, the limit $\mathbb{M}$ is a
random matching on the unimodular limiting tree $(\mathbb{T},o)$ with iid
edge-weights $w=(w(e))_{e\in E(\mathbb{T})}$ with law $\omega$, whose law is
invariant by re-rooting. We call such random matchings unimodular (see Section
2 for precise definitions). In addition, the limit $\mathbb{M}$ is optimal in
the sense that the quantity

$\displaystyle\operatorname{perf}(\mathbb{T},o,w,\mathbb{M})$
$\displaystyle:=\mathbb{E}\left[\sum_{v\sim
o}w(o,v)\mathbbm{1}_{(o,v)\in\mathbb{M}}\right]$ (1)

is maximal among all unimodular matchings of $(\mathbb{T},o,w)$.

Before stating our main result, we need to introduce Unimodular Bienaymé
Galton Watson random trees (UBGW), which are the limiting unimodular random
trees of our graphs. Let $\pi$ be a distribution on non-negative integers with
finite variance and generating function $\phi$. We say that a rooted tree
$(\mathbb{T},{o})$ is a UBGW with offspring distribution $\pi$ if it has the
following law:

  * •

The number of children of vertices of $\mathbb{T}$ are all independent.

  * •

The number of children of the root $o$ is distributed according to $\pi$.

  * •

The number of children of every non-root vertex is distributed according to
$\hat{\pi}$, the sized biased version of $\pi$. The generating function of
$\hat{\pi}$ is $\hat{\phi}(x)=\frac{\phi^{\prime}(x)}{\phi^{\prime}(1)}$.

We can now state our main result:

######  Theorem 1.

Let $G_{n}=(V_{n},E_{n},w_{n})$ be a sequence of weighted random graphs and
let $\mathbb{M}_{\mathrm{opt}}(G_{n})$ be a maximum matching on $G_{n}$.
Choose a root ${o}_{n}$ uniformly among the vertices and suppose that the
sequence of rooted weighted random graphs $(G_{n},{o}_{n})$ converges locally
to a vertex-rooted Unimodular Bienaymé-Galton-Watson (UBGW) tree
$(\mathbb{T},{o})$ with reproduction law $\pi$ and i.i.d edge-weights with law
$\omega$ such that:

  * •

both $\pi$ and $\omega$ have finite expectation,

  * •

the law $\omega$ is atomless,

  * •

the ratio $\frac{2|E_{n}|}{|V_{n}|}$ converges in probability to the
expectation of $\pi$.

Then there exists a unique (in law) optimal matching $\mathbb{M}$ on
$(\mathbb{T},{o})$ such that $(G_{n},o_{n},\mathbb{M}_{\mathrm{opt}}(G_{n}))$
converges locally to $(\mathbb{T},{o},\mathbb{M})$. Furthermore the
distribution of $(\mathbb{T},{o},\mathbb{M})$ is explicitly described in
Proposition 9 (ii).

######  Remark.

As often with unimodular local limits, we also get a similar statement when
the graphs are rooted at a uniform oriented edge. See Section 2 for precise
statements.

The description of $\mathbb{M}$ given in Proposition 9 (ii) relies on the
belief propagation mentioned above. In the setting of finite trees, this
procedure always constructs an optimal matching. A good portion of this work,
done in Section 3 is then to show that the same procedure produces an optimal
random matching when it is applied to a weighted UBGW tree. The second
important step, done in Section 4, is to show that it is possible to exhibit a
matching of the (large) finite graph whose average weight per vertex is close
to the performance of the limit as defined in (1).

To gain more insight into the belief propagation procedure and our results, we
introduce informally the belief variables $Z(u,v)$ associated with oriented
edges $(u,v)$ of a finite deterministic tree $T$. This will be done in detail
in Section 3.1. Each variable $Z(u,v)$ captures the gain of allowing $v$ to be
matched in $T_{v}$, the connected component of $T\setminus\\{\\{u,v\\}\\}$
containing $v$. When $T_{v}$ is finite, this corresponds to the difference
between the maximal weight of a matching of $T_{v}$ and the maximal weight of
a matching of $T_{v}\setminus\\{v\\}$. From this, we can deduce the so-called
decision rule of the belief propagation procedure:

$\displaystyle\\{u,v\\}\in\mathbb{M}\Leftrightarrow Z(u,v)+Z(v,u)<w(u,v).$ (2)

We will also see that the tree structure induces the following recursive
equation for the belief variables:

$Z(u,v)=\max\left(0\,,\,\max_{\begin{subarray}{c}u^{\prime}\sim v\\\
u^{\prime}\neq
u\end{subarray}}\left(w(v,u^{\prime})-Z(v,u^{\prime})\right)\right).$ (3)

In a UBGW tree whose reproduction law $\pi$, this translates into the
following equation in law

$Z\overset{\text{(law)}}{=}\max\left(0,\max_{1\leq i\leq
N}\left(w_{i}-Z_{i}\right)\right),$ (4)

where $N\sim\hat{\pi}$, the $w_{i}$’s and the $Z_{i}$’s are all independent,
$w_{i}\sim\omega$ and $Z_{i}\sim Z$. As we will see, it is not very hard to
show that this equation in law always has a solution, but the question of the
uniqueness of the solution is trickier. In fact we were unable to prove it by
conventional methods. We will come back to this in a few lines.

One of the main advances of the present work is that the matching $\mathbb{M}$
constructed from any solution of (4) by the decision rule is optimal. Our
proof of this claim is inspired by Aldous’ work [3] on the Poisson Weighted
Infinite Tree (PWIT). However, we work in the more general context of
unimodular random trees, and one of our main difficulty is that, contrary to
Aldous’ work, we deal with partial matchings rather than perfect matchings.
Furthermore, there is no explicit solution to Equation (4). We overcome these
two difficulties by introducing self-loops in Subsection 3.2 and by proving
just enough properties on solutions to Equation (4) to allow us to conclude.

The second main contribution of Theorem 1, proved in Subsections 3.3 and 3.4,
is that the law of $\mathbb{M}$ is unique and does not depend on the
particular solution used. This bypasses previous restrictions on the belief
propagation approach as in Gamarnik, Nowick and Swirscsz [7], Aldous and
Steele [1] or Aldous and Bandyopadhyay [4] that mostly required the variables
$Z(u,v)$ to be measurable with respect to the tree.

The last step in proving Theorem 1 is to construct almost optimal matchings of
finite graphs from an optimal matching $\mathbb{M}$ on their limiting tree.
This is the purpose of section 4. A similar program has already been carried
out by Aldous in the special case of the random assignment problem in
bipartite graphs [2].

Let us come back to the uniqueness in law of the solution to Equation (4). As
mentioned, we are not able to prove it directly and, quite surprisingly, we
need the uniqueness of the optimal matching in Theorem 1 to establish it
(under mild assumptions on the weights). This is formulated in the following
theorem, proved in Section 5. Conversely, we emphasise that assuming
uniqueness of the solution of Equation (4) does not help in proving Theorem 1.

######  Theorem 2.

Let $\omega$ be a non atomic law such that there exists
$a<\sup(\mathrm{supp}(\omega))$ such that
$\left[a,\sup(\mathrm{supp}(\omega))\right)\subseteq\mathrm{supp}(\omega)$.
Let $\hat{\pi}$ be a law on natural integers that has finite expectation. Then
there is a unique law $\zeta$ satisfying:

$Z\overset{\text{(law)}}{=}\max\left(0,\max_{1\leq i\leq
N}\left(w_{i}-Z_{i}\right)\right),$

where $N\sim\hat{\pi}$, the $w_{i}$’s and the $Z_{i}$’s are all independent,
$w_{i}\sim\omega$ and $Z_{i},Z\sim\zeta$.

Theorem 1 describes the full local geometry of the optimal matching. In
particular, it can be used to obtain the asymptotic weight and density of the
optimal matching on the sequence of graphs:

######  Corollary 3.

Let $G_{n}=(V_{n},E_{n},w_{n},o_{n})$ be a sequence of uniformly rooted
weighted graphs as in Theorem 1. Take Z and Z’ to be independent copies of
random variables satisfying (4) and $W$ with law $\omega$ independent of $Z$
and $Z^{\prime}$. One has

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{E}\left[\frac{\sum_{e\in\mathbb{M}_{\mathrm{opt}}(G_{n})}w(e)}{|E_{n}|}\right]$
$\displaystyle=\mathbb{E}[w(o)\mathbbm{1}_{o\in\mathbb{M}}]=\mathbb{E}\left[W\mathbbm{1}_{Z+Z^{\prime}<W}\right],$
(5)
$\displaystyle\lim_{n\rightarrow\infty}\mathbb{E}\left[\frac{\left|E\left(\mathcal{M}_{\mathrm{opt}}(G_{n})\right)\right|}{|E_{n}|}\right]$
$\displaystyle=\mathbb{E}[\mathbbm{1}_{o\in\mathbb{M}}]=\mathbb{E}\left[\mathbbm{1}_{Z+Z^{\prime}<W}\right]=\frac{1-\phi(\hat{\phi}^{-1}(\mathbb{P}(Z=0))}{\phi^{\prime}(1)}.$
(6)

Notice that (6) is the probability that a uniform edge is in the optimal
matching. It could also be stated as the probability that a uniform vertex is
in the matching:

$\lim_{n\rightarrow\infty}\mathbb{E}\left[\frac{\left|V\left(\mathcal{M}_{\mathrm{opt}}(G_{n})\right)\right|}{|V_{n}|}\right]=1-\phi\left(\hat{\phi}^{-1}(\mathbb{P}(Z=0))\right).$

We can also establish a conditional version of this statement:

######  Corollary 4.

Let $G_{n}=(V_{n},E_{n},w_{n},o_{n})$ be a sequence of uniformly rooted
weighted graphs as in Theorem 1. Recall that $o_{n}$ is a uniform vertex of
$G_{n}$. One has

$\lim_{n\rightarrow\infty}\mathbb{P}\left(o_{n}\in
V\left(\mathbb{M}_{\mathrm{opt}}(G_{n})\right)\middle|\deg(o_{n})=k\right)=1-\left(\hat{\phi}^{-1}(\mathbb{P}(Z=0))\right)^{k}.$
(7)

The article is organised as follows. In Section 2, we introduce the notions of
unimodular matchings and unimodular graphs. Section 3 carries out the study of
optimal matchings on the limiting tree. In Section 4 we construct almost
optimal matchings on finite graphs from their optimal infinite counterparts.
In Section 5, we use the results established in the previous two sections to
prove the two main theorems. Finally, Section 6 covers corollaries of Theorem
1 and a few adjacent problems to maximum matching on which this method also
works.

##### Acknowledgements.

L.M.’s research is supported by the ANR grant ProGraM (ANR-19-CE40-0025). V.P.
acknowledges the support of the ANR through the grant DOOM (ANR-23-CE23-0002)

###### Contents

  1. 1 Introduction
  2. 2 Unimodular matched random graphs
    1. 2.1 Unimodular rooted graphs
    2. 2.2 Correspondance between vertex-rooted and edge-rooted unimodularity
    3. 2.3 Matchings, optimality and unimodularity
  3. 3 Optimal unimodular matching on unimodular BGW trees
    1. 3.1 A message passing algorithm
    2. 3.2 Adding self-loops
    3. 3.3 Optimality
    4. 3.4 Uniqueness
  4. 4 From infinite to finite
    1. 4.1 Local convergence of subsequences
    2. 4.2 Optimality of limits of subsequences
      1. 4.2.1 Score function on edges of finite graphs
      2. 4.2.2 Proof of the second part of Proposition 16
      3. 4.2.3 Proof of the technical lemmas
  5. 5 Proof of the main results
    1. 5.1 Convergence of optimally matched graphs (Theorem 1)
    2. 5.2 Uniqueness of the message passing distribution (Theorem 2)
  6. 6 Applications
    1. 6.1 Optimal matching performance and density
    2. 6.2 Exponential edge weights
    3. 6.3 Extensions
      1. 6.3.1 Multi-type UBGW tree and Stochastic Block Model
      2. 6.3.2 Vertex weights
      3. 6.3.3 Maximum subgraph satisfying random capacity constraints

##  2 Unimodular matched random graphs

The goal of this section is to define precisely the objects we are working on,
and the precise notions of optimality for matchings and local convergence we
will use. The key concept is unimodularity for rooted graphs. Depending on the
context, it is often easier to work either with graphs rooted at a vertex or
with graphs rooted at an oriented edge. We will present both cases, as well as
the classical correspondence between the two points of view. For a more
complete exposition on the subject, we refer the reader to [5].

Finally, we will focus on unimodular matchings and a concept of optimality
with respect to a natural performance for vertex-rooted or edge-rooted graphs.
We will see that the correspondence mentioned above conserves our notions of
optimality.

###  2.1 Unimodular rooted graphs

We will work on rooted weighted graphs defined as follows.

######  Definition 2.1.

Let $G=(V,E)$ be a (locally finite) graph and $w$ be a function from $E$ to
$\mathbb{R}$. We that $(G,o,w)$ is

  * •

a _vertex-rooted weighted graph_ if $o\in V$,

  * •

an _edge-rooted weighted graph_ if $o\in\overset{\rightarrow}{E}$, the set of
directed edges.

It will be useful to add decorations to our graphs: we allow the existence of
additional functions $(f_{i})_{i\in\\{1..I\\}}$ that map $E$ or
$\overset{\rightarrow}{E}$ to $\mathbb{R}$. The integer $I$ will typically be
no larger than $4$.

######  Definition 2.2.

Let $(G,o,w)$ be a vertex-rooted (resp. edge-rooted) weighted graph. Fix $I$
an integer and $(f_{i})_{i\in\\{1...I\\}}$ some functions from $E$ or
$\overset{\rightarrow}{E}$ to $\mathbb{R}$. We say that
$(G,o,w,(f_{i})_{i\in\\{1,...I\\}})$ is a _decorated_ vertex-rooted (resp.
edge-rooted) weighted graph.

Let us name $\mathcal{G}^{*}$ the space of locally finite decorated vertex-
rooted weighted graphs. We will write $\mathcal{L}(\mathcal{G}^{*})$ for the
space of laws on this space. Similarly, we denote by $\hat{\mathcal{G}}^{*}$
and $\mathcal{L}(\hat{\mathcal{G}}^{*})$ the corresponding edge-rooted space
and laws. When we do not need to keep track of the weights, root, or some
decorations of the graphs, we will denote elements of $\mathcal{G}^{*}$
indifferently by $G$, $(G,o)$, $(G,o,w)$,
$(G,o,w,(f_{i})_{i\in\\{1,...I\\}})$, …, keeping only the quantities we are
currently interested in.

######  Remark.

The labels of the vertices being of no importance we work up graph
isomorphism.

We now introduce the notion of unimodularity, which translates the intuition
that the choice of the root is uniform for some random graph $\mathbb{G}$ even
when the graph is infinite. To this end, we introduce the space of doubly
rooted graphs up to isomorphism $\mathcal{G}^{**}$ which is defined similarly
as before but with two distinguished roots. It will be simpler to give
specific definitions for vertex and edge-rooted graphs.

######  Definition 2.3 (Vertex-rooted unimodularity).

We say that a probability measure $\mu$ on decorated vertex-rooted graphs is
unimodular if the following statement holds for every
$f:\mathcal{G}^{**}\mapsto\mathbb{R}_{+}$:

$\int_{\mathcal{G}^{*}}\left(\sum_{v\in
V(G)}f(G,o,v)\right)\,\mathrm{d}\mu(G,o)=\int_{\mathcal{G}^{*}}\left(\sum_{v\in
V(G)}f(G,v,o)\right)\,\mathrm{d}\mu(G,o).$

The subspace of unimodular laws on vertex rooted-graph will be noted
$\mathcal{L}_{U}(\mathcal{G}^{*})$

The definition can be written alternatively as

$\mathbb{E}_{(\mathbb{G},\mathbf{o})\sim\mu}\left[\sum_{v\in
V(G)}f(\mathbb{G},\mathbf{o},v)\right]=\mathbb{E}_{(\mathbb{G},\mathbf{o})\sim\mu}\left[\sum_{v\in
V(G)}f(\mathbb{G},v,\mathbf{o})\right].$

For edge-rooted graphs, we will use the following definition:

######  Definition 2.4 (Edge-rooted unimodularity).

Let $\hat{\mu}$ be a probability measure on decorated edge-rooted graphs. Let
$(\mathbb{G},(\mathbf{o}_{-},\mathbf{o}_{+}))$ be a random edge-weighted
decorated graph with law $\hat{\mu}$. Let $\overset{\rightarrow}{e}_{1}$ be a
uniformly picked directed edge of the form $(\mathbf{o}_{+},\mathbf{v})$ for
$\mathbf{v}\neq\mathbf{o}_{-}$. We say that $\hat{\mu}$ is:

  * •

stationary if
$(\mathbb{G},(\mathbf{o}_{-},\mathbf{o}_{+}))\overset{\mathcal{L}}{=}(\mathbb{G},\overset{\rightarrow}{e}_{1})$

  * •

revertible if
$(\mathbb{G},(\mathbf{o}_{-},\mathbf{o}_{+}))\overset{\mathcal{L}}{=}(\mathbb{G},(\mathbf{o}_{+},\mathbf{o}_{-}))$

  * •

unimodular if it is both revertible and stationary.

The subspace of unimodular laws on edge-rooted graphs will be noted
$\mathcal{L}_{U}(\hat{\mathcal{G}}^{*})$

To simplify notation, we will say that a random rooted graph (as a random
variable) is unimodular when its corresponding law is.

######  Remark.

Fix $G$ a finite deterministic graph, and let $\mathbf{o}$ be a random vertex
(resp. oriented edge). It is straightforward to check that $(G,\mathbf{o})$ is
unimodular iff $\mathbf{o}$ is uniform. Hence, unimodular graphs can be viewed
as generalisations of uniformly rooted graphs.

###  2.2 Correspondance between vertex-rooted and edge-rooted unimodularity

In this section, we present the classical transformation that maps a
unimodular vertex-rooted graph into a unimodular edge-rooted graph.
Heuristically, to transform a graph rooted at a uniform vertex into a graph
rooted at a uniformly oriented edge, one has to pick an oriented edge starting
at its root vertex, but this induces a bias by the degree of the root vertex.
This bias has to be taken into account to conserve unimodularity. This is done
in the following.

######  Definition 2.5.

Take $\mu_{v}\in\mathcal{L}(\mathcal{G}^{*})$ such that
$m=\int_{\mathcal{G}^{*}}\deg(o)\,\mathrm{d}\mu_{v}(G,o)<\infty$. Let
$R(\mu_{v})\in\mathcal{L}(\hat{\mathcal{G}}^{*})$ be the unique measure such
that, for every $f$ measurable from $\hat{\mathcal{G}}^{*}$ to
$\mathbb{R}_{+}$,

$\int_{\hat{\mathcal{G}}^{*}}f(G,(o_{-},o_{+}))\,\mathrm{d}R(\mu_{v})(G,(o_{-},o_{+}))=\int_{\mathcal{G}*}\frac{1}{m}\sum_{u\sim
o}f(G,o,u)\,\mathrm{d}\mu_{v}(G,o).$

######  Remark.

The operator $R$ is the composition of two transformations. The first operator
consists on choosing a uniform oriented edge started at the root vertex,
giving a measure $R_{1}(\mu_{v})\in\mathcal{L}(\hat{\mathcal{G}}^{*})$:

$\int_{\hat{\mathcal{G}}^{*}}f(G,(o_{-},o_{+}))\,\mathrm{d}R_{1}(\mu_{v})(G,(o_{-},o_{+})))=\int_{\mathcal{G}*}\frac{1}{\deg(o)}\sum_{u\sim
o}f(\textbf{}G,o,u)\,\mathrm{d}\mu_{v}(G,o).$

The second step is then to cancel the biais by the degree of the vertex,
giving $R(\mu_{v})=R_{2}\circ
R_{1}(\mu_{v})\in\mathcal{L}(\hat{\mathcal{G}}^{*})$:

$\int_{\hat{\mathcal{G}}^{*}}f(G,(o_{-},o_{+}))\mathrm{d}R_{2}\circ
R_{1}(\mu_{v})(G,(o_{-},o_{+}))=\int_{\hat{\mathcal{G}}^{*}}\frac{\deg(o_{-})}{m}f(G,(o_{-},o_{+}))\,\mathrm{d}R_{1}(\mu_{v})(G,(o_{-},o_{+})).$

The following proposition links vertex unimodularity and edge unimodularity.

######  Proposition 5 (Theorem 4.1 in [5]).

Let $\mu_{v}\in\mathcal{L}(\mathcal{G}^{*})$ such that
$m=\int_{\mathcal{G}^{*}}\deg(o)\,\mathrm{d}\mu_{v}(G,o)<\infty$. Then the
measure $\mu_{v}$ is unimodular if and only if $R(\mu_{v})$ is unimodular.

We finish this Section with the classical example of unimodular Bienaymé-
Galton-Watson trees (UGBW), seen from both points of view and without weights.
In either case, the weighted version with weight law $\omega$ corresponds to
drawing $(w(e))_{e\in E}$ independently of law $\omega$.

######  Example 2.1 (Unimodular Bienaymé Galton Watson trees)

Let $\pi$ be a probability measure on $\mathbb{N}=\\{0,1,...\\}$ with finite
expectation $m>0$. Let $\hat{\pi}$ be the size-biased version of $\pi$, that,
$\forall k\geq 0$, $\hat{\pi}(k)=\frac{k}{m}\pi(k)$.

In the introduction, we defined the Unimodular Bienaymé Galton Watson Tree
(what we will shorten as UBGW tree) with reproduction law $\pi$. It is the
random tree $\mathbb{T}$ with the following law:

  * •

The number of children of vertices of $\mathbb{T}$ are all independent.

  * •

The number of children of the root $o$ is distributed according to $\pi$.

  * •

Every non-root vertex has a number of children distributed according to
$\hat{\pi}$, the sized biased version of $\pi$.

The random tree $(\mathbb{T},o)$ is a vertex-rooted unimodular random graph.
See Figure 1 for an illustration.

$\pi$$\hat{\pi}$$\hat{\pi}$$o$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$
Figure 1: A $3-$Neighbourhood of a vertex-rooted UBGW tree with the law of the
number of children drawn on every vertex.

The corresponding edge-rooted UBGW tree has a very simple description. Take
two independent copies of Bienaymé-Galton-Watson trees with offspring
distribution $\hat{\pi}$ with respective root vertex $o_{-}$ and $o_{+}$, and
connect their roots by the oriented edge $(o_{-},o_{+})$. The resulting random
tree $(\hat{\mathbb{T}},(o_{-},o_{+}))$ is an edge-rooted unimodular random
graph. See Figure 2 for an illustration.

$o_{-}$$o_{+}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$$\hat{\pi}$
Figure 2: A 2-Neighbourhood of an edge-rooted UBGW tree with the law of the
number of children drawn on every vertex.

Note that UGBW trees are the limits in law for the local topology of random
configuration graphs with iid degrees sampled for $\pi$, and rooted uniformly
at a vertex or a directed edge.

###  2.3 Matchings, optimality and unimodularity

We start with the definition of matchings on a graph.

######  Definition 2.6.

For any weighted graph $G=((V,E),w)$, a matching $M=(V^{\prime},E^{\prime})$
on $G$ is a subgraph of $G$ in the sense $V=V^{\prime}$ and $E^{\prime}\subset
E$, such that every vertex of $V$ belongs to at most one edge of $E^{\prime}$.
A matched graph is a pair $(G,M)$, where $M$ is a matching on $G$.

We can extend the notion of unimodularity for random graphs to random matched
graphs by assimilating a matching to a decoration.

######  Definition 2.7.

Let $(\mathbb{G},\mathbb{M},\mathbf{o})$ be a random matched rooted graph. We
say that $(\mathbb{G},\mathbb{M},\mathbf{o})$ is unimodular iff
$(\mathbb{G},\mathbf{o},\mathbbm{1}_{\mathbb{M}})$ is. By convention, we will
append the matching as the final decoration.

######  Remark.

Note that this definition does not require that the matching is measurable
with respect to the graph. This will be important in the sequel.

The central objects of this work are optimal matchings. For finite graphs,
this corresponds to the classical notion of maximum weighted matching. When
$G$ is infinite, this optimality is ill-defined. However, in the case of a
unimodular random weighted graph, since the root edge is informally a typical
edge, we can define optimality via its weight when it is in the matching. This
leads to the following definition:

######  Definition 2.8.

Let $(\mathbb{G},\mathbf{o},\mathbb{M},)$ be a unimodular random matched
rooted graph, we define the performance of
$(\mathbb{G},\mathbf{o},\mathbb{M})$ as:

$\displaystyle\operatorname{perf_{E}}(\mathbb{G},\mathbf{o},\mathbb{M})$
$\displaystyle:=\mathbb{E}\left[w((\mathbf{o}_{-},\mathbf{o}_{+}))\mathbbm{1}_{(\mathbf{o}_{-},\mathbf{o}_{+})\in\mathbb{M}}\right]\text{
in the edge-rooted setting,}$
$\displaystyle\operatorname{perf_{V}}(\mathbb{G},\mathbf{o},\mathbb{M})$
$\displaystyle:=\mathbb{E}\left[\sum_{v\sim
o}w(\mathbf{o},v)\mathbbm{1}_{(\mathbf{o},v)\in\mathbb{M}}\right]\text{in the
vertex-rooted setting.}$

When the context is clear, we will just shorten the notation to
$\operatorname{perf}(\mathbb{M})$. By extension, since those quantities only
depend on the law of $(\mathbb{G},\mathbf{o},\mathbb{M})$, we will freely use
the same notation
$\operatorname{perf_{E}}(\mu_{o,m}):=\operatorname{perf_{E}}(\mathbb{G},\mathbb{M})$
for $(\mathbb{G},\mathbf{o},\mathbbm{1}_{\mathbb{M}})\sim\mu_{o,m}$ and
$\operatorname{perf_{V}}(\mu_{v,m}):=\operatorname{perf_{V}}(\mathbb{G},\mathbb{M})$
for $(\mathbb{G},\mathbf{o},\mathbbm{1}_{\mathbb{M}})\sim\mu_{v,m}$ where
$\mu_{e,m}\in\mathcal{L}_{U}(\hat{\mathcal{G}}^{*})$ satisfies that the last
decoration defines a matching almost surely and the same for
$\mu_{v,m}\in\mathcal{L}_{U}(\mathcal{G}^{*})$.

Let $(\mathbb{G},\mathbf{o})$ be a (undecorated) unimodular vertex-rooted
graph. We say that $(\mathbb{G}^{\prime},\mathbf{o},\mathbb{M})$ is optimal if
it is a unimodular matched vertex-rooted graph such that

  * •

$(\mathbb{G}^{\prime},\mathbf{o}^{\prime})$ has the same law as
$(\mathbb{G},\mathbf{o})$

  * •

$\operatorname{perf_{V}}((\mathbb{G}^{\prime},\mathbf{o}^{\prime}),\mathbb{M})$
is maximal.

######  Remark.

This formulation may seem a bit complicated but it is possible that
$\mathbb{M}$ is not measurable with respect to $(\mathbb{G},\mathbf{o})$. We
thus allow resampling to avoid dealing with this difficulty.

In the edge-rooted setting, we can define optimality similarly. The next
proposition shows that the operator $R$ preserves optimality.

######  Proposition 6.

Let $\mu_{v,m}\in\mathcal{L}_{U}(\mathcal{G}^{*})$ such that the last
decoration defines a matching almost surely, assume
$m=\int_{\mathcal{G}^{*}}\deg(o)\,\mathrm{d}\mu_{v}(G,o)<\infty$. Recall the
operator $R$ of Definition 2.5, then:

$\operatorname{perf_{V}}(\mu_{v,m})=m\operatorname{perf_{E}}(R(\mu_{v,m})).$

######  Remark.

If the graph is finite and the root is chosen uniformly among the vertices or
the directed edges, then $\operatorname{perf_{V}}$ is simply the average
contribution per vertex, and $\operatorname{perf_{E}}$ is the average
contribution per directed edge. It is then clear that the two quantities are
proportional. The proposition shows that it generalises to unimodular matched
graphs.

###### Proof.

We will decompose both quantities with respect to the degree of the root, let
us write $(\mathbb{G},o,\mathbbm{1}_{\mathbb{M}})\sim\mu_{v,m}$ and
$(\hat{\mathbb{G}},(o_{-},o_{+}),\mathbbm{1}_{\hat{\mathbb{M}}})\sim
R(\mu_{v,m})$. In the edge-rooted case, we get:

$\sum_{k=1}^{\infty}\mathbb{E}[w((o_{-},o_{+}))\mathbbm{1}_{(o_{-},o_{+})\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}].$

In the vertex-rooted case, we get :

$\sum_{k=0}^{\infty}\mathbb{E}\left[\sum_{v\sim
o}w(o,v)\mathbbm{1}_{(o,v)\in\mathbb{M}}\mathbbm{1}_{\deg(o)=k}\right].$

The $0$ term in the second sum is zero, it then suffices to show that the
$k^{\text{th}}$ term of each sum is proportional by a factor
$\mathbb{E}[\deg(o)]$. Namely, for $k>0$,

$\mathbb{E}\left[\sum_{v\sim
o}w(o,v)\mathbbm{1}_{(o,v)\in\mathbb{M}}\mathbbm{1}_{\deg(o)=k}\right]=\mathbb{E}[\deg(o)]\mathbb{E}\left[w(o_{-},o_{+})\mathbbm{1}_{(o_{-},o_{+})\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}\right].$

First, let us show that

$\mathbb{E}\left[w(o_{-},o_{+})\mathbbm{1}_{(o_{-},o_{+})\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}\right]=\frac{1}{k}\mathbb{E}\left[\sum_{v\sim
o_{-}}w(o_{-},v)\mathbbm{1}_{(o_{-},v)\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}\right].$

For this purpose, we use reversibility to show that:

$\mathbb{E}\left[w(o_{-},o_{+})\mathbbm{1}_{(o_{-},o_{+})\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}\right]=\mathbb{E}\left[w(o_{+},o_{-})\mathbbm{1}_{(o_{+},o_{-})\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{+})=k}\right].$

Then use the 1-step stationarity to show that:

$\mathbb{E}\left[w(o_{+},o_{-})\mathbbm{1}_{(o_{+},o_{-})\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{+})=k}\right]=\mathbb{E}\left[\frac{1}{k-1}\sum_{\begin{subarray}{c}v\sim
o_{-}\\\ v\neq
o_{+}\end{subarray}}w(o_{-},v)\mathbbm{1}_{(o_{-},v)\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}\right].$

Hence:

$\displaystyle\mathbb{E}\left[\sum_{v\sim
o_{-}}w(o_{-},v)\mathbbm{1}_{(o_{-},v)\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}\right]$
$\displaystyle\quad=\mathbb{E}\left[\sum_{\begin{subarray}{c}v\sim o_{-}\\\
v\neq
o_{+}\end{subarray}}w(o_{-},v)\mathbbm{1}_{(o_{-},v)\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}\right]+\mathbb{E}\left[w(o_{-},o_{+})\mathbbm{1}_{(o_{-},o_{+})\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}\right]$
$\displaystyle\quad=(k-1)\mathbb{E}\left[w(o_{-},o_{+})\mathbbm{1}_{(o_{-},o_{+})\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}\right]+\mathbb{E}\left[w(o_{-},o_{+})\mathbbm{1}_{(o_{-},o_{+})\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}\right]$
$\displaystyle\quad=k\mathbb{E}\left[w(o_{-},o_{+})\mathbbm{1}_{(o_{-},o_{+})\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}\right].$

Recall that the operator $R$ is the operation of taking $o_{-}=o$, $o_{+}$
uniformly chosen among $v\sim o$, then biasing by $\deg(o)$. Taking
$f=\sum_{v\sim
o_{-}}w(o_{-},v)\mathbbm{1}_{(o_{-},v)\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}$
and applying the definition of bias on $f$:

$\displaystyle\mathbb{E}\left[\sum_{v\sim
o_{-}}w(o_{-},v)\mathbbm{1}_{(o_{-},v)\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}\right]=\frac{1}{\mathbb{E}[\deg(o)]}\mathbb{E}\left[\deg(o)\sum_{v\sim
o}w(o,v)\mathbbm{1}_{(o,v)\in\mathbb{M}}\mathbbm{1}_{\deg(o)=k}\right]$

In this second sum, $\deg(o)\mathbbm{1}_{\deg(o)=k}=k\mathbbm{1}_{\deg(o)=k}$
so it is the same as :

$\frac{k}{\mathbb{E}[\deg(o)]}\mathbb{E}\left[\sum_{v\sim
o}w(o,v)\mathbbm{1}_{(o,v)\in\mathbb{M}}\mathbbm{1}_{\deg(o)=k}\right].$

Putting everything together, we have shown:

$\frac{k}{\mathbb{E}[\deg(o)]}\mathbb{E}\left[\sum_{v\sim
o}w(o,v)\mathbbm{1}_{(o,v)\in\mathbb{M}}\mathbbm{1}_{\deg(o)=k}\right]=k\mathbb{E}\left[w((o_{-},o_{+}))\mathbbm{1}_{(o_{-},o_{+})\in\hat{\mathbb{M}}}\mathbbm{1}_{\deg(o_{-})=k}\right].$

Dividing by $k$ then multiplying by $\mathbb{E}[\deg(o)]$ yields the required
equality. ∎

We state a useful property of unimodular graphs: events that have probability
zero (resp. almost sure) at the root have probability zero (resp. almost sure)
everywhere.

######  Proposition 7.

Let $(\mathbf{G},\mathbf{o})$ be a unimodular graph, let $H>0$ and $f$ be a
positive H-local function on $\mathcal{G}^{*}$ in the sense that if
$(G,o),(G^{\prime},o^{\prime})\in\mathcal{G}^{*}$ such that
$N_{H}(G,o)=N_{H}(G^{\prime},o^{\prime})$, $f(G,o)=f(G^{\prime},o^{\prime})$.
Assume that

$\mathbb{E}\left[f(\mathbf{G},\mathbf{o})\right]=0.$

Then almost surely, for all $v\in\mathbf{V}$

$f(\mathbf{G},v)=0.$

##  3 Optimal unimodular matching on unimodular BGW trees

In this section, we construct optimal matchings on UBGW trees. As mentioned in
the introduction, our construction relies on a message passing algorithm that
we will present and study in depth in Section 3.1. We then prove that the
matchings constructed are optimal in Section 3.3. Finally, we prove the
uniqueness of optimal matchings in UBGW trees in Section 3.4.

###  3.1 A message passing algorithm

_In this subsection, we will adopt the edge-rooted point of view._

Before formally introducing the message passing algorithm mentioned in the
introduction, we start by discussing the simpler setting of finite trees. We
are looking for a dynamic program that builds the maximum matching.

$u$$v$$w(u,v)$$\begin{array}[]{l}Z(u,v)=OPT({\color[rgb]{0.56,0.07,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.56,0.07,1}T_{v}})-OPT({\color[rgb]{0.29,0.56,0.89}\definecolor[named]{pgfstrokecolor}{rgb}{0.29,0.56,0.89}T_{v}\setminus\\{v\\}}).\end{array}$$T_{v}$$T_{u}\setminus\\{u\\}$$T_{u}$${\color[rgb]{0.29,0.56,0.89}\definecolor[named]{pgfstrokecolor}{rgb}{0.29,0.56,0.89}T_{v}\setminus\\{v\\}}$$\begin{array}[]{l}Z(v,u)=OPT({\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}T_{u}})-OPT({\color[rgb]{0.49,0.83,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.49,0.83,0.13}T_{u}\setminus\\{u\\}}).\end{array}$$\begin{array}[]{l}OPT(G)=\text{weight
of}\\\ \text{a maximum matching}\\\ \text{on}\ G.\end{array}$ Figure 3:
Definitions of $Z$.

Fix a finite weighted rooted deterministic tree $T$ with a unique optimal
matching. Let $\\{u,v\\}$ be an edge of $T$, we denote by $T_{u}$ and $T_{v}$
the two connected components of $T\setminus\\{u,v\\}$ containing respectively
$u$ and $v$. Let us start by simple but key observations illustrated in Figure
3:

  * •

The maximal weight of matchings of $T$ that exclude the edge $\\{u,v\\}$ is
merely the sum of the maximal weights of matchings of $T_{u}$ and $T_{v}$,
denoted $OPT(T_{u})$ and $OPT(T_{v})$.

  * •

The maximal weight of matchings that include the edge $\\{u,v\\}$ is the sum
of the weight of $\\{u,v\\}$ and of the maximal weights of matchings of
$T_{u}\setminus\\{u\\}$ and $T_{v}\setminus\\{v\\}$. Note that both
$T_{u}\setminus\\{u\\}$ and $T_{v}\setminus\\{v\\}$ consist of collections of
disjoint subtrees of $T$ issued from the children of $u$ and $v$. We denote by
$OPT(T_{u}\setminus\\{u\\})$ and $OPT(T_{v}\setminus\\{v\\})$ the relevant
maximal weights.

From this discussion, one can see that the edge $\\{u,v\\}$ is in the optimal
matching of $T$ iff

$w(u,v)>OPT(T_{u})+OPT(T_{v})-\Big{(}OPT(T_{u}\setminus\\{u\\})+OPT(T_{v}\setminus\\{v\\})\Big{)}.$

It will be instrumental to isolate quantities depending only on $T_{u}$ and
$T_{v}$ in the previous display. This leads us to introduce the following
quantities

$\displaystyle Z(u,v)$ $\displaystyle=OPT(T_{v})-OPT(T_{v}\setminus\\{v\\}),$
$\displaystyle Z(v,u)$ $\displaystyle=OPT(T_{u})-OPT(T_{u}\setminus\\{u\\}),$

and the criterion of $(u,v)\in\mathbb{M}_{\mathrm{opt}}$ is simply

$w(u,v)>Z(u,v)+Z(v,u).$ (8)

Note that the variable $Z(u,v)$ has a neat interpretation in terms of the
matchings of $T_{v}$. Indeed, it is the marginal gain between allowing $v$ to
be matched or not.

The variables $Z$ have the nice property of satisfying a recursive equation.
We describe this recursion for $Z(u,v)$ and $T_{v}$. See Figure 4 for an
illustration.

Listing $v_{1},...v_{k}$ the children of $v$ in $T_{v}$, assume that the
maximum matching of $T_{v}$ matches $v$ with $v_{i}$. In that situation, the
maximum matching of $T_{v}$ and the maximum matching of
$T_{v}\setminus\\{v\\}$ coincide on the subtrees $T_{v_{j}}$ for $j\neq i$. On
$T_{v_{i}}$, this maximum matching has matched $v_{i}$ with $v$, so $v_{i}$ is
not matched to other vertices. Therefore, our maximum matching on $T_{v}$
restricted to $T_{v_{i}}$ is the union of $\\{v,v_{i}\\}$ with the maximum
matching of $T_{v_{i}}\setminus\\{v_{i}\\}$. In that case, the weight of the
maximal matching is given by:

$w(v,v_{i})+OPT(T_{v_{i}}\setminus\\{v_{i}\\})+\sum_{j\neq i}OPT(T_{v_{j}}).$

On the other hand, if the maximum matching of $T_{v}$ does not match $v$ it is
also the maximum matching in $T_{v}\setminus\\{v\\}$. Thus, inside each sub-
tree $T_{v_{i}}$, it coincides with the maximal matching of $T_{v_{i}}$. In
that case, the weight of the maximal matching is given by:

$\sum_{j}OPT(T_{v_{j}}).$

Putting all the different cases together, we have the identity

$OPT(T_{v})=\max\left\\{\sum_{j}OPT(T_{v_{j}})\,,\max_{i\in\\{1,\ldots,k\\}}\left\\{w(v,v_{i})+OPT(T_{v_{i}}\setminus\\{v_{i}\\})+\sum_{j\neq
i}OPT(T_{v_{j}})\right\\}\right\\}.$

Recalling the definition of $Z(u,v)$, we get:

$\displaystyle Z(u,v)$ $\displaystyle=OPT(T_{v})-\sum_{j}OPT(T_{v_{j}})$
$\displaystyle=\max\left\\{0,\max_{i\in\\{1,\ldots,k\\}}\left\\{w(v,v_{i})-(OPT(T_{v_{i}})-OPT(T_{v_{i}}\setminus\\{v_{i}\\})\right\\}\right\\}$
$\displaystyle=\max\left\\{0,\max_{i\in\\{1,\ldots,k\\}}w(v,v_{i})-Z(v,v_{i})\right\\}.$

In conclusion, we have obtained the recursive equation (3) given in the
introduction.

Note that, since $T$ is a finite tree, it is possible to calculate $Z(u,v)$
for all vertices $u\sim v\in T$ by starting when $v$ is a leaf, in which case
$Z(u,v)=0$. By construction, our decision rule (2) constructs the optimal
matching on $T$ from the values of $Z$.

$v_{i}$$v$$v_{j}$common to both
OPT${\color[rgb]{0.56,0.07,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.56,0.07,1}\text{in
}OPT(T_{v})}$${\color[rgb]{0.29,0.56,0.89}\definecolor[named]{pgfstrokecolor}{rgb}{0.29,0.56,0.89}\text{in}\
OPT(T_{v}\ \setminus\\{v\\})}$ Figure 4: Illustration of the deduction of the
recursive equation.

Now, let us discuss how to extend the construction of variables $Z(u,v)$ when
the underlying tree is a (possibly infinite) UBGW tree. This is not trivial,
since the previous deterministic construction from leaves is impossible when
the tree is infinite. Moreover, it is not clear to us that a solution of the
recursive system (3) on a given random weighted UBGW tree $\mathcal{T}$ can be
constructed measurably. First, if $Z$ exists, then its law must satisfy a
recursive distributional equation, the first lemma below guarantees the
existence of a solution to this equation:

######  Lemma 8.

Let $N$ be a random variable with law $\hat{\pi}$ and
$(w_{k})_{k\in\mathbb{N}}$ be a sequence of i.i.d. random variables with law
$\omega$, independent of $N$. Then there exists a law $\zeta$ such that for
all sequence $(Z_{k})_{k\geq 0}$ i.i.d of law $\zeta$ and independent of $N$
and of the sequence $(w_{k})_{k\in\mathbb{N}}$, the following equality in law
holds:

$Z_{0}\overset{\mathrm{(law)}}{=}\max(0,\max_{1\leq i\leq N}(w_{i}-Z_{i})).$

###### Proof.

Let us express the invariance of $\zeta$ in terms of its cumulative
distribution function $h$. Let us call $\hat{\phi}$ the generating function of
$\hat{\pi},\hat{\phi}(x)=\sum_{k=0}^{\infty}\mathbb{P}(N=k)x^{k}=\sum_{k=0}^{\infty}\hat{\pi}_{k}x^{k}$.

Let $t\in\mathbb{R}$,

$\displaystyle h(t)$ $\displaystyle=\mathbb{P}(Z_{0}\leq
t)=\mathbb{P}\left(\max(0,\max_{1\leq i\leq N}(w_{i}-Z_{i}))\leq t\right)$
$\displaystyle=\mathbbm{1}_{t\geq 0}\mathbb{P}\left(\forall i\leq
N,w_{i}-Z_{i}\leq t\right)$ $\displaystyle=\mathbbm{1}_{t\geq
0}\sum_{k=0}^{\infty}\hat{\pi}_{k}\mathbb{P}(Z_{i}\geq w_{i}-t)^{k}$
$\displaystyle=\mathbbm{1}_{t\geq
0}\sum_{k=0}^{\infty}\hat{\pi_{k}}(1-\mathbb{E}[h_{-}(w_{1}-t)])^{k}$
$\displaystyle=\mathbbm{1}_{t\geq 0}\hat{\phi}(1-\mathbb{E}[h_{-}(w_{1}-t)])$

where for all real $x$, we define $h_{-}(x)$ as the left limit of $h$ at $x$.

The invariance of $\zeta$ is equivalent to:

$\forall t\in\mathbb{R},\quad h(t)=\mathbbm{1}_{t\geq
0}\hat{\phi}(1-\mathbb{E}[h_{-}(w_{1}-t)]).$ (9)

Our goal is to apply Schauder’s fixed point theorem on the subspace $X$ of
non-decreasing functions of $\mathbb{R}\mapsto[0,1]$ equipped with the product
topology of $\mathbb{R}^{\mathbb{R}}$. The space $X$ is closed and contained
in the compact space $[0,1]^{\mathbb{R}}$ (by Tychonoff’s theorem) so $X$ is
compact. It is also convex, so it is a compact convex subspace of
$\mathbb{R}^{\mathbb{R}}$ that is a Hausdorff topological vector space. Let us
define the map

$\displaystyle\mathrm{F}\colon X$ $\displaystyle\rightarrow X$ $\displaystyle
f$ $\displaystyle\mapsto\mathrm{F}(f)\colon{}$ $\displaystyle\mathbb{R}$
$\displaystyle\rightarrow[0,1]$ $\displaystyle t$
$\displaystyle\mapsto{}\mathbbm{1}_{t\geq
0}\hat{\phi}(1-\mathbb{E}[f_{-}(w_{1}-t)])$

By dominated convergence theorem, the map $\mathrm{F}$ is a continuous map
from $X$ into itself. Hence, Schauder’s fixed point theorem implies that there
exists a function $f_{0}\in X$ such that $\mathrm{F}(f_{0})=f_{0}$. To
conclude we just need to verify that the image $\mathrm{F}(X)$ is contained in
the subspace of cadlag functions. Since elements of $X$ are non-decreasing,
the fact that they admit left limits is obvious, we just need to show that any
element of $\mathrm{F}(X)$ is right-continuous, that is for any increasing map
$f$, the map $t\mapsto\mathbbm{1}_{t\geq
0}\hat{\phi}(1-\mathbb{E}[f_{-}(w_{1}-t)])$ is right continuous. It is just a
consequence of the left continuity of $f_{-}$ combined with the dominated
convergence theorem. ∎

The proof of Lemma 8 is not constructive and we do not know of a construction
for the variables $Z$ that is measurable in terms of the tree and that
satisfies the recursion (3), except in specific examples (e.g. finite trees).
Still, we will see in the next proposition that for any law $\zeta$ given by
the previous lemma, we can resample a pair $(\mathcal{T}^{\prime},Z_{h})$
satisfying:

  * •

The family $Z_{h}$ is a solution of (3) on $\mathcal{T}^{\prime}$.

  * •

For all $(u,v)\in\overset{\rightarrow}{E^{\prime}}$ the variable $Z_{h}(u,v)$,
in average over $T_{v}$, is distributed according to $\zeta$.

  * •

The first marginal $\mathcal{T}^{\prime}$ has the same law as $\mathcal{T}$.

This is possible even if we take into account unimodular decorations on
$\mathcal{T}$, a unimodular matching for example. This will be instrumental in
proving the uniqueness of the law of the optimal matching on $\mathcal{T}$
since we will need to compare any unimodular matching to the one obtained by
the decision rule (2) obtained from the family $Z_{h}$.

######  Proposition 9.

Let $h$ be a solution to Equation (9) and let $\zeta_{h}$ be a law associated
with $h$ and solution to (4). Let $\mathbb{T}$ be a unimodular decorated
weighted UBGW tree with reproduction law $\pi$ and weights law $\omega$ (for
example, $\mathbb{T}=(\mathcal{T},\mathbbm{1}_{\mathbb{M}})$, where
$\mathcal{M}$ is a matching of $\mathcal{T}$).

  1. (i)

There exists a random decorated tree
$(\mathbb{T}^{\prime},Z_{h}(u,v)_{(u,v)\in\overset{\rightarrow}{E^{\prime}}})$
such that the law of $\mathbb{T}^{\prime}$ is the law of $\mathbb{T}$, each
$Z_{h}(u,v)$, in average over $T_{v}$, has law $\zeta_{h}$ and such that for
every $(u,v)\in\overset{\rightarrow}{E^{\prime}}$:

$Z_{h}(u,v)=\max\left\\{0,\max_{\begin{subarray}{c}u^{\prime}\sim v\\\
u^{\prime}\neq
u\end{subarray}}\left\\{w(v,u^{\prime})-Z_{h}(v,u^{\prime})\right\\}\right\\}.$

  2. (ii)

The rule

$\\{u,v\\}\in\mathbb{M}_{h}\Leftrightarrow Z_{h}(u,v)+Z_{h}(v,u)<w(u,v)$

defines a matching $\mathbb{M}_{h}$ on $\mathbb{T}^{\prime}$.

Furthermore, if $\omega$ is non-atomic, this "edge-rule" is equivalent to the
following "vertex-rule":

$\displaystyle v\text{ is the neighbour of }u\text{ in
}\mathbb{M}_{h}\Leftrightarrow v=\operatorname*{argmax}_{v^{\prime}\sim
u}(w(u,v^{\prime})-Z_{h}(u,v^{\prime}))\text{ and }w(u,v)-Z_{h}(u,v)>0.$

In particular, almost surely,

$\displaystyle u\text{ is not matched by
}\mathbb{M}_{h}\Leftrightarrow\max_{v^{\prime}\sim
u}(w(u,v^{\prime})-Z_{h}(u,v^{\prime}))\leq 0.$

  3. (iii)

The random decorated tree
$(\mathbb{T}^{\prime},(Z_{h}(u,v))_{(u,v)\in\overset{\rightarrow}{E^{\prime}}})$
viewed as $\mathbb{T}^{\prime}$ with $Z_{h}$ as an additional decoration is
unimodular.

######  Remark.

Note that we do not claim at this stage the uniqueness of the invariant law
$\zeta$. It turns out that, surprisingly, if $\zeta_{1}$ and $\zeta_{2}$ are
two invariant laws, then the laws of the matchings $\mathbb{M}_{\zeta_{1}}$
and $\mathbb{M}_{\zeta_{2}}$ are equal. We will use this fact to prove the
uniqueness of $\zeta$ as Theorem 2 in Section 5.

We now turn to the proof of the proposition:

###### Proof of Proposition 9.

i) For an illustration of this proof, we refer to Figure 5. Let
$H\in\mathbb{N}^{*}$, recall $N_{H}(\mathbb{T})$ the $H-$neighbourhood of the
root edge of $\mathbb{T}$. We call the depth of a non-oriented edge
$\\{u,v\\}$ its distance to the root edge. Let $E_{k}$ be the set of directed
edges $(u,v)\in\overset{\rightarrow}{E}$ such that the depth of $\\{u,v\\}$ is
$k$ and $(u,v)$ is pointing away from the root. We set $(Z_{h}(u,v))_{(u,v)\in
E_{H}}$ to be independent variables with law $\zeta_{h}$ from the previous
lemma.

We can then use Recursion (3):

$Z_{h}(u,v)=\max(0,\underset{\begin{subarray}{c}w\sim v\\\ w\neq
u\end{subarray}}{\max}(W(v,w)-Z_{h}(v,w)))$

to define $(Z_{h}(u,v)))_{(u,v)\in E_{H-1}}$. By induction, we define every
$Z_{h}(u,v)$ for $(u,v)$ pointing away from the root and then on the edge-root
and its symmetric. We can then define $Z_{h}(u,v)$ on $E_{-1}$ the set of
directed edges pointing towards the root of depth $1$, then by the same
induction, we define them on all $E_{-k}$, the set of directed edges pointing
towards the root of depth $k$, for $k$ running from $1$ to $H$.

In this way, we have defined $Z_{h}(u,v)$ on $N_{H}(\mathbb{T})$, and we can
see that because $\zeta_{h}$ is an invariant law for the RDE, the restriction
of $Z_{h}(u,v)$ to $N_{H-1}(\mathbb{T})$ has the same law as if we defined it
directly on $N_{H-1}(\mathbb{T})$. By Kolmogorov’s extension theorem, we
deduce that there exists a process $(\mathbb{T}^{\prime},Z_{h})$ such that the
first marginal’s law is $\mathbb{T}$ and $Z_{h}$ satisfies Recursion (3) on
$\mathbb{T}^{\prime}$ with the prescribed law.

ii) For an illustration of this proof, refer to Figure 6. We need to show that
for every vertex $u\in V$, there is at most one neighbouring vertex $v\in V$
satisfying Rule (2)

$w(u,v)>Z_{h}(u,v)+Z_{h}(v,u).$

To this end, we will first show the following implication for any
$\\{u,v\\}\in E$

$w(u,v)>Z_{h}(u,v)+Z_{h}(v,u)\Rightarrow\\{v\\}=\operatorname*{argmax}_{v^{\prime}\sim
v}(w(u,v^{\prime})-Z_{h}(u,v^{\prime})).$

Figure 5: Construction of the law of $Z_{h}$ on a $1-$neighbourhood.
$u$$w_{1}$$w_{2}$$w_{3}$${\color[rgb]{0.96,0.65,0.14}\definecolor[named]{pgfstrokecolor}{rgb}{0.96,0.65,0.14}Z}{\color[rgb]{0.96,0.65,0.14}{}_{1}^{{}^{\prime}}}=\max(0,w_{2}-{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z}{\color[rgb]{0.82,0.01,0.11}{}_{2}})$$\begin{array}[]{l}{\color[rgb]{0.96,0.65,0.14}\definecolor[named]{pgfstrokecolor}{rgb}{0.96,0.65,0.14}Z}{\color[rgb]{0.96,0.65,0.14}{}_{2}^{{}^{\prime}}}=\max(0,w_{1}-{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z}{\color[rgb]{0.82,0.01,0.11}{}_{1}})\end{array}$${\color[rgb]{0.96,0.65,0.14}\definecolor[named]{pgfstrokecolor}{rgb}{0.96,0.65,0.14}Z}{\color[rgb]{0.96,0.65,0.14}{}_{3}^{{}^{\prime}}}=\max(0,w_{1}-{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z}{\color[rgb]{0.82,0.01,0.11}{}_{1}})$$\begin{array}[]{l}\text{Suppose
}w_{1}-{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z}{\color[rgb]{0.82,0.01,0.11}{}_{1}}\
>\
w_{2}-{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z}{\color[rgb]{0.82,0.01,0.11}{}_{2}}>w_{3}-{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z}{\color[rgb]{0.82,0.01,0.11}{}_{3}}.\\\
\text{We can see that the}\
{\color[rgb]{0.96,0.65,0.14}\definecolor[named]{pgfstrokecolor}{rgb}{0.96,0.65,0.14}Z_{i}^{{}^{\prime}}}\
\text{pointing towards}\ u\\\ \text{are all equal to }\max_{v\sim
u}(0,w(u,v)-{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z}(u,v))\\\
\text{except for the }v\ \text{hitting that maximum}\\\ \text{in which case
the value is the second
largest.}\end{array}$${\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z_{1}}$${\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z}{\color[rgb]{0.82,0.01,0.11}{}_{2}}$${\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z}{\color[rgb]{0.82,0.01,0.11}{}_{3}}$$v_{1}$$v_{2}$$v_{3}$
Figure 6: Illustration of the behaviour of the $Z_{h}$ around a vertex $u$.

Indeed:

$\displaystyle w(u,v)>Z_{h}(u,v)+Z_{h}(v,u)$ $\displaystyle\Rightarrow$
$\displaystyle
w(u,v)-Z_{h}(u,v)>Z_{h}(v,u)=\max(0,\max_{\begin{subarray}{c}v^{\prime}\sim
u\\\ v^{\prime}\neq v\end{subarray}}(w(u,v^{\prime})-Z_{h}(u,v^{\prime}))).$

This implies that for every neighbour of $u$, $v^{\prime}$ different from $v$,
$w(u,v)-Z_{h}(u,v)>w(u,v^{\prime})-Z_{h}(u,v^{\prime})$, which in turn implies
that $v$ is the unique element of $\operatorname*{argmax}_{v^{\prime}\sim
u}(w(u,v^{\prime})-Z_{h}(u,v^{\prime}))$. Hence the vertex $u$ is matched to
at most one neighbour.

To show the equivalent rule, we only need to show that $u$ is not matched if
and only if $\max_{v^{\prime}\sim u}(w(u,v^{\prime})-Z_{h}(u,v^{\prime}))\leq
0$. For the implication, we have that any incident $Z_{h}(v,u)$ for $v\sim u$
evaluates to zero by applying Recursion (3). So for any $v\sim u$,
$Z_{h}(v,u)+Z_{h}(u,v)=Z_{h}(u,v)$. Since $\max_{v^{\prime}\sim
u}(w(u,v^{\prime})-Z_{h}(u,v^{\prime}))\leq 0$, we deduce that for any
$v^{\prime}\sim u$, $w(u,v^{\prime})\leq Z_{h}(u,v^{\prime})$ , but we have
just seen that $Z_{h}(v^{\prime},u)=0$ hence $w(u,v^{\prime})\leq
Z_{h}(u,v^{\prime})+Z_{h}(v^{\prime},u)$ for any $v^{\prime}\sim u$ so
$v^{\prime}$ is not matched to $u$. Reciprocally, if $u$ is not matched by
$\mathbb{M}_{h}$, then

$\max(0,\max_{\begin{subarray}{c}v^{\prime}\sim u\\\ v^{\prime}\neq
v\end{subarray}}(w(u,v^{\prime})-Z_{h}(u,v^{\prime}))=Z_{h}(v^{\prime},u)\geq
w(u,v^{\prime})-Z_{h}(u,v^{\prime})$

for any $v^{\prime}\sim u$, so the maximum of
$\operatorname*{argmax}_{v^{\prime}\sim
u}(w(u,v^{\prime})-Z_{h}(u,v^{\prime}))$ is not reached by any $v^{\prime}\sim
u$ or there are several $v^{\prime}$ in the $\operatorname*{argmax}$, since
$\omega$ is non-atomic there is almost surely no ties and the $\max$ is not
reached, so $0\geq\max_{v^{\prime}\sim u}(w(u,v^{\prime})-Z_{h}(u,v^{\prime})$
which concludes.

iii) The goal is to show that the law of $Z_{h}$ restricted to a
$H-$neighbourhood of $(o_{+},v)$ with $v$ chosen uniformly among the children
of $o_{+}$ is the same as the law of $Z_{h}$ restricted to the
$H-$neighbourhood of $(o_{-},o_{+})$. Since Recursion (3) is preserved, one
only needs to show that the exterior variables of $Z_{h}$ on the $H-$boundary
of $(o_{+},v)$ are i.i.d variables of law $\zeta_{h}$. The $H-$neighbourhood
of $(o_{+},v)$ is included in the $H+1-$neighbourhood of $(o_{-},o_{+})$ and
can be computed from it. One can check by applying Recursion (3) up to twice
from the $H+1$-boundary of $(o_{-},o_{+})$, that we effectively recover
variables $Z$ on the $H-$boundary of $(o_{+},v)$ that are i.i.d of law
$\zeta_{h}$. $(\mathbb{T},Z_{h})$ is thus stationary.

Clearly, the law of the $Z_{h}$ are also symmetric so changing $(o_{-},o_{+})$
into $(o_{+},o_{-})$ does not change their laws, $(\mathbb{T},Z_{h})$ is thus
reversible. ∎

From now on, despite resampling $\mathbb{T}$ when applying Proposition 9, we
will forgo the notation $\mathbb{T}^{\prime}$ for $\mathbb{T}$ to ease
notations.

We conclude this Section with a technical result we will need later. It deals
with a property of the probability distributions which are solutions of
Equation (4).

######  Lemma 10.

Any law $\zeta_{h}$ defined as a solution of Equation (4) is atomic at zero
and only at zero.

###### Proof.

Let $h$ be any solution to Equation (9). First, let us show that $\zeta_{h}$
is atomic at zero. Evaluate Equation $\eqref{eq:hequation}$ at $0$:

$h(0)=\hat{\phi}(1-\mathbb{E}_{W\sim\omega}[h_{-}(W)]).$

If $\hat{\phi}(0)>0$ we are done, else, assume $\hat{\phi}(0)=0$ and $h(0)=0$.

Because $\hat{\phi}>0$ on $]0,1]$, we deduce that
$\mathbb{E}_{W\sim\omega}[h_{-}(W)]=1$. This implies in particular that
$\inf(\mathrm{supp}(\omega))\geq\sup(\mathrm{supp}(\zeta_{h}))$. Since
$\mathrm{supp}(\zeta_{h})\subset\mathbb{R}_{+}$, this implies that
$\mathrm{supp}(\omega)\subset\mathbb{R}_{+}$ aswell.

Recall equation (9):

$h(t)=\mathbbm{1}_{t\geq
0}\hat{\phi}\left(1-\mathbb{E}_{W\sim\omega}\left[h_{-}(W-t)\right]\right).$

Evaluate this equation at some variable $W^{\prime}$ of law $\omega$, this
yields:

$h(W^{\prime})=\mathbbm{1}_{W^{\prime}\geq
0}\hat{\phi}\left(1-\mathbb{E}_{W\sim\omega}\left[h_{-}(W-W^{\prime})\right]\right)$

We’ve shown previously that $W^{\prime}\geq 0$ almost surely so we can discard
$\mathbbm{1}_{W^{\prime}\geq 0}$. Now take expectation with respect to
$\mathcal{W}^{\prime}$, this yields:

$1=\mathbb{E}_{W^{\prime}\sim\omega}\left[\hat{\phi}\left(1-\mathbb{E}_{W\sim\omega}\left[h_{-}(W-W^{\prime})\right]\right)\right].$

But since $\hat{\phi}<1$ outside of $1$, this implies that almost surely on
$W^{\prime}$,

$\mathbb{E}_{W\sim\omega}[h_{-}(W-W^{\prime})]=0.$

Let $W^{\prime},W^{\prime\prime}$ independent variables each of law $\omega$,
evaluate equation (9) on $W^{\prime}-W^{\prime\prime}$:

$h(W^{\prime}-W^{\prime\prime})=\mathbbm{1}_{W^{\prime}-W^{\prime\prime}\geq
0}\hat{\phi}\left(1-\mathbb{E}_{W\sim\omega}\left[h_{-}(W+W^{\prime\prime}-W^{\prime})\right]\right).$

Taking expectations:

$0=\mathbb{E}\left[\mathbbm{1}_{W^{\prime}-W^{\prime\prime}\geq
0}\hat{\phi}\left(1-\mathbb{E}_{W\sim\omega}\left[h_{-}(W-(W^{\prime}-W^{\prime\prime}))\right]\right)\right].$

So almost surely, either $W^{\prime}-W^{\prime\prime}<0$ or
$\mathbb{E}_{W\sim\omega}[h(W-(W^{\prime}-W^{\prime\prime}))]=1$.
Conditionally on $W^{\prime}-W^{\prime\prime}\geq 0$,
$\mathbb{E}_{W\sim\omega}[h(W-(W^{\prime}-W^{\prime\prime}))]=1$. But $h_{-}$
is non-decreasing so this statement stays true for
$W^{\prime}-W^{\prime\prime}<0$.

So now, taking expectations on $W^{\prime}-W^{\prime\prime}$, we obtained:

$\mathbb{E}(h_{-}(W+W^{\prime\prime}-W^{\prime}))=1.$

We can now then iterate: Let $(W_{i})_{i\in\mathbb{N}^{*}}$ i.i.d variables of
law $\omega$, we will show the following statement by induction:

$\forall
n\in\mathbb{N}^{*},\mathbb{E}\left[h_{-}\left(\sum_{i=1}^{n}W_{2i-1}-\sum_{i^{\prime}=1}^{n-1}W_{2i}\right)\right]=1.$
(10)

The statement holds for $n=2$, assume it holds for some $n\in\mathbb{N}^{*}$.
Evaluate $h$ at $\sum_{i=1}^{n}W_{2i-1}-\sum_{i^{\prime}=1}^{n-1}W_{2i}$, this
yields

$h\left(\sum_{i=1}^{n}W_{2i-1}-\sum_{i^{\prime}=1}^{n-1}W_{2i}\right)=\mathbbm{1}_{\sum_{i=1}^{n}W_{2i-1}-\sum_{i^{\prime}=1}^{n-1}W_{2i}\geq
0}\hat{\phi}\left(1-\mathbb{E}\left[h\left(\sum_{i^{\prime}=1}^{n}W_{2i}-\sum_{i=1}^{n}W_{2i-1}\right)\right]\right).$

where the expectation is over $W_{2n}$.

Now take expectation over $(W_{i})_{i\leq 2n-1}$, by hypothesis the left-hand
side will evaluate to one:

$1=\mathbb{E}\left[\mathbbm{1}_{\sum_{i=1}^{n}W_{2i-1}-\sum_{i^{\prime}=1}^{n-1}W_{2i}\geq
0}\hat{\phi}\left(1-\mathbb{E}\left[h_{-}\left(\sum_{i^{\prime}=1}^{n}W_{2i}-\sum_{i=1}^{n}W_{2i-1}\right)\right]\right)\right].$

We deduce that almost surely on $(W_{i})_{i\leq 2n-1}$,

$\mathbb{E}_{W_{2n}\sim\omega}\left[h_{-}\left(\sum_{i^{\prime}=1}^{n}W_{2i}-\sum_{i=1}^{n}W_{2i-1}\right)\right]=0.$

Now evaluate $h$ on $\sum_{i^{\prime}=1}^{n}W_{2i}-\sum_{i=1}^{n}W_{2i-1}$,
this yields:

$\displaystyle h$
$\displaystyle\left(\sum_{i^{\prime}=1}^{n}W_{2i}-\sum_{i=1}^{n}W_{2i-1}\right)$
$\displaystyle\quad=\mathbbm{1}_{\sum_{i^{\prime}=1}^{n}W_{2i}-\sum_{i=1}^{n}W_{2i-1}\geq
0}\hat{\phi}\left(1-\mathbb{E}\left[h_{-}\left(W_{2n+1}-\left(\sum_{i^{\prime}=1}^{n}W_{2i}-\sum_{i=1}^{n}W_{2i-1}\right)\right)\right]\right),$

where the expectation is over $W_{2n+1}$. Now take expectation over
$(W_{i})_{i\leq 2n}$, the left-hand side evaluates to 0 as we have just shown:

$0=\mathbb{E}\left[\mathbbm{1}_{\sum_{i^{\prime}=1}^{n}W_{2i}-\sum_{i=1}^{n}W_{2i-1}\geq
0}\hat{\phi}\left(1-\mathbb{E}\left[h_{-}\left(W_{2n+1}-\left(\sum_{i^{\prime}=1}^{n}W_{2i}-\sum_{i=1}^{n}W_{2i-1}\right)\right)\right]\right)\right].$

We deduce that:

$\mathbb{P}\left(\mathbb{E}_{W_{2n+1}\sim\omega}\left[h_{-}\left(\sum_{i^{\prime}=1}^{n+1}W_{2i-1}-\sum_{i=1}^{n}W_{2i}\right)\right]=1\middle|\sum_{i^{\prime}=1}^{n}W_{2i}-\sum_{i=1}^{n}W_{2i-1}\geq
0\right)=1.$

Again, since $h_{-}$ is non-decreasing, we can discard the conditioning to
obtain:

$\mathbb{P}\left(\mathbb{E}_{W_{2n+1}\sim\omega}\left[h_{-}\left(\sum_{i^{\prime}=1}^{n+1}W_{2i-1}-\sum_{i=1}^{n}W_{2i}\right)\right]=1\right)=1.$

So taking expectation over $(W_{i})_{i\leq 2n+1}$, we have proven that:

$\mathbb{E}\left[h_{-}\left(\sum_{i^{\prime}=1}^{n+1}W_{2i-1}-\sum_{i=1}^{n}W_{2i}\right)\right]=1.$

As required.

Now Equation (10) implies that:

$\forall
n\in\mathbb{N}^{*},\inf(\mathrm{supp}(\omega))-n\left[\sup(\mathrm{supp}(\omega))-\inf(\mathrm{supp}(\omega))\right]\geq\sup(\mathrm{supp}(\zeta_{h})).$

But since $\omega$ is atomless, $\mathrm{supp}(\omega)$ is not reduced to a
single point so $\sup(\mathrm{supp}(\omega))-\inf(\mathrm{supp}(\omega))>0$.
Taking $n\rightarrow\infty$ then shows that
$-\infty\geq\sup(\mathrm{supp}(\zeta_{h}))$, this is clearly impossible as
$\zeta_{h}$ is a law on $\mathbb{R}_{+}$.

Now let us show that $\zeta$ is non-atomic outside of zero, this is
essentially a consequence of the RDE, for $Z,Z_{i}\sim\zeta$ and
$w_{i}\sim\omega$, all mutually independent :

$Z\overset{\mathcal{L}}{=}\max\left(0,\max_{1\leq i\leq
N}(w_{i}-Z_{i})\right).$

As $w_{i}$ is non-atomic, $w_{i}-Z_{i}$ is non-atomic as well, so the right-
hand side is non-atomic when it doesn’t evaluate to zero, which concludes. ∎

###  3.2 Adding self-loops

_In the remainder of this section, we will adopt the vertex-rooted point of
view._

We will prove that if $\omega$ is atomless, $(\mathbb{T},\mathbb{M}_{h})$
constructed in the previous section is the unique optimal unimodular random
matching on $\mathbb{T}$. Note that in the previous section, we constructed
$\mathbb{M}_{h}$ starting from any solution $h$ to equation
$(\ref{eq:hequation})$, this will indirectly show that any solution to
equation $(\ref{eq:hequation})$ constructs the same matching law.

This fact may seem quite surprising at first, but when we come back to the
finite case, it is really the atomless property of the weights that makes it
so that the optimal matching is unique almost surely. In the infinite case,
this still holds.

We will first introduce an extension of $\mathbb{T}$ as a graph where
optimality of matchings on $\mathbb{T}$ transfers over. The main reason that
led us to do this is to look at the vertex-rooted definition of performance:

$\operatorname{perf_{V}}(\mathbb{T},\mathbb{M})=\mathbb{E}\left[\sum_{v\sim
o}w(o,v)\mathbbm{1}_{(o,v)\in\mathbb{M}}\right]$

We would like to use the recursion on $Z_{h}$ to compare $\mathbb{M}_{h}$ to
other matchings $\mathbb{M}$. In the previous expression, there are two cases
depending on whether $o$ is matched:

  * •

If $o$ is matched to some $v$, $w(o,v)$ intervenes in the recursion of
$Z_{h}(u,o)$ and $Z_{h}(u,v)$ so the information transported by the $Z_{h}$
has "compared" $w(o,v)$ with other quantities, we can then hope to use the
recursion to study the optimality of $v$.

  * •

However, if the sum is empty, the contribution is $0$ which has not intervened
anywhere, so we would a priori have to study this exception everywhere.

This introduces very cumbersome exceptional cases that become intractable when
we start to consider complex events, the goal is thus to extend the weights
and make the random variables $Z_{h}$ on self edges $(v,v)$ so that the
weights on $(v,v)$ (that is zero for now, but we will see that we will put non
zero values on them instead) are transported through the recursion as well.
The definition of $Z_{h}(u,u)$ that we introduce shortly after also has a
simple interpretation, it is the (signed) gain if one forced u to be matched
to one of its neighbours.

Another more technical motivation to do this is to recover the same recursion
that has been studied by Aldous in [3].

We will define the extension
$(\mathbb{T}^{s},Z_{h}^{s},(f_{i}^{s})_{i\in\\{0,...,I\\}})=((V^{s},E^{s}),o,w^{s},Z_{h}^{s},(f_{i}^{s})_{i\in\\{0,....,I\\}})$
deterministically on every outcome of
$(\mathbb{T},Z_{h})=((E,V),o,w,Z_{h},(f_{i})_{i\in\\{0,...,I\\}})$, refer to
Figure 7 for an illustration. The vertex set and the decorations remain
unchanged, $V^{s}=V,f_{i}^{s}=f_{i}$. We will enrich the edge set by adding
self-loops $(v,v)$ for every $v\in V$ to construct $E^{s}$. If $e=(u,v)$ with
$u\neq v$, we do not change $w$ nor $Z_{h}$: we set $w^{s}(u,v)=w(u,v)$ and
$Z_{h}^{s}(u,v)=Z_{h}(u,v)$.

$w_{1},{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z_{1}}$$w_{2},{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z}{\color[rgb]{0.82,0.01,0.11}{}_{2}}$$w_{3},{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z}{\color[rgb]{0.82,0.01,0.11}{}_{3}}$$w_{4},{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z}{\color[rgb]{0.82,0.01,0.11}{}_{4}}$$\begin{array}[]{l}w^{s}(v,v):=Z_{h}^{s}(v,v)\
:=\underset{i}{\max}(w_{i}-{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}Z}_{{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}i}}).\end{array}$$v$
Figure 7: Extension to self-loops.

If $e=(v,v)$, we set :

$Z_{h}^{s}(v,v)=\max_{\begin{subarray}{c}u^{\prime}\sim v\\\ u^{\prime}\neq
v\end{subarray}}(w(v,u^{\prime})-Z_{h}(v,u^{\prime})),$
$w^{s}(v,v)=Z_{h}^{s}(v,v).$

The following recursive equation holds for $(\mathbb{T}^{s},Z_{h}^{s})$:

$\forall(u,v)\in\overset{\rightarrow}{E^{s}},Z_{h}^{s}(u,v)=\max_{\begin{subarray}{c}u^{\prime}\sim
v\\\ u^{\prime}\neq
u\end{subarray}}(w^{s}(v,u^{\prime})-Z_{h}^{s}(v,u^{\prime})).$ (11)

Indeed if $u=v$ then it is obvious by definition, now if $u\neq v$, then by
the previous equation:

$\displaystyle Z_{h}^{s}(u,v)$
$\displaystyle=Z_{h}(u,v)=\max(0,\max_{\begin{subarray}{c}u^{\prime}\sim v\\\
u^{\prime}\neq u,v\end{subarray}}(w(v,u^{\prime})-Z_{h}(v,u^{\prime})))$
$\displaystyle=\max(w^{s}(v,v)-Z_{h}^{s}(v,v),\max_{\begin{subarray}{c}u^{\prime}\sim
v\\\ u^{\prime}\neq u,v\end{subarray}}(w(v,u^{\prime})-Z_{h}(v,u^{\prime})))$
$\displaystyle=\max(w^{s}(v,v)-Z_{h}^{s}(v,v),\max_{\begin{subarray}{c}u^{\prime}\sim
v\\\ u^{\prime}\neq
u,v\end{subarray}}(w^{s}(v,u^{\prime})-Z_{h}^{s}(v,u^{\prime})))$
$\displaystyle=\max_{\begin{subarray}{c}u^{\prime}\sim v\\\ u^{\prime}\neq
u\end{subarray}}(w^{s}(v,u^{\prime})-Z_{h}^{s}(v,u^{\prime}))$

Now, since $v$ is unmatched by $\mathbb{M}_{h}$ is equivalent to
$\max(0,\max_{v^{\prime}\sim v}w(v,v^{\prime})-Z_{h}(v,v^{\prime}))$ being
zero from Proposition 9 ii) and $Z_{h}^{s}(v,v)=\max_{v^{\prime}\sim
v}w(v,v^{\prime})-Z_{h}(v,v^{\prime})$. We deduce that
$(v,v)\in\mathbb{M}_{h}^{s}$ if and only if $w^{s}(v,v)=Z_{h}^{s}(v,v)\leq 0$.
Since the $w$’s are non-atomic, we can replace the previous inequality with a
strict one. As a consequence, the implication we defined previously for the
criterion of edges being in $\mathbb{M}_{h}$ is now an equivalence:

$\\{u,v\\}\in\mathbb{M}_{h}^{s}\Leftrightarrow
w^{s}(u,v)>Z_{h}^{s}(u,v)+Z_{h}^{s}(v,u)\Leftrightarrow
v=\operatorname*{argmax}_{v^{\prime}\sim
v}(w(u,v^{\prime})-Z_{h}(u,v^{\prime})).$ (12)

This is the part that would break down had we chosen $\omega$ to be atomic,
the last inclusion rule would become fuzzy with multiple ties.

The following property we have just shown will be key later:

$(v,v)\in\mathbb{M}_{h}^{s}\Leftrightarrow Z_{h}^{s}(v,v)=w^{s}(v,v)<0.$ (13)

Intuitively, this corresponds to the fact that $u$ is matched to one of its
neighbours if and only if the gain of forcing $u$ to be matched to one of its
neighbours is positive. In other words, $u$ is matched by $\mathbb{M}_{h}$ if
and only if $w^{s}(u,u)=Z^{s}(u,u)\geq 0$. However, this does not give
information about who is the chosen neighbour of $u$.

We now define a new performance on the space of matchings on $\mathbb{T}^{s}$,
we only consider perfect matchings $\mathbb{M}^{s}$ where every vertex has
exactly one neighbour.

$\operatorname{perf}^{s}_{V}(\mathbb{T}^{s},\mathbb{M}^{s})=\mathbb{E}\left[\sum_{v\sim
o}w^{s}(o,v)\mathbbm{1}_{(o,v)\in\mathbb{M}^{s}}\right]$

If $\mathbb{M}$ is a partial matching on $\mathbb{T}$, there is a natural
projection of $\mathbb{M}$ into $\mathbb{M}^{s}$ a perfect matching on
$\mathbb{T}^{s}$ where we simply identify previously unmatched vertices $v$ as
matched to themselves through $(v,v)$. Note that this projection is invertible
by just forgetting $(v,v)$. This gives a canonical way to extend pre-existing
matchings on $\mathbb{T}$.

###  3.3 Optimality

The goal of this subsection is to prove the following statement:

######  Proposition 11.

The matching $(\mathbb{T},\mathbb{M}_{h})$ is optimal on $\mathbb{T}$.
Furthermore, almost surely, any optimal matching $\mathbb{M}$ on
$(\mathbb{T},Z_{h},\mathbb{M}_{h})$ shares the same set of unmatched vertices.

Before we embark on this proof, let us stress the fact that given any
unimodular matching $\mathbb{M}$ on $\mathbb{T}$, Proposition 9 iii) allows to
resample $\mathbb{M}_{h}$ on top of $(\mathbb{T},\mathbb{M})$ such that
$(\mathbb{T},\mathbb{M},\mathbb{M}_{h})$ is unimodular, we can then make both
matchings co-exist on the tree while retaining unimodularity.

We will proceed by proving the following lemma:

######  Lemma 12.

$(\mathbb{T}^{s},\mathbb{M}_{h}^{s})$ is a matching maximising
$\operatorname{perf}^{s}_{V}$.

###### Proof of Lemma 12.

Fix $\mathbb{M}^{s}$ any unimodular matching on $\mathbb{T}^{s}$. And sample
$(\mathbb{T}^{s},\mathbb{M}^{s},\mathbb{M}_{h}^{s})$ as in Proposition 9 iii).

We define the neighbour function $n$ associated with $\mathbb{M}^{s}$ for
which $n(u)$ is the vertex matched with $u$ in $\mathbb{M}^{s}$. Similarly, we
define the neighbour function $n_{h}$ associated with $\mathbb{M}_{h}^{s}$.

Set $v_{0}=o$, $v_{1}=n(o)$, $v_{-1}=n_{h}(o)$,
$v_{-2}=n(v_{-1})=n(n_{h}(o))$, see Figure 8 for an illustration.

$\in\
{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}\mathbb{M}^{s}}$$\in\
\mathbb{{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}M}}{\color[rgb]{0.82,0.01,0.11}{}^{s}}$$\in\
{\color[rgb]{0.56,0.07,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.56,0.07,1}\mathbb{M}_{h}^{s}}$$v_{-1}$$v_{-2}$$v_{1}$$o=v_{0}$
Figure 8: Illustration of the configuration in the proof of Proposition 9.

We want to show that

$\mathbb{E}[w^{s}(v_{0},v_{1})-w^{s}(v_{0},v_{-1})]\leq 0.$

To this end, we will use the recursion on $Z_{h}^{s}$ to bound the expectation
by an expression involving $Z_{h}^{s}$.

The expectation is zero outside the event $A=\\{n_{h}(o)\neq
n(o)\\}=\\{v_{-1}\neq v_{1}\\}$. Let us work on this event from now on. By
definition of $Z_{h}^{s}$, we have that

$Z_{h}^{s}(v_{-2},{v_{-1}})=\max_{y\sim v_{-1},y\neq
v_{-2}}(w^{s}(v_{-1},y)-Z_{h}^{s}(v_{-1},y)).$

However, because $(v_{0},v_{-1})$ is in $\mathbb{M}_{h}$, we know that

$v_{0}=\operatorname*{argmax}_{y\sim
v_{-1}}(w^{s}(v_{-1},y)-Z_{h}^{s}(v_{-1},y))$

and that $v_{-2}$ does not satisfy that maximum (else, $v_{0}=v_{-2}$ which
contradicts being in $A$).

Hence

$Z_{h}^{s}(v_{-2},{v_{-1}})=w^{s}(v_{-1},v_{0})-Z_{h}^{s}(v_{-1},v_{0}).$ (14)

Now, by definition of the $Z_{h}$, we also have

$Z_{h}^{s}(v_{-1},v_{0})=\max_{\begin{subarray}{c}y\sim v_{0}\\\ y\neq
v_{-1}\end{subarray}}((w^{s}(v_{0},y)-Z_{h}^{s}(v_{0},y))\geq
w^{s}(v_{0},v_{1})-Z_{h}^{s}(v_{0},v_{1})$ (15)

as we condition on $v_{-1}\neq v_{1}$.

Combining (14) and (15), we get that:

$\displaystyle w^{s}(v_{0},v_{1})-w^{s}(v_{0},v_{-1})$
$\displaystyle=w^{s}(v_{0},v_{1})-Z_{h}^{s}(v_{-1},v_{0})-Z_{h}^{s}(v_{-2},v_{-1})$
(16)
$\displaystyle=\left[w^{s}(v_{0},v_{1})-Z_{h}^{s}(v_{0},v_{1})-Z_{h}^{s}(v_{-1},v_{0})\right]+Z_{h}^{s}(v_{0},v_{1})-Z_{h}^{s}(v_{-2},v_{-1})$
(17) $\displaystyle\leq Z_{h}^{s}(v_{0},v_{1})-Z_{h}^{s}(v_{-2},v_{-1}).$ (18)

Taking expectation and remembering that $v_{1}=n(o)$ and $v_{-1}=n_{h}(o)$, we
get that:

$\displaystyle\operatorname{perf_{V}}^{s}(\mathbb{T}^{s},\mathbb{M}^{s})-\operatorname{perf_{V}}^{s}(\mathbb{T}^{s},\mathbb{M}_{h}^{s})$
$\displaystyle\mathbb{E}[w^{s}(o,n(o))]-\mathbb{E}[w^{s}(o,n_{h}(o))]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[(w^{s}(v_{0},v_{1})-w^{s}(v_{0},v_{-1}))\mathbbm{1}_{A}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\left[(Z_{h}^{s}(v_{0},v_{1})-Z_{h}^{s}(v_{-2},v_{-1}))\mathbbm{1}_{A}.\right]$

It remains to show that the final expectation is zero, to this end, we will
use unimodularity to prove that conditionally on $A$, $Z_{h}^{s}(v_{0},v_{1})$
and $Z_{h}^{s}(v_{-2},v_{-1})$ have the same law.

Let $B$ some Borel set of $\mathbb{R}$, we want to show that:

$\mathbb{P}\left(Z_{h}^{s}(v_{0},v_{1})\in
B,A\right)=\mathbb{P}\left(Z_{h}^{s}(v_{-2},v_{-1})\in B,A\right).$ (19)

To prove this, we will use a chain of intermediary equalities between the two
events by applying the mass-transport principle. First, we need to show that
the mass-transport principle still holds when $(\mathbb{T},\mathbb{M},Z_{h})$
is replaced by $(\mathbb{T}^{s},\mathbb{M}^{s},Z_{h}^{s})$. But
$(\mathbb{T}^{s},\mathbb{M}^{s},Z_{h}^{s})$ is the image of
$(\mathbb{T},\mathbb{M},Z_{h})$ through a deterministic bijective operator so
taking expectations over either yields the same thing. Indeed for every $f$
that is a measurable function over the space of doubly pointed decorated
trees, we want to show that:

$\mathbb{E}_{(T,M,Z_{h})\sim(\mathbb{T}^{s},\mathbb{M}^{s},Z_{h}^{s})}\left[\sum_{v\in
V^{s}}f(T,M,Z_{h},o,v)\right]$
$=\mathbb{E}_{(T,M,Z_{h})\sim(\mathbb{T}^{s},\mathbb{M}^{s},Z_{h}^{s})}\left[\sum_{v\in
V^{s}}f(T,M,Z_{h},v,o)\right].$

To this end we will write $(T,M,Z_{h})\sim s(\hat{T},\hat{M},\hat{Z_{h}})$
where $(\hat{T},\hat{M},\hat{Z_{h}})\sim(\mathbb{T},\mathbb{M},Z_{h})$, and
notice $V=V^{s}$ so the required equality rewrites as:

$\mathbb{E}_{(T,M,Z_{h})\sim(\mathbb{T},\mathbb{M},Z_{h})}\left[\sum_{v\in
V}f(s(T,M,Z_{h}),o,v)\right]$
$=\mathbb{E}_{(T,M,Z_{h})\sim(\mathbb{T},\mathbb{M},Z_{h})}\left[\sum_{v\in
V}f(s(T,M,Z_{h}),v,o)\right].$

which is true by unimodularity of $(\mathbb{T},\mathbb{M},Z_{h})$.

$v_{-1}$$v_{-2}$$v_{1}$$v_{0}$$Z_{h}(u,v)\in
B$$v_{0}$$v_{1}$$v_{-2}$$v_{-1}$$Z_{h}(u,v)\in B$ Figure 9: The second idea is
that the two events have the same probability seen either from $v_{0}$ or
$v_{-1}$.

Let us recall the definition of $v_{k}$ so the desired equality rewrites as :

$\mathbb{P}\left(Z_{h}^{s}(o,n(o))\in B,n(o)\neq
n_{h}(o)\right)=\mathbb{P}\left(Z_{h}^{s}(n(n_{h}(o)),n_{h}(o))\in B,n(o)\neq
n_{h}(o)\right).$

Define the $(\mathbb{T}^{s},\mathbb{M}^{s},Z_{h}^{s})$ measurable function $f$
on the space of double rooted decorated trees:

$f(T,M,Z_{h}^{s},a,b)=\mathbbm{1}_{Z_{h}^{s}(a,b)\in B,n(a)\neq
n_{h}(a),b=n(a)}.$

Applying mass-transport principle to $f$ we get:

$\mathbb{E}\left[\sum_{v\in
V}f(\mathbb{T}^{s},\mathbb{M}^{s},Z_{h}^{s},o,v)\right]=\mathbb{E}\left[\sum_{v\in
V}f(\mathbb{T}^{s},\mathbb{M}^{s},Z_{h}^{s},v,o)\right]$

Computing the first expectation yields:

$\displaystyle\mathbb{E}\left[\sum_{v\in V}\mathbbm{1}_{Z_{h}^{s}(o,v)\in
B,n(o)\neq n_{h}(o),v=n(o)}\right]$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}_{Z_{h}^{s}(o,n(o))\in B,n(o)\neq
n_{h}(o)}\right]$ $\displaystyle=\mathbb{P}\left(Z_{h}^{s}(o,n(o))\in
B,n(o)\neq n_{h}(o)\right).$

Computing the second expectation yields:

$\displaystyle\mathbb{E}\left[\sum_{v\in V}\mathbbm{1}_{Z_{h}^{s}(v,o)\in
B,n(v)\neq n_{h}(v),o=n(v)}\right]$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}_{Z_{h}^{s}(n(o),o)\in B,n(n(o))\neq
n_{h}(n(o))}\right]$ $\displaystyle=\mathbb{P}\left(Z_{h}^{s}(n(o),o)\in
B,n(o)\neq n_{h}(o)\right)$

where we used that $o=n(v)$ is equivalent to $v=n(o)$ and the fact that
$n(n(o))\neq n_{h}(n(o))$ is equivalent to $n(o)\neq n_{h}(o)$.

We now define another measurable function $f^{\prime}$ on the same space:

$f^{\prime}(T,M,Z_{h}^{s},a,b)=\mathbbm{1}_{Z_{h}^{s}(n(a),a)\in B,n(a)\neq
n_{h}(a),b=n_{h}(a)}.$

Once again, applying the mass-transport principle to $f^{\prime}$ we get:

$\mathbb{E}\left[\sum_{v\in
V}f^{\prime}(\mathbb{T}^{s},\mathbb{M}^{s},Z_{h}^{s},o,v)\right]=\mathbb{E}\left[\sum_{v\in
V}f^{\prime}(\mathbb{T}^{s},\mathbb{M}^{s},Z_{h}^{s},v,o)\right].$

Computing the first expectation yields:

$\displaystyle\mathbb{E}\left[\sum_{v\in V}\mathbbm{1}_{Z_{h}^{s}(n(o),o)\in
B,n(o)\neq n_{h}(o),v=n_{h}(o)}\right]$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}_{Z_{h}^{s}(n(o),o)\in B,n(o)\neq
n_{h}(o)}\right]$ $\displaystyle=\mathbb{P}\left(Z_{h}^{s}(n(o),o)\in
B,n(o)\neq n_{h}(o)\right).$

Computing the second expectation yields:

$\displaystyle\mathbb{E}\left[\sum_{v\in V}\mathbbm{1}_{Z_{h}^{s}(n(v),v)\in
B,n(v)\neq n_{h}(v),o=n_{h}(v)}\right]$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}_{Z_{h}^{s}(n(n_{h}(o)),n_{h}(o))\in
B,n(n_{h}(o))\neq n_{h}(n_{h}(o))}\right]$
$\displaystyle=\mathbb{P}\left(Z_{h}^{s}(n(n_{h}(o)),n_{h}(o))\in B,n(o)\neq
n_{h}(o)\right).$

where we used that $o=n_{h}(v)$ is equivalent to $v=n_{h}(o)$ and the fact
that $n(n_{h}(o))\neq(n_{h}(n_{h}(o)))$ is equivalent to $n(o)\neq n_{h}(o)$.

In conclusion, we showed

$\mathbb{P}\left(Z_{h}^{s}(o,n(o))\in B,n(o)\neq
n_{h}(o)\right)=\mathbb{P}\left(Z_{h}^{s}(n(o),o)\in B,n(o)\neq
n_{h}(o)\right)$ $=\mathbb{P}\left(Z_{h}^{s}(n(n_{h}(o)),n_{h}(o))\in
B,n(o)\neq n_{h}(o)\right),$

yielding (19) and the Lemma. ∎

We are now ready to prove our optimality result for unimodular matchings.

###### Proof of Proposition 11.

Let $(\mathbb{T},\mathbb{M})$ an optimal matching on $\mathbb{T}$ and $n$ its
associated neighbour function. Let $(\mathbb{T},\mathbb{M},Z_{h})$ such that
the law of the marginals $(\mathbb{T},\mathbb{M})$ and $(\mathbb{T},Z_{h})$
are preserved. The main idea is that by adding self-loops with the rules given
in the previous subsection, the matching $\mathbb{M}_{h}^{s}$ is the most
penalised perfect matching of $\mathbb{T}^{s}$. This allows us to compare
$\mathbb{M}$ and $\mathbb{M}_{h}$ by comparing their counterparts on
$\mathbb{T}^{s}$. The fact that $\mathbb{M}$ is optimal translates into the
fact that

$\operatorname{perf}(\mathbb{M})=\mathbb{E}\left[w^{s}(o,n(o))\mathbbm{1}_{o\neq
n(o)}\right]$

is maximal among unimodular perfect matchings of $\mathbb{T}^{s}$.

Let us decompose $w^{s}(o,n(o))$ and $w^{s}(o,n_{h}(o))$ into their positive
and negative parts.

$\displaystyle\operatorname{perf_{V}}^{s}(\mathbb{M}^{s})$
$\displaystyle=\mathbb{E}\left[w^{s}(o,n(o))\mathbbm{1}_{w^{s}(o,n(o))\geq
0}\right]+\mathbb{E}\left[w^{s}(o,n(o))\mathbbm{1}_{w^{s}(o,n(o))<0}\right]$
$\displaystyle\operatorname{perf_{V}}^{s}(\mathbb{M}_{h}^{s})$
$\displaystyle=\mathbb{E}\left[w^{s}(o,n_{h}(o))\mathbbm{1}_{w^{s}(o,n_{h}(o))\geq
0}\right]+\mathbb{E}\left[w^{s}(o,n_{h}(o))\mathbbm{1}_{w^{s}(o,n_{h}(o))<0}\right]$

But remembering (13), $\mathbb{M}_{h}^{s}$ is precisely the matching that
includes all the strictly negative weight self-loops and only them.

This implies that the previous decomposition can be written as:

$\operatorname{perf_{V}}^{s}(\mathbb{M}_{h}^{s})=\operatorname{perf_{V}}(\mathbb{M}_{h})+\mathbb{E}[w^{s}(o,o)\mathbbm{1}_{w^{s}(o,o)<0}.]$

Now we can lower bound the positive part of
$\operatorname{perf_{V}}^{s}(\mathbb{M}^{s})$ by
$\operatorname{perf_{V}}(\mathbb{M})$ by omitting the positive weight self-
loops and we can lower bound the negative part by
$[w^{s}(o,o)\mathbbm{1}_{w^{s}(o,o)<0}.]$ because $\mathbb{M}^{s}$ can at most
include every negative self-loop:

$\operatorname{perf_{V}}^{s}(\mathbb{M}^{s})\geq\operatorname{perf_{V}}(\mathbb{M})+\mathbb{E}[w^{s}(o,o))\mathbbm{1}_{w^{s}(o,o)<0}].$

But $\mathbb{M}$ is optimal so
$\operatorname{perf_{V}}(\mathbb{M})\geq\operatorname{perf_{V}}(\mathbb{M}_{h})$,
so we proved

$\operatorname{perf_{V}}^{s}(\mathbb{M}^{s})\geq\operatorname{perf_{V}}(\mathbb{M}_{h})+\mathbb{E}[w^{s}(o,o)\mathbbm{1}_{w^{s}(o,o)<0})]=\operatorname{perf_{V}}^{s}(\mathbb{M}_{h}^{s}).$

But we proved in Lemma 12 that $\mathbb{M}_{h}^{s}$ is optimal for
$\operatorname{perf_{V}}^{s}$ so

$\operatorname{perf_{V}}^{s}(\mathbb{M}_{h}^{s})\geq\operatorname{perf_{V}}^{s}(\mathbb{M}^{s}).$

So equality holds and all previous inequalities were equalities:

$\displaystyle\operatorname{perf_{V}}(\mathbb{\mathbb{M}})=\operatorname{perf_{V}}(\mathbb{M}_{h}),$
$\displaystyle\operatorname{perf_{V}}(\mathbb{\mathbb{M}})=\mathbb{E}\left[w^{s}(o,n(o))\mathbbm{1}_{w^{s}(o,n(o))\geq
0}\right],$
$\displaystyle\mathbb{E}\left[w^{s}(o,n(o))\mathbbm{1}_{w^{s}(o,n(o))<0}\right]=\mathbb{E}[w^{s}(o,o)\mathbbm{1}_{w^{s}(o,o)<0})].$

So we’ve shown that $\mathbb{M}^{s}$ maximizes $\operatorname{perf_{V}}^{s}$
and that $\mathbb{M}_{h}$ is optimal on $\mathbb{T}$. Furthermore, by
unimodularity, we get that the set of unmatched vertices by $\mathbb{M}$ is
almost surely the same as the set of unmatched vertices by $\mathbb{M}_{h}$,
and it is almost surely the set of vertices $v$ such that $w^{s}(v,v)<0$. ∎

######  Remark.

If $\mathbb{M}$ is optimal, we have
$\operatorname{perf_{V}}^{s}(\mathbb{M}^{s})=\operatorname{perf_{V}}^{s}(\mathbb{M}_{h}^{s})$
in addition to
$\operatorname{perf_{V}}(\mathbb{M})=\operatorname{perf_{V}}(\mathbb{M}_{h})$.

###  3.4 Uniqueness

_We will keep using the vertex-rooted point of view in this section._

The goal of this section is to prove that $\mathbb{M}_{h}$ is also the unique
optimal matching in law. We will actually prove the following stronger result:

######  Proposition 13.

Let $(\mathbb{T},\mathbb{M})$ be a unimodular optimal matched graph, sample
$(\mathbb{T},\mathbb{M},Z_{h})$ with Proposition 9. Almost surely,
$\mathbb{M}=\mathbb{M}_{h}$.

###### Proof.

We will show that almost surely, $\mathbb{M}^{s}=\mathbb{M}_{h}^{s}$ and
deduce that almost surely, $\mathbb{M}=\mathbb{M}_{h}$ through the projection
that forgets self-loops. Recall that $A$ is the event when $n_{h}(o)\neq n(o)$
and assume $\mathbb{P}(A)\neq 0$.

Going back into the proof of optimality of $\mathbb{M}_{h}^{s}$. Taking
expectation in Equation (16) we get

$\displaystyle\operatorname{perf_{V}}^{s}(\mathbb{M}^{s})-\operatorname{perf_{V}}^{s}(\mathbb{M}_{h}^{s})$
$\displaystyle=\mathbb{E}\left[(w^{s}(v_{0},v_{1})-Z_{h}^{s}(v_{0},v_{1})-Z_{h}^{s}(v_{-1},v_{0}))\mathbbm{1}_{v_{1}\neq
v_{-1}}\right]$

Equality between $\operatorname{perf_{V}}^{s}(\mathbb{M}_{h}^{s})$ and
$\operatorname{perf_{V}}^{s}(\mathbb{M}^{s})$ (see Remark Remark) implies that
the RHS is equal to $0$ , furthermore Equation (15) says that the variable in
the expectation of the RHS is non negative almost surely, we conclude that
almost surely:

$Z_{h}^{s}(v_{-1},o)=\max_{\begin{subarray}{c}y\sim o\\\ y\neq
v_{-1}\end{subarray}}(w^{s}(o,y)-Z_{h}^{s}(o,y))=w^{s}((o,v_{1})-Z_{h}^{s}(o,v_{1})).$

By definition of $n_{h}$,

$v_{-1}=n_{h}(o)=\operatorname*{argmax}_{y\sim o}(w^{s}(o,y)-Z_{h}^{s}(o,y)).$

So $v_{1}$ achieves the maximum among the list of
$(w^{s}(o,y)-Z_{h}^{s}(o,y))$ stripped of its maximum. We deduce that
$v_{1}=n(o)$ achieves the second largest among the
$(w^{s}(o,y)-Z_{h}^{s}(o,y))$ that we will write as
$\overset{[2]}{\underset{y\sim
o}{\operatorname*{argmax}}}(w^{s}(o,y)-Z_{h}^{s}(o,y))$.

Thus:

$\mathbb{P}\left(n(o)=\underset{y\sim
o}{\operatorname*{argmax}}(w^{s}(o,y)-Z_{h}^{s}(o,y))\text{ or
}\underset{y\sim
o}{\operatorname*{\overset{[2]}{argmax}}}(w^{s}(o,y)-Z_{h}^{s}(o,y))\right)=1.$

$\in\
\mathbb{{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}M}}{\color[rgb]{0.82,0.01,0.11}{}^{s}}$$\in\
\mathbb{{\color[rgb]{0.56,0.07,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.56,0.07,1}M}}{\color[rgb]{0.56,0.07,1}{}_{h}^{s}}$$v_{1}$$v_{0}$$v_{-1}$$v_{2}$$v_{3}$$v_{-2}$$v_{-3}$$v_{-4}$
Figure 10: Alternating path from $o$.

Now let us set:

$\displaystyle v_{0}$ $\displaystyle=o,$ $\displaystyle v_{1}$
$\displaystyle=\underset{y\sim
o}{\operatorname*{\overset{[2]}{argmax}}}(w^{s}(o,y)-Z_{h}^{s}(o,y)),$
$\displaystyle v_{-1}$ $\displaystyle=\underset{y\sim
o}{\operatorname*{argmax}}(w^{s}(o,y)-Z_{h}^{s}(o,y)),$ $\displaystyle
v_{-2k}$ $\displaystyle=\underset{y\sim
w_{-2k+1}}{\operatorname*{\overset{[2]}{argmax}}}(w^{s}(v_{-2k+1},y)-Z_{h}^{s}(v_{-2k+1},y))$
$\displaystyle\forall k\in\mathbb{N}^{*},$ $\displaystyle v_{-2k-1}$
$\displaystyle=\underset{y\sim
w_{-2k}}{\operatorname*{argmax}}(w^{s}(v_{-2k},y)-Z_{h}^{s}(v_{-2k},y))$
$\displaystyle\forall k\in\mathbb{N}^{*},$ $\displaystyle v_{2k}$
$\displaystyle=\underset{y\sim
w_{2k-1}}{\operatorname*{argmax}}(w^{s}(v_{2k-1},y)-Z_{h}^{s}(v_{2k-1},y))$
$\displaystyle\forall k\in\mathbb{N}^{*},$ $\displaystyle v_{2k+1}$
$\displaystyle=\underset{y\sim
w_{2k}}{\operatorname*{\overset{[2]}{argmax}}}(w^{s}(v_{2k},y)-Z_{h}^{s}(v_{2k},y))$
$\displaystyle\forall k\in\mathbb{N}^{*}.$

We always have by construction that $(v_{-2k},v_{-2k-1})\in\mathbb{M}_{h}$ for
any $k\in\mathbb{Z}$.

Conditionally on the event $A=\\{n_{h}(o)\neq n(o)\\}$, we get that:

$\mathbb{P}\left(\bigcup_{k\in\mathbb{Z}}\left\\{(v_{-2k-1},v_{-2k-2})\in\mathbb{M}\right\\}\middle|A\right)=1$

Furthermore, by the second part of Proposition 11, almost surely, for any
$v\in V$, $n_{h}(v)=v$ if and only if $n(v)=v$, from this we deduce that on
$A$ we have $v_{-1}\neq v_{0}$ and, by induction, $\forall
k\in\mathbb{N},v_{-k}\neq v_{-k-1}$ (no loops in the path) and also that
$\forall k\in\mathbb{N},v_{-k-2}\neq v_{-k}$ (the path cannot go back up).

Thus, $\mathbb{P}\left(k\mapsto v_{k}\text{ is into }|A\right)=1.$ Let us
write $C=\\{k\in\mathbb{Z}\mapsto v_{k}\text{ is into}$}. Define for
$(N,N^{\prime})\in\overline{\mathbb{Z}}^{2}$, $N<N^{\prime}$:

$C_{N,N^{\prime}}=\\{k\mapsto v_{k}\text{ is into for }N\leq k\leq
N^{\prime}\\}.$

We have that $\mathbb{P}(A)>0$ and $\mathbb{P}(C|A)=1$ so
$\mathbb{P}(C)\geq\mathbb{P}(A)>0$. Furthermore, $C\subset C_{-\infty,0}$ so
$\mathbb{P}(C_{-\infty,0})>0$. We are going to show that this is not possible
by establishing a contradiction for the value of the probability

$\mathbb{P}\left(\overline{C_{0,2}}|C_{-\infty,0}\right).$ (20)

First, we will use unimodularity to show that
$\mathbb{P}\left(\overline{C_{0,2}}|C_{-\infty,0}\right)=0$. We will rely on
the following Lemma whose proof is postponed to the end of this Section.

######  Lemma 14.

For any $N\in\mathbb{N}$,

$\mathbb{P}\left(C_{-2N,2}\right)=\mathbb{P}\left(C_{-2N-2,0}\right).$

From this Lemma we deduce that:

$\mathbb{P}(C_{-\infty,2})=\mathbb{P}(C_{-\infty,0}).$

As long as $\deg(o)\geq 1$, there is one regular edge with $o$ as an endpoint
and the self-loop $\\{o,o\\}$ the $\operatorname*{argmax}$ and
$\operatorname*{\overset{[2]}{argmax}}$ around $o$ are thus automatically
different. We can then decompose $C_{-\infty,2H}$ as $C_{-\infty,0}\cap
C_{0,2}\cap\\{\deg(o)\geq 1\\}$

$\mathbb{P}\left(C_{0,2}\cap\\{\deg(o)\geq 1\\}|C_{-\infty,0}\right)=1.$

Hence
$\mathbb{P}\left(\overline{C_{0,2}}\cup\\{\deg(o)<1\\}|C_{-\infty,0}\right)=0$
and

$\mathbb{P}\left(\overline{C_{0,2}}|C_{-\infty,0}\right)=0.$

Second, by exhibiting explicit configurations of positive total mass where
$\overline{C_{0,2}}$ happens, we will show that
$\mathbb{P}\left(\overline{C_{0,2}}|C_{-\infty,0}\right)>0$.

Set $T_{v_{-1}}$ the subtree rooted at $v_{-1}$.

Referring to Figure 11, the idea is that if $v_{0}\neq v_{-1}$, the only
dependence the $\\{v_{-k},k\geq 1\\}$ has from $T\setminus T_{v_{-1}}$ comes
from $Z_{h}(v_{0},v_{-1})$ and $w(v_{-1},v_{0})$, so we will condition on the
values of $Z_{h}(v_{0},v_{-1}),w(v_{0},v_{-1})$. Let $\mathcal{P}$ be the law
of $Z_{h}(v_{0},v_{-1}),w(v_{0},v_{-1})$ conditionally on $C_{-\infty,0}$, we
have then shown that:

$\displaystyle\mathbb{P}\left(\overline{C_{0,2}}|C_{-\infty,0}\right)$
$\displaystyle\geq$
$\displaystyle\iiint\mathbb{P}\left(\overline{C_{0,2}}|Z_{h}(v_{0},v_{-1}),w(v_{0},v_{-1}),C_{-\infty,0}\right)\mathrm{d}\mathcal{P}.$
$\displaystyle=$
$\displaystyle\iiint\mathbb{P}\left(\overline{C_{0,2}}|Z_{h}(v_{0},v_{-1}),w(v_{0},v_{-1})\right)\mathrm{d}\mathcal{P}.$

It suffices to show that

$\mathbb{P}\left(\overline{C_{0,2}}|Z_{h}(v_{0},v_{-1}),w(v_{0},v_{-1})\right)>0$

$\mathcal{P}$-almost everywhere and this will imply a contradiction.

$v_{-1}$$v_{0}$$T_{v_{0}}=T\setminus
T_{v_{-1}}{}$$T_{v_{-1}}$$Z_{h}(v_{0},v_{-1})$ Figure 11: The variables
attached to $T_{v_{0}}$ only depend on $T_{v_{-1}}\cup\\{v_{0},v_{-1}\\}$ and
its attached variables through $Z(v_{0},v_{-1})$ and $w(v_{0},v_{-1})$.

The next Lemma shows an explicit lower bound as required:

######  Lemma 15.

Let $(W_{i})_{i\geq 1}$ be i.i.d variables of law $\omega$.

Let $\tilde{\pi}_{k}=\mathbb{P}(\deg(o)=k|C_{-\infty,0})$.

Let $\mathbf{X}$ any Borel subset of
$\mathrm{supp}(\omega)\times\mathrm{supp}(\zeta_{h})$:

$\mathbb{P}\left(\overline{C_{0,2}}|\left(w(v_{0},v_{-1}),Z_{h}(v_{0},v_{-1})\right)\in\mathbf{X}\right)\geq\sum_{k>1}\tilde{\pi}_{k}\mathbb{P}_{Z\sim\zeta_{h}}(Z=0)^{k-1}.$

Lemma 10 implies that $\mathbb{P}_{Z\sim\zeta_{h}}(Z=0)>0$. This uniform lower
bound does not depend on the values of $w(v_{0},v_{-1}),Z_{h}(v_{0},v_{-1})$,
so it is $\mathcal{P}$ almost-sure. ∎

We now turn to the proof of our two Lemmas.

###### Proof of Lemma 14.

$v_{1}$$v_{0}$$v_{-1}$$v_{2}$$v_{-5}$$v_{-2}$$v_{-3}$$v_{-4}$ Figure 12: We
see the same event from the perspectives of $v_{2}$ inside the orange box and
$v_{0}$ inside the green box.

Refer to Figure 12 for an illustration. Define the alternating path starting
from a vertex $u$ as:

$u_{1}(u)=\operatorname*{argmax}_{y\sim
u}(w^{s}(u,y)-Z_{h}^{s}(u,y)),u_{2}(u)=\operatorname*{\overset{[2]}{argmax}}_{y\sim
u_{1}}(w^{s}(u_{1},y)-Z_{h}^{s}(u_{1},y)),$

and for $n\geq 1,$

$u_{2n+1}(u)=\operatorname*{argmax}_{y\sim
u_{2n}}(w^{s}(u_{2n},y)-Z_{h}^{s}(a_{2n},y)),u_{2n+2}(u)=\operatorname*{\overset{[2]}{argmax}}_{y\sim
u_{2n+1}}(w^{s}(u_{2n+1},y)-Z_{h}^{s}(u_{2n+1},y)),$

By convention, set $u_{0}=\text{Id}_{V}$, in other words, $u_{0}(u)=u$. Let
$N\in\mathbb{N}$, define events:

$C_{N}(T,Z_{h},a,b)=\left\\{n\mapsto u_{n}(a)\text{ is into for }0\leq n\leq
2N\right\\}\cap\left\\{n\mapsto u_{n}(b)\text{ is into for }0\leq n\leq
2N\right\\}$

Let us define
$f_{N}(T,M,Z_{h},a,b):=\mathbbm{1}_{C_{N}(T,Z_{h},a,b)\cap\\{b=u_{2}(a)\\}}$.

On one hand,

$\mathbb{E}\left[\sum_{v\in
V}f_{N}(T,M,Z_{h},o,v)\right]=\mathbb{P}\left(C_{-N,2}\right),$

on the other hand

$\mathbb{E}\left[\sum_{v\in
V}f_{N}(T,M,Z_{h},v,o)\right]=\mathbb{P}\left(C_{-N-2,0}\right).$

Applying mass-transport principle to $f_{N}$ yields the result. ∎

###### Proof of Lemma 15.

$v_{0}$$v_{-1}$${\color[rgb]{0.29,0.56,0.89}\definecolor[named]{pgfstrokecolor}{rgb}{0.29,0.56,0.89}Z_{i}}=0$$u_{i}$$w_{i}$
Figure 13: For $\mathbb{M}_{h}$ to stop, it suffices that all the $Z_{i}=0$.

Let $u_{i}$ be the children of $o$ as vertices for $i\leq\deg(o)$,
$Z_{i}=Z_{h}(o,u_{i})$. This follows from seeing that:

$\displaystyle\left\\{\left(W(v_{0},v_{-1}),Z_{h}(v_{0},v_{-1})\right)\in\mathbf{X},\overline{C_{0,2}}\right\\}$
$\displaystyle\subseteq$
$\displaystyle\left\\{\left(W(v_{0},v_{-1}),Z_{h}(v_{0},v_{-1})\right)\in\mathbf{X},n_{h}(v_{1})=v_{1}\right\\}$
$\displaystyle\subseteq$
$\displaystyle\left\\{\left(W(v_{0},v_{-1}),Z_{h}(v_{0},v_{-1})\right)\in\mathbf{X},\forall
i\leq\deg(o),Z_{i}=0\right\\}.$

Refer to Figure 13 for an illustration. Every variable appearing in this event
is independent of all others, so we can sum over $\deg(o)$ to obtain the
bound:

$\displaystyle\mathbb{P}\left(\overline{C_{0,2}}|\left(w(v_{0},v_{-1}),Z_{h}(v_{0},v_{-1})\right)\in\mathbf{X}\right)$
$\displaystyle\geq\frac{\mathbb{P}\left(\left(w(v_{0},v_{-1}),Z_{h}(v_{0},v_{-1})\right)\in\mathbf{X}\right)\sum_{k>1}\tilde{\pi}_{k}\mathbb{P}_{Z\sim\zeta_{h}}(Z=0)^{k-1}}{\mathbb{P}\left(w(v_{0},v_{-1}),Z_{h}(v_{0},v_{-1})\right)\in\mathbf{X})}.$

The factors
$\mathbb{P}\left(\left(w(v_{0},v_{-1}),Z_{h}(v_{0},v_{-1})\right)\in\mathbf{X}\right)$
cancel out, so we get the desired expression. ∎

##  4 From infinite to finite

_In this entire section, unless stated otherwise, we will adopt the edge-
rooted point of view._

The aim of this section is to prove the following statement:

######  Proposition 16.

Assume $(G_{n},o_{n})_{n\geq 1}$ a sequence of finite graphs which converges
locally to the unimodular BGW tree $(\mathbb{T},o)$ with reproduction law
$\pi$ and weights $\omega$.

Assume $\mathbb{E}_{N\sim\pi}[N]<\infty$,
$\mathbb{E}_{W\sim\omega}[W]<\infty$, $\omega$ is atomless, and that
$\frac{|E_{n}|}{|V_{n}|}$ converges in probability to
$\frac{\mathbb{E}_{N\sim\pi}[N]}{2}$.

Let $M_{\mathrm{opt}}(G_{n})$ be the optimal matching on $G_{n}$, then every
subsequence of $(G_{n},o_{n},M_{\mathrm{opt}}(G_{n}))$ has a subsequence that
converges locally to $(\mathbb{T},o,\mathbb{M})$ where $\mathbb{M}$ is an
optimal unimodular matching on $\mathbb{T}$.

The proof can be broken down into two parts, one easy, and one hard:

  * •

Every subsequence of $(G_{n},o_{n},M_{\mathrm{opt}}(G_{n}))$ has a subsequence
that converges locally to some $(\mathbb{T},o,\mathbb{M})$ where $\mathbb{M}$
is a unimodular matching on $\mathbb{T}$.

  * •

The previously found $\mathbb{M}$ must be optimal.

For the easy part, using tightness arguments, we will show that every
subsequence has a convergent subsequence. The limit of any convergent
subsequence is necessarily suboptimal by the definition of optimality, one
only needs to verify that the limit will define a unimodular matched graph.

For the hard part, we will show that the limit of any convergent subsequence
is necessarily optimal by constructing an almost optimal quasi-matching on
$G_{n}$ from the optimal matching $(\mathbb{T},\mathbb{M}_{h})$. Indeed, as a
consequence, this will show that $M_{\mathrm{opt}}(G_{n})$ does asymptotically
better than $\operatorname{perf_{V}}(\mathbb{M}_{h})$.

###  4.1 Local convergence of subsequences

In this section we will carry out the easy part using the following lemma:

######  Lemma 17.

Let $(G_{n},o_{n})$ be a sequence in the space of rooted graphs,
$G_{n}=(V_{n},E_{n})$. Let $(f_{n})_{n\in\mathbb{N}}$ be any (random)
functions on $E_{n}$ such that the sequence $(f_{n})$ is uniformly bounded.
Assume that $G_{n}$ converges locally to an almost surely locally finite graph
$G$. Then for any $H\in\mathbb{N}$, the sequence of decorated graphs
$N_{H}(G_{n},o_{n},f_{n})$ is tight.

###### Proof.

Let $H\in\mathbb{N}$ and $\varepsilon>0$. Denote by $\tau_{H,N}$ the set of
rooted graphs of depth $H$ and degree bounded by $N$. Since $G$ is locally
finite, for $N$ large enough, we have
$\mathbb{P}(N_{H}(G,o)\in\tau_{H,N})>1-\frac{\epsilon}{2}$. By local
convergence,
$\mathbb{P}(N_{H}(G_{n},o_{n})\in\tau_{H,N})\underset{n\rightarrow\infty}{\longrightarrow}\mathbb{P}(N_{H}(G,o)\in\tau_{H,N})$
hence for $n$ large enough,

$\mathbb{P}(N_{H}(G_{n},o_{n})\in\tau_{H,N})>1-\epsilon$

Let $A=\sup_{n\geq 0}\|f_{n}\|_{\infty}$, denote by $\tau_{H,N,A}$ the set of
edge-decorated graphs consisting of elements of $\tau_{H,N}$ decorated by a
function bounded by $A$. Then $\tau_{H,N,A}$ is compact and for $n$ large
enough:

$\mathbb{P}(N_{H}(G_{n},o_{n},f_{n})\in\tau_{H,N,A})>1-\epsilon,$

$N_{H}(G_{n},o,f_{n})$ is thus tight. ∎

We can now go back to the proof of Proposition 16. Take
$f_{n}=\mathbbm{1}_{M_{\mathrm{opt}}(G_{n})}$, it is uniformly bounded by $1$.
Apply Lemma 17 to $N_{0}(G_{n},o_{n},f_{n})$ to obtain a subsequence such that
$N_{0}(G_{k_{n}},o_{k_{n}},f_{k_{n}})$ converges.

But $(G_{k_{n}},o_{k_{n}})$ still converges locally to $(G,o)$, so apply Lemma
17 again to find a subsequence $k_{n}^{\prime}$ of $k_{n}$ such that
$N_{1}(G_{k^{\prime}_{n}},o_{k^{\prime}_{n}},f_{k^{\prime}_{n}})$ converges
locally. Repeat the process and use a diagonal argument to obtain a
subsequence $l_{n}$ such that for all $H\in\mathbb{N}$,
$N_{H}(G_{l_{n}},o_{l_{n}},f_{l_{n}})$ converges weakly to some limit
$N_{H}(G,o,g_{H})$ for some decoration $g_{H}$.

Furthermore, since the decorations $g_{H}$ are obtained from a diagonal
construction, the family $(g_{H})_{H\geq 0}$ is consistent and therefore
define a limiting decoration $g$. To prove that this decoration is a matching,
we just have to take successively limits in $n\rightarrow\infty$ and
$H\rightarrow\infty$ in the equalities

$\mathbb{P}\left(\sum_{u\sim v}f_{l_{n}}(u,v)\leq 1,(u,v)\in
V(N_{H}(G_{n},o_{n}))\right)=1,\mathbb{P}\left(f_{l_{n}}(e)\in\\{0,1\\},e\in
E(N_{H}(G_{n},o_{n}))\right)=1.$

Now we just need to check that the limiting object is unimodular, it is a
consequence that any local limit of unimodular graphs is unimodular, we refer
to [5].

The sequence of graphs $(G_{n},o_{n})$ converges weakly to $\mathbb{T}$. Take
$j_{n}$ a subsequence such that
$\operatorname{perf_{V}}(G_{j_{n}},\mathbb{M}_{\mathrm{opt}}(G_{j_{n}}))$
converges to
$\limsup_{n\rightarrow\infty}\operatorname{perf_{V}}(G_{n},\mathbb{M}_{\mathrm{opt}}(G_{n}))$.

Now do the previous procedure on the sequence of
$(G_{j_{n}},o_{j_{n}},f_{j_{n}})$ to find a subsequence $l_{n}$ such that
$(G_{l_{n}},o_{l_{n}},f_{l_{n}})$ converges weakly to some $(\mathbb{T},g)$.
Set $\mathbb{M}$ the matching on $\mathbb{T}$ such that
$\mathbbm{1}_{\mathbb{M}}=g$, then $\mathbb{M}$ is at most optimal by
definition so it has less performance than $\mathbb{M}_{h}$:

$\limsup_{n\rightarrow\infty}\operatorname{perf_{V}}(G_{n},\mathbb{M}_{\mathrm{opt}}(G_{n}))=\operatorname{perf_{V}}(\mathbb{T},\mathbb{M})\leq\operatorname{perf_{V}}(\mathbb{T},\mathbb{M}_{h}).$

We have thus shown that every subsequence of
$(G_{n},o_{n},M_{\mathrm{opt}}(G_{n}))$ has a locally convergent subsequence
to some $(\mathbb{T},\mathbb{M})$ where $\mathbb{M}$ is an at most optimal
matching on $\mathbb{T}$.

###  4.2 Optimality of limits of subsequences

In this section, we carry out the hard part of the proof of Proposition 16. We
want to reconstruct a quasi matching on $G_{n}=(V_{n},E_{n})$ from
$(\mathbb{T},\mathbb{M}_{h})$. The crucial idea is, for every $(i,j)\in
V_{n}^{2}$, to compute the probability that $(i,j)\in\mathbb{M}_{h}$
conditionally on the $H$-neighbourhood of $o$ in $\mathbb{T}$ being the
corresponding one of $(i,j)$ in $G_{n}$. Informally, this constructs a "score"
matrix where each score is the likelihood of matching $(i,j)$ by looking up to
depth $H$.

The first hurdle is that the $H$\- neighbourhood of $(i,j)$ in $G_{n}$ needs
not to be a tree, so we will consider the universal cover of $G_{n}$ rooted at
$(i,j)$ instead, and control the resulting error.

Second, we will show that, by completing the diagonal with the probability
that $i$ is unmatched, we create, with a small error, a symmetric stochastic
matrix.

Finally, this means that with a small error as $n\rightarrow\infty$, we
created a random symmetric stochastic matrix on $(V_{n})^{2}$ that we
decompose into a convex combination of involution matrices with the Birkhoff-
Von Neumann theorem, which we reinterpret as a random matching.

By construction, this random matching on $G_{n}$ will have the same
performance as $(\mathbb{T},\mathbb{M}_{h})$ with asymptotically small error,
which concludes.

####  4.2.1 Score function on edges of finite graphs

Let $(i,j)\in V_{n}^{2}$, we define $G_{n,\infty}^{(i,j)}$ as $\emptyset$ if
$(i,j)$ is not an edge of $G_{n}$, and as the universal cover
$G_{n,\infty}^{(i,j)}$ of $G_{n}$ rooted at $(i,j)$ if $(i,j)$ is an edge of
$G_{n}$. This cover is the tree of non-backtracking trajectories from the edge
$(i,j)$. Namely, when $(i,j)$ is an edge of $G_{n}$, $G_{n,\infty}^{(i,j)}$ is
a tree rooted at the edge $(i,j)$, children of $j$ children of $i$ (resp. $j$)
are the neighbours of $i$ (resp. $j$) in $G_{n}$, with $j$ (resp. $i$
excluded). The children of any vertex $v$ with parent $v^{\prime}$ are then
the neighbours in $G_{n}$ of $v$, with $v^{\prime}$ excluded. See Figure 14
for an illustration. For $H\geq 0$, we set
$G_{n,H}^{(i,j)}:=N_{H}(G_{n,\infty}^{(i,j)})$.

Figure 14: Example of the universal cover of an edge-rooted graph.

We will need the following that translates the fact that the universal cover
of $G_{n}$ converges locally to the same limit as $G_{n}$.

######  Lemma 18.

Let $(i,j)$ be chosen uniformly in $(V_{n})^{2}$, then:

$G_{n,\infty}^{(i,j)}|(i,j)\in
E_{n}\underset{n\rightarrow\infty}{\overset{loc}{\longrightarrow}}\mathbb{T}.$

###### Proof of Lemma 18.

Fix $H>0$, $G_{n}$ converges locally to $\mathbb{T}$ so:

$\mathbb{P}\left(N_{H}(G_{n},(i,j))|(i,j)\in E_{n},(i,j)\text{ uniformly
chosen})\text{ is a
tree}\right)\underset{n\rightarrow\infty}{\longrightarrow}\mathbb{P}\left(N_{H}(\mathbb{T})\text{
is a tree}\right)=1.$

So w.h.p $N_{H}((G_{n},(i,j)))$ is a tree, in which case the universal cover
of $G_{n}$ rooted on $o_{n}$ up to height $H$ coincides with $G_{n}$. The
conclusion follows. ∎

Let $\hat{\lambda}$ be the law of the UBGW tree of i.i.d weights $\omega$ and
reproduction law $\pi$, let $\hat{\lambda}_{n}$ be the measure arising from
$G_{n,\infty}^{(i,j)}$ conditionally on $(i,j)\in E_{n}$ and $i,j$ picked
uniformly. We also denote by $\hat{\lambda}_{H}$ and $\hat{\lambda}_{n,H}$ the
corresponding measures when restricted to the space of trees of height $H$.
Lemma 18 states that:

$\forall
H>0,\hat{\lambda}_{n,H}\overset{weak}{\underset{n\rightarrow\infty}{\longrightarrow}}\hat{\lambda}_{H}.$

From $(\mathbb{T},\mathbb{M}_{h})$, we define a function on the space of
rooted graphs $\hat{\mathcal{G}}^{*}$ in the following way:

$g(T)=\mathbb{P}(o\in\mathbb{M}|\mathbb{T}=T),\forall
T\in\hat{\mathcal{G}}^{*},$ (21)

where it is seen as a Radon-Nikodym density.

Integrating with regards to the second marginal, we can rewrite
$\operatorname{perf_{E}}(\mathbb{T},\mathbb{M}_{h})$ as

$\operatorname{perf_{E}}(\mathbb{T},\mathbb{M}_{h})=\mathbb{E}\left[w(o)\mathbbm{1}_{o\in\mathbb{M}_{h}}\right]=\int_{\hat{\mathcal{G}}^{*}}w(o)g(T)\hat{\lambda}(\mathrm{d}T),$
(22)

For $H>0$, we define the restricted $g_{H}$ as $g_{H}(\emptyset)=0$ and

$g_{H}(T)=\mathbb{P}(o\in\mathbb{M}_{h}|N_{H}(\mathbb{T})=N_{H}(T)),\forall
T\in\hat{\mathcal{G}}^{*}.$ (23)

The function $g_{H}$ can be seen as a conditional expectation if we only
looked at $T$ up to depth $H$. The quantity $g_{H}(T)$ is exactly what we
wanted at the beginning: it returns a matching score for the root if
$\mathbb{M}_{h}$ "sees" $T$ up to depth $H$. For $x\in\mathbb{R}$, define
$g_{H,x}=g_{H}\mathbbm{1}_{w(o)\leq x}$.

Figure 15: Example of a score $q_{i,j,H,x}$ when the $H-$Boundary is a tree.
Here, the score $q_{i,j,1,x}$ is the probability that
$Z(i,j)+Z(j,i)<w(i,j)\leq x$ where $Z(i,j)$ and $Z(j,i)$ are computed from
independent exterior variables $Z$ with law $\zeta_{h}$ (drawn as red arrows)
on the $1-$boundary.

We can finally define our random "score" matrix:

######  Definition 4.1.

$Q_{H,n,x}(G_{n}):=\left(q_{i,j,H,n,x}\right)_{(i,j)\in V_{n}^{2}}$ is a
$|V_{n}|\times|V_{n}|$ random matrix with:

$\forall(i,j)\in V_{n}^{2},i\neq
j,\,q_{i,j,H,n,x}:=g_{H,x}(G_{n,\infty}^{(i,j)})$

and $q_{j,j,H,n,x}:=1-\sum_{i\neq j}q_{j,i,H,n,x}$ for $j\in V_{n}$.

We will use several intermediary results which proofs are postponed to
Subsection 4.2.3. For all $n\in\mathbb{N}$ . Let $w_{i,j}$ be the weights of
$(i,j)$ in $(V_{n})^{2}$ (we set it as $0$ if the edge is not present).

######  Lemma 19.

The matrices $Q_{H,n,x}$ are asymptotically optimal:

$\forall
H>0,\lim_{x\rightarrow\infty}\lim_{n\rightarrow\infty}\mathbb{E}\left[\frac{1}{|V_{n}|}\sum_{(i,j)\in
V_{n}^{2}}q_{i,j,H,n,x}w_{i,j}\right]=\operatorname{perf_{V}}(\mathbb{T},\mathbb{M}_{h}).$
(24)

######  Lemma 20.

The matrices $Q_{H,n,x}$ are asymptotically non-negative:

$\forall
x\in\mathbb{R},\lim_{H\rightarrow\infty}\limsup_{n\rightarrow\infty}\mathbb{E}\left[\frac{1}{|V_{n}|}\sum_{j\in
V_{n}}\left|q_{j,j,H,n,x}\right|_{-}\right]=0.$ (25)

As a consequence, since we defined the matrices $Q_{H,n,x}$ so that the rows
sum to $1$, the matrices $Q_{H,n,x}$ are asymptotically left stochastic. Let
$\text{Birk}_{n}$ be the Birkhoff polytope on $M_{n}(\mathbb{R})$,
$\text{Sym}_{n}$ the subspace of symmetric matrices, $\text{RStoc}_{n}$ the
right stochastic matrices for which every row sums to 1 and $\text{LStoc}_{n}$
the left stochastic matrices for which every column sums to 1.

Now, Lemma 20 controls the distance of the matrix $Q_{H,n,x}$ to
$\text{LStoc}_{|V_{n}|}$. Since $Q_{H,n,x}$ is symmetric, it also controls the
distance to $\text{RStoc}_{|V_{n}|}$. Now, we would like to control the
distance to $\text{Birk}_{|V_{n}|}$.

For this, we need some geometric results: We will write
$\|M\|_{1}=\sum_{i,j}|m_{i,j}|$ for $M_{n}(\mathbb{R})$. We will use the
following proposition that states that if a matrix $M$ is $o(n)$ close to
$\text{LStoc}_{n}$ and $o(n)$ close to $\text{RStoc}_{n}$, then it is $o(n)$
close to $\text{LStoc}_{n}\cap\text{RStoc}_{n}=\text{Birk}_{n}$:

######  Proposition 21.

Assume $M$ has non-negative coefficients.

Assume that there is some $\frac{1}{2}>\varepsilon>0$ such that:

$\sum_{i}\left|\sum_{j}m_{i,j}-1\right|+\sum_{j}\left|\sum_{i}m_{i,j}-1\right|<n\varepsilon$

Then there is some constant $C$ that does not depend on $n$ such that:

$d_{\|\cdot\|_{1}}(M,\mathrm{Birk}_{n})\leq C\varepsilon n.$

By Proposition 21, the distance of $Q_{H,n,x}$ to $\text{Birk}_{|V_{n}|}$ is
thus $o(|V_{n}|)$. We need another geometric lemma that controls the distance
to symmetric bistochastic matrices from the distance to bistochastic matrices
and the distance to symmetric matrices:

######  Lemma 22.

Let $M\in M_{n}(\mathbb{R})$:

$d(M,\mathrm{Sym}_{n}\cap\mathrm{Birk}_{n})\leq
d(M,\mathrm{Sym}_{n})+d(M,\mathrm{Birk}_{n}).$ (26)

Combining Equation (26) with Lemmas 19 and 20, the expected distance of
$Q_{H,n,x}$ to symmetric bistochastic matrices is $o(|V_{n}|)$ as
$n,H\rightarrow\infty$.

####  4.2.2 Proof of the second part of Proposition 16

Fix $\varepsilon,\eta>0$.

Applying Lemma 19 , there exists $H_{\eta}$, $x_{\eta}$ and $N_{\eta}$ big
enough such that for any $n\geq N_{\eta}$:

$\mathbb{E}\left[\frac{1}{|V_{n}|}\sum_{(i,j)\in
V_{n}^{2}}q_{i,j,H_{\eta},n,x_{\eta}}w_{i,j}\right]>\operatorname{perf_{V}}(\mathbb{T},\mathbb{M}_{h})-\eta.$

Now, applying what we just showed at the end of the previous subsection, by
taking $H_{\eta,\varepsilon}$ and $N_{\eta,\varepsilon}$ big enough, such that
for any $n\geq N_{\eta,\varepsilon}$, the previous inequality holds along
with:

$\mathbb{E}\left[\frac{1}{|V_{n}|}d(Q_{H_{\eta,\varepsilon},n,x_{\eta}},\mathrm{Birk}_{|V_{n}|}\cap\mathrm{Stoc}_{|V_{n}|})\right]\leq\frac{\varepsilon^{2}}{x_{\eta}}.$

Applying Markov inequality:

$\mathbb{P}\left[\frac{1}{|V_{n}|}d(Q_{H_{\eta,\varepsilon},n,x_{\eta}},\mathrm{Birk}_{|V_{n}|}\cap\mathrm{Stoc}_{|V_{n}|})\geq\frac{\varepsilon}{x_{\eta}}\right]\leq\varepsilon$

We drop the dependency of $H$ and $x$ in $\eta$ and $\varepsilon$ from now on
to ease notation. With probability at least $(1-\varepsilon)$, there exists
some bistochastic symmetric matrix $\hat{Q}_{H,n,x}$ such that
$\|\hat{Q}_{H,n,x}-Q_{H,n,x}\|_{1}\leq\frac{\varepsilon}{x_{\eta}}|V_{n}|$.
Now apply Birkhoff-Von Neumann theorem on $\hat{Q}_{H,n,x}$ and
$\hat{Q}_{H,n,x}^{T}$ to show that $\hat{Q}_{H,n,x}$ is the convex combination
of matrices of the form $\frac{P+P^{T}}{2}$ where $P$ is a permutation matrix.
This shows that $\hat{Q}_{H,n,x}$ is a convex combination of involution
matrices.

Involution matrices are in bijection with the set of matchings on the complete
graph $K_{|V_{n}|}$. Therefore $\hat{Q}_{H,n,x}$ encodes a random matching
$M(\hat{Q}_{H,n,x})$ on $G_{n}$ (we just leave edges unmatched if they are not
in $G_{n}$). On the event where $\hat{Q}_{H,n,x}$ exists we have:

$\displaystyle\operatorname{perf_{V}}(G_{n},M(\hat{Q}_{H,n,x}))$
$\displaystyle=\mathbb{E}\left[\frac{1}{|V_{n}|}\sum_{(i,j)\in
V_{n}^{2}}\hat{q}_{i,j,H,n,x}w_{i,j}\right]$
$\displaystyle>\mathbb{E}\left[\frac{1}{|V_{n}|}\sum_{(i,j)^{2}\in
V_{n}^{2}}q_{i,j,H,n,x}w_{i,j}\right]-\mathbb{E}\left[\frac{1}{|V_{n}|}\sum_{(i,j)^{2}\in
V_{n}^{2}}|q_{i,j,H,n,x}-\hat{q}_{i,j,H,n,x}|w_{i,j}\right]$
$\displaystyle>\operatorname{perf_{V}}(\mathbb{T},\mathbb{M}_{h})-\eta-\mathbb{E}\left[\frac{1}{|V_{n}|}\sum_{(i,j)^{2}\in
V_{n}^{2}}|q_{i,j,H,n,x}-\hat{q}_{i,j,H,n,x}|w_{i,j}\right]$
$\displaystyle>\operatorname{perf_{V}}(\mathbb{T},\mathbb{M}_{h})-\eta-\mathbb{E}\left[\frac{1}{|V_{n}|}\sum_{(i,j)\in
V_{n}^{2}}|q_{i,j,H,n,x}-\hat{q}_{i,j,H,n,x}|w_{i,j}(\mathbbm{1}_{w_{i,j}\leq
x})\right]$
$\displaystyle>\operatorname{perf_{V}}(\mathbb{T},\mathbb{M}_{h})-\eta-x\frac{d(Q_{H,n,x},\hat{Q}_{H,n,x})}{|V_{n}|}$
$\displaystyle>\operatorname{perf_{V}}(\mathbb{T},\mathbb{M}_{h})-\eta-x\frac{\varepsilon}{x}$
$\displaystyle>\operatorname{perf_{V}}(\mathbb{T},\mathbb{M}_{h})-\eta-\varepsilon.$

We have shown that with probability at least $(1-\varepsilon)$ there exists a
random matching $M(\hat{Q}_{H,n,x})$ on $G_{n}$ whose performance is at least
$\operatorname{perf_{V}}(\mathbb{T},\mathbb{M}_{h})-\eta-\varepsilon$. In
particular, $\mathbb{M}_{\mathrm{opt}}(G_{n})$ has to do better. So

$\operatorname{perf_{V}}(G_{n},\mathbb{M}_{\mathrm{opt}}(G_{n}))\geq(1-\varepsilon)\operatorname{perf_{V}}(G_{n},M(\hat{Q}_{H,n,x}))\geq(1-\varepsilon)\left[\operatorname{perf_{V}}(\mathbb{T},\mathbb{M}_{h})-\eta-\varepsilon\right].$

Taking the limit inferior we get:

$\liminf_{n\rightarrow\infty}\operatorname{perf_{V}}(G_{n},\mathbb{M}_{\mathrm{opt}}(G_{n}))\geq\operatorname{perf_{V}}(\mathbb{T},\mathbb{M}_{h}).$

In conclusion, we showed that:

$\lim_{n\rightarrow\infty}\operatorname{perf_{V}}(G_{n},\mathbb{M}_{\mathrm{opt}}(G_{n}))=\operatorname{perf_{V}}(\mathbb{T},\mathbb{M}_{h}),$

and as such, all locally convergent subsequences of
$(G_{n},\mathbb{M}_{\mathrm{opt}}(G_{n}))$ converge to an optimal matching
couple $(\mathbb{T},\mathbb{M})$ as desired.

####  4.2.3 Proof of the technical lemmas

We start by proving a stronger version of Lemma 19, where we show the
asymptotic correspondence not just for $w_{i,j}$ but for a well-behaved local
function.

######  Definition 4.2.

Let $f:\hat{\mathcal{G}}^{*}\mapsto\mathbb{R}$. We say that $f$ is a local
function if there exists some $H>0$ such that for any
$T,T^{\prime}\in\hat{\mathcal{G}}^{*}$,

$N_{H}(T)=N_{H}(T^{\prime})\Rightarrow f(T)=f(T^{\prime}).$

######  Proposition 23.

Let $f$ be a non-negative local function. For every ${i,j}\in E_{n}$, set
$f_{i,j}=f(G_{n},(i,j))$, which is f evaluated on $G_{n}$ rooted at $(i,j)$
and $f_{i,j}=0$ if $\\{i,j\\}\notin E_{n}$. Assume $f$ is either bounded or
Lipschitz with respect to the weight of the root $w(o)$, then:

$\exists H_{f}\in\mathbb{N},\forall
H>H_{f},\lim_{x\rightarrow\infty}\lim_{n\rightarrow\infty}\mathbb{E}\left[\frac{1}{|V_{n}|}\sum_{(i,j)\in
V_{n}^{2}}q_{i,j,H,n,x}f_{i,j}\right]=\frac{\mathbb{E}_{N\sim\pi}[N]}{2}\mathbb{E}\left[f(\mathbb{T},o)\mathbbm{1}_{o\in\mathbb{M}_{h}}\right].$
(27)

Lemma 19 follows by taking $f(G,o)=w(o)$ that is local with $H=0$.

###### Proof of Proposition 23.

Let $H_{f}$ be the integer arising from the locality of $f$. First we will
condition on $(i,j)$ being in $E_{n}$, else $f_{i,j}=0$.

$\mathbb{E}\left[\frac{1}{|V_{n}|}\sum_{(i,j)\in
V_{n}^{2}}q_{i,j,H,n,x}f_{i,j}\mathbbm{1}_{(i,j)\in
E_{n}}\right]=\mathbb{E}\left[\frac{2|E_{n}|}{|V_{n}|}\frac{1}{2|E_{n}|}\sum_{(i,j)\in
V_{n}^{2}}q_{i,j,H,n,x}f_{i,j}\mathbbm{1}_{(i,j)\in E_{n}}\right]$

Notice that $2|E_{n}|$=$|\overset{\rightarrow}{E}_{n}|$. We will now integrate
with respect to $\hat{\lambda}_{n,H}$ for $H>H_{f}$:

$\mathbb{E}\left[\frac{1}{|\overset{\rightarrow}{E}_{n}|}\sum_{(i,j)\in
V_{n}^{2}}q_{i,j,H,n,x}f_{i,j}\right]=\int_{\hat{\mathcal{G}}^{*}}g_{H}(T)\mathbbm{1}_{w(o)\leq
x}f(T)\mathrm{d}\hat{\lambda}_{n,H}(T)$

Let $M$ be the Lipschitz constant of $f$ on the weights of $N_{H}(T)$. As
$f\mathbbm{1}_{w(o)\leq x}$ is bounded by $Mx$ and $g_{H}$ by $1$, we have
that

$\int_{\hat{\mathcal{G}}^{*}}g_{H}(T)\mathbbm{1}_{w(o)\leq
x}f(T)\mathrm{d}\hat{\lambda}_{n,H}(T)\underset{n\rightarrow\infty}{\longrightarrow}\int_{\hat{\mathcal{G}}^{*}}g_{H}(T)\mathbbm{1}_{w(o)\leq
x}f(T)\mathrm{d}\hat{\lambda}_{H}(T).$

On the other hand:

$\mathbb{E}\left[\frac{2|E_{n}|}{|V_{n}|}\right]\underset{n\rightarrow\infty}{\overset{\mathcal{P}}{\longrightarrow}}\mathbb{E}_{N\sim\pi}[N]$

So by Slutsky’s lemma:

$\mathbb{E}\left[\frac{2|E_{n}|}{|V_{n}|}\frac{1}{|\overset{\rightarrow}{E}_{n}|}\sum_{(i,j)\in
V_{n}^{2}}q_{i,j,H,n,x}f_{i,j}\mathbbm{1}_{(i,j)\in
E_{n}}\right]\underset{n\rightarrow\infty}{\longrightarrow}\mathbb{E}_{N\sim\pi}[N]\int_{\hat{\mathcal{G}}^{*}}g_{H}(T)\mathbbm{1}_{w(o)\leq
x}f(T)\mathrm{d}\hat{\lambda}_{H}(T)$

Now taking $x\rightarrow\infty$ by monotone convergence theorem:

$\int_{\hat{\mathcal{G}}^{*}}g_{H}(T)\mathbbm{1}_{w(o)\leq
x}f(T)\mathrm{d}\hat{\lambda}_{H}(T)\underset{n\rightarrow\infty}{\longrightarrow}\int_{\hat{\mathcal{G}}^{*}}g_{H}(T)f(T)\mathrm{d}\hat{\lambda}_{H}(T).$

Since we only look up to height $H$, we can substitute $f$ by $f_{H}$ so by
law of total expectation:

$\int_{\hat{\mathcal{G}}^{*}}g_{H}(T)f(T)\mathrm{d}\hat{\lambda}_{H}(T)=\int_{\hat{\mathcal{G}}^{*}}g(T)f(T)\mathrm{d}\hat{\lambda}(T)=\mathbb{E}[f(\mathbb{T},o)\mathbbm{1}_{o\in\mathbb{M}}].$

So the limit is

$\mathbb{E}_{N\sim\pi}[N]\mathbb{E}[f(\mathbb{T},o)\mathbbm{1}_{o\in\mathbb{M}}].$

When $f(T,o)=w(o)$, then we recover

$\mathbb{E}_{N\sim\pi}[N]\mathbb{E}[w(o)\mathbbm{1}_{o\in\mathbb{M}}]=\mathbb{E}_{N\sim\pi}[N]\operatorname{perf_{E}}[\mathbb{T},\mathbb{M}_{h}]=\operatorname{perf_{V}}[\mathbb{T},\mathbb{M}_{h}]$

by Proposition 6. ∎

###### Proof of Lemma 20.

For this equation, we adopt the vertex-rooted point of view, let $\lambda_{n}$
the law of uniformly vertex rooted $G_{n}$ and $\lambda$ the law of vertex
rooted UBGW, then:

$\mathbb{E}\left[\frac{1}{|V_{n}|}\sum_{j\in
V_{n}}\left|q_{j,j,H,n,x}\right|_{-}\right]=\int_{\mathcal{G}^{*}}\left|1-\sum_{v\sim
o}g_{H}(T,(o,v))\mathbbm{1}_{w(o)\leq
x}\right|_{-}\mathrm{d}\lambda_{n,H}(T).$

Neglecting $\mathbbm{1}_{w(o)\leq x}$ can only increase the negative part, so:

$\int_{\mathcal{G}^{*}}\left|1-\sum_{v\sim
o}g_{H}(T,(o,v))\mathbbm{1}_{w(o)\leq
x}\right|_{-}\mathrm{d}\lambda_{n,H}(T)\leq\int_{\mathcal{G}^{*}}\left|1-\sum_{v\sim
o}g_{H}(T,(o,v))\right|_{-}\mathrm{d}\lambda_{n,H}(T).$

Now with a proof almost identical to the one of Lemma 18, we can prove that
for any $H$, $\lambda_{n,H}$ converges weakly to $\lambda_{H}$. Since
$\mathbb{E}_{N\sim\pi}[N]<\infty$, we can first integrate on $\deg(o)$ to
bound the integrand by $\mathbb{E}_{N\sim\pi}[N]$. So as $n\rightarrow\infty$,
we get:

$\int_{\mathcal{G}^{*}}\left|1-\sum_{v\sim
o}g_{H}(T,(o,v))\right|_{-}\mathrm{d}\lambda_{H}(T)$

Now:

$\sum_{v\sim o}g(T,(o,v))=\mathbb{P}\left(o\text{ is matched by
}\mathbb{M}|\mathbb{T}=T\right)\leq 1\,\,\,\,\lambda-\text{almost surely on
}\mathcal{G}^{*}$

So applying $L^{1}$ martingale convergence theorem as $H\rightarrow\infty$, we
recover:

$\int_{\mathcal{G}^{*}}\left|1-\sum_{v\sim
o}g_{H}(T,(o,v))\right|_{-}\mathrm{d}\lambda(T)=0.$

∎

###### Proof of Proposition 21.

We will modify $M$ into a bistochastic matrix with a load-balancing algorithm.
The idea is to redistribute the load of the heaviest rows to the lightest rows
while preserving the columns, then redistribute the load of the heaviest
columns to the lightest columns while preserving the rows. At the end of such
an algorithm, every row and every column sums to the average of the columns or
rows at the start.

Set $M^{(0)}=M$, $L_{i}^{(0)}=\sum_{j}m_{i,j}$, $C_{j}^{(0)}=\sum_{i}m_{i,j}$.
For $t\leq n$, we will do the following:

  * •

Rank $L_{i}^{(t)}$ such that
$L_{k_{1}}^{(t)}=\ldots=L_{k_{p}}^{(t)}>L_{k_{p+1}}^{(t)}\geq\ldots\geq
L_{k_{n}-l}^{(t)}=\ldots=L_{k_{n}}^{(t)}$.

  * •

Set
$(L_{i}^{(t+1)},C_{j}^{(t+1)},m_{i,j}^{(t+1)})\leftarrow(L_{i}^{(t)},C_{j}^{(t)},m_{i,j}^{(t)})$
for now.

Now, while $L_{k_{p}}^{(t+1)}>L_{k_{p+1}}^{(t+1)}$. As each row has a positive
sum, there are some coefficients
$m_{k_{1},j_{1}^{\prime}}^{(t+1)},m_{k_{2},j_{2}^{\prime}}^{(t+1)},...,m_{k_{p},j_{p}^{\prime}}^{(t+1)}>0$.

We will redistribute a fraction of these coefficients along their respective
columns to the rows with the smallest sums. Note that by doing so, the sum of
each column stays unchanged. However, we want the distribution to:

  1. 1.

never distribute more than one of the $m_{k_{i},j_{i}^{\prime}}^{(t+1)}$,

  2. 2.

not exceed $L_{k_{p+1}}^{(t+1)}-L_{k_{p+1}}^{(t)}$ otherwise $p$ has to be
increased,

  3. 3.

not exceed $L_{k_{n-l-1}}^{(t+1)}-L_{k_{n-l}}^{(t+1)}$ otherwise $l$ has to be
increased.

The maximal weight that can be distributed is then

$\alpha^{(t+1)}:=\min\left(\min_{1\leq i\leq
p}\left(m_{k_{i},j_{i}^{\prime}}^{(t+1)}\right),L_{k_{p}}^{(t+1)}-L_{k_{p+1}}^{(t+1)},\frac{p}{l+1}\left[L_{k_{n-l-1}}^{(t+1)}-L_{k_{n-l}}^{(t+1)}\right]\right).$

Thus, we set $m_{k_{i},j_{i}^{\prime}}^{(t+1)}\leftarrow
m_{k_{i},j_{i}^{\prime}}^{(t+1)}-\alpha^{(t+1)}$ and
$L_{k_{i}}^{(t+1)}\leftarrow L_{k_{i}}^{(t+1)}-\alpha^{(t+1)}$ for $1\leq
i\leq p$ , $m_{k_{i},j_{i}^{\prime}}^{(+1)}\leftarrow
m_{k_{i},j_{i}^{\prime}}^{(+1)}+\frac{p}{l+1}\alpha^{(t+1)}$ and
$L_{k_{i}}^{(t+1)}\leftarrow L_{k_{i}}^{(t+1)}+\frac{p}{l+1}\alpha^{(t+1)}$
for $n-l\leq i\leq n$.

As long the second condition is not satisfied, we recompute $l$, redraw
coefficients $m$ and repeat. This is possible as long as the sum of each line
is positive, which is the case since we only increased the minimum of the
$L_{i}^{(t+1)}$ away from zero. At every step, the algorithm increases $p$ by
at least 1, and at step $n$ every line sums to the same amount. Furthermore,
it has not changed the value of any $C_{j}$.

We then apply the same algorithm to the columns in order to obtain a matrix
$\tilde{M}$ whose rows and columns sum to the same amount $\hat{L}$, which is
$\hat{L}:=\frac{1}{n}\sum_{i,j}m_{i,j}$. Finally we output
$S:=\frac{1}{\hat{L}}\tilde{M}$ that is a bistochastic matrix.

It remains to bound $\|S-M\|_{1}$. Tracking the values of $L_{i}$ over the
course of the algorithm, we see that the total modification to its
coefficients is $L_{i}-\hat{L}$ during the first step and then $C_{j}-\hat{L}$
during the second step. So the total amount of modification we did before
dividing by $\hat{L}$ is:

$\sum_{i}|L_{i}^{(0)}-\hat{L}|+\sum_{j}|C_{j}^{(0)}-\hat{L}|.$ (28)

When we divide by $\hat{L}$, we make a modification of at most

$\sum_{i,j}\tilde{m}_{i,j}\left|1-\frac{1}{\hat{L}}\right|.$ (29)

First, we see that $\hat{L}$ is close to $1$:

$\displaystyle|\hat{L}-1|$
$\displaystyle=\left|\frac{1}{n}\sum_{i}L_{i}-1\right|=\frac{1}{n}\left|\sum_{i}L_{i}-\sum_{i}\frac{1}{n}\right|$
$\displaystyle\leq\frac{1}{n}\sum_{i}\left|L_{i}-1\right|$
$\displaystyle\leq\varepsilon.$

We can now bound (28):

$\displaystyle\sum_{i}|L_{i}^{(0)}-\hat{L}|+\sum_{j}|C_{j}^{(0)}-\hat{L}|$
$\displaystyle\leq\sum_{i}\left(|L_{i}^{(0)}-1|+|1-\hat{L}|\right)+\sum_{j}\left(|C_{j}^{(0)}-1|+|1-\hat{L}|\right).$
$\displaystyle<\sum_{i}|L_{i}-1|+\sum_{j}|C_{j}-1|+2n|1-\hat{L}|$
$\displaystyle<n\varepsilon+2n\varepsilon=3n\varepsilon.$

For (29), since $\frac{1}{2}>\varepsilon>0$, we have
$|1-\frac{1}{\hat{L}}|=|\frac{1-\hat{L}}{\hat{L}}|<4\varepsilon$. Finally, we
have that
$n\hat{L}=\sum_{i,j}\tilde{m}_{i,j}=\sum_{i,j}m_{i,j}^{(0)}<n(1+\varepsilon)$.

Summing everything up, we established that:

$\|S-M\|_{1}<3\varepsilon+4n\varepsilon(1+\varepsilon)<12n\varepsilon$

and $C=12$ works. ∎

###### Proof of Lemma 22.

This is true because the Birkhoff polytope is symmetric through the subspace
of symmetric matrices.

$\displaystyle\inf_{S\text{ bistochastic symmetric}}\|M-S\|_{1}$
$\displaystyle\leq\left\|M-\frac{M+M^{T}}{2}\right\|_{1}+\inf_{S\text{
bistochastic symmetric}}\left\|\frac{M+M^{T}}{2}-S\right\|_{1}$
$\displaystyle\leq d(M,\text{Sym}_{n})+\inf_{S\text{ bistochastic
symmetric}}\left\|\frac{M+M^{T}}{2}-\frac{S+S^{T}}{2}\right\|_{1}.$

Now take $S^{*}$ such that $d(M,\text{Birk}_{n})=\|M-S^{*}\|_{1}$, then
$\frac{S^{*}+S^{*T}}{2}$ is bistochastic symmetric so:

$\displaystyle\inf_{S\text{ bistochastic symmetric}}\|M-S\|_{1}$
$\displaystyle\leq d(M,\text{Sym}_{n})+\inf_{S\text{ bistochastic
symmetric}}\left\|\frac{M+M^{T}}{2}-\frac{S+S^{T}}{2}\right\|_{1}$
$\displaystyle\leq
d(M,\text{Sym}_{n})+\left\|\frac{M+M^{T}}{2}-\frac{S^{*}+S^{*T}}{2}\right\|_{1}$
$\displaystyle\leq
d(M,\text{Sym}_{n})+\left\|\frac{M-S^{*}}{2}\right\|_{1}+\left\|\frac{M^{T}-S^{*T}}{2}\right\|_{1}$
$\displaystyle\leq d(M,\text{Sym}_{n})+d(M,\text{Birk}_{n}).$

∎

##  5 Proof of the main results

This Section is devoted to the remaining of the proof of Theorem 1 and to the
proof of Theorem 2.

###  5.1 Convergence of optimally matched graphs (Theorem 1)

Let us conclude the proof of Theorem 1 by combining the main results of
Section 3 and Section 4.

Section 4 shows that every subsequence of
$(G_{n},o_{n},M_{\mathrm{opt}}(G_{n}))$ has a subsequence that converges
locally to some $(\mathbb{T},\mathbb{M})$ where $\mathbb{M}$ is an optimal
matching on $\mathbb{T}$. Section 3 shows that the only optimal matching in
law on the UBGW tree $\mathbb{T}$ is $\mathbb{M}_{h}$. So every subsequence of
$(G_{n},o,M_{\mathrm{opt}}(G_{n}))$ has a subsequence that converges to
$(\mathbb{T},\mathbb{M}_{h})$. We deduce that
$(G_{n},o,M_{\mathrm{opt}}(G_{n}))$ converges locally to
$(\mathbb{T},\mathbb{M}_{h})$. This concludes the proof of Theorem 1.

###  5.2 Uniqueness of the message passing distribution (Theorem 2)

We now turn to the proof of Theorem 2. The idea is to recover the law of
$\zeta_{h}$ from families of statistics on $\mathbb{M}_{h}$.

As a warm-up, we first treat the simple case where
$\mathrm{supp}(\omega)=\mathbb{R}_{+}$. Take $h_{1}$ and $h_{2}$ two solutions
to $\eqref{eq:hequation}$, they both produce optimal matchings
$\mathbb{M}_{h_{1}}$ and $\mathbb{M}_{h_{2}}$ on $\mathbb{T}$. From our
previous results, this matching is unique in law so both matchings have the
same law. Any event that is locally measurable with respect to the couple
graph and matching will have equal probability for $\mathbb{M}_{h_{1}}$ and
$\mathbb{M}_{h_{2}}$. We will look at the probability that the root is matched
conditioned on the weight being $x\in\mathbb{R}_{+}$:

$\mathbb{P}\left(w(o)\in\mathbb{M}|w(o)=x\right)$

as a Radon-Nikodym derivative.

Evaluated for $\mathbb{M}_{h_{1}}$ and $\mathbb{M}_{h_{2}}$, this yields:

$\mathbb{P}\left(Z_{h_{1}}+Z_{h_{1}}^{\prime}<x\right)=\mathbb{P}\left(Z_{h_{2}}+Z_{h_{2}}^{\prime}<x\right),$

where $Z_{h_{1}},Z_{h_{2}},Z_{h_{1}}^{\prime},Z_{h_{2}}^{\prime}$ are
independent variables, and the cdf of $Z_{h_{1}},Z_{h_{1}}^{\prime}$ is
$h_{1}$, the cdf of $Z_{h_{2}},Z_{h_{2}}^{\prime}$ is $h_{2}$. This shows that
for any $t\in\mathbb{R}$:

$\mathbb{E}\left[e^{itZ_{h_{1}}}\right]^{2}=\mathbb{E}\left[e^{it(Z_{h_{1}}+Z_{h_{1}}^{\prime})}\right]=\mathbb{E}\left[e^{it(Z_{h_{2}}+Z_{h_{2}}^{\prime})}\right]=\mathbb{E}\left[e^{itZ_{h_{2}}}\right]^{2}$

So the square of the characteristic functions of $\zeta_{h_{1}}$ and
$\zeta_{h_{2}}$ are the same. Since the support of $\omega$ is
$\mathbb{R}_{+}$, the support of $\zeta_{h_{i}}\subseteq\mathbb{R}_{+}$ and
the characteristic functions are analytically extendable to
$\\{\imaginary(z)<0\\}$. Now because both characteristic functions evaluate to
$1$ at $0$ and their square are the same, we deduce that they coincide in some
neighbourhood of $0$. By analyticity, the characteristic functions of
$\zeta_{h_{1}}$ and $\zeta_{h_{2}}$ coincide on
$\left\\{\imaginary(z)<0\right\\}$ and thus $h_{1}=h_{2}$.

This reasoning breaks down when the $\mathrm{supp}(\omega)$ has "holes" as we
have no access to the information of $Z$ at $x$ if
$x\notin\mathrm{supp}(\omega)$. To deal with generic supports for $\omega$, we
will consider conditioning on the weights of edges along a path originating
from the root rather than just the weight of the root edge.

Let us assume that $\hat{\pi}_{1}>0$, we will condition on the event that the
weight of the root edge is $w_{0}$ and that the $+$ side of the root is a
simple path $v_{1},v_{2},....,v_{H}$ of length $H$ of weights
$w_{1},....,w_{H}$. We will further condition on the event that $v_{H}$ is
unmatched in the matching $\mathbb{M}_{h}$. The total event of conditioning on
the sequence of weights and $v_{H}$ being unmatched is measurable in the
matching and graph, Figure 16 gives a depiction of the situation.

…$o_{-}$$o_{+}$$v_{1}$$v_{2}$$v_{3}$$v_{H-2}$$w_{0}$$w_{1}$$w_{2}$$w_{3}$$w_{H-1}$$w_{H}$$v_{H-1}$$v_{H}$$Z$$Z^{\prime}$
Figure 16: We look at the event where $v_{H}$ (in the green box) is unmatched
conditionally on the sequence of weights $w_{0},....,w_{H}$.

Now writing $Z=Z_{h}(o_{+},o_{-})$ and $Z^{\prime}=Z_{h}(v_{H-1},v_{H})$,
$v_{H}$ being unmatched is equivalent to:

$\displaystyle\left\\{\max_{u\sim v_{H}}(w(v_{H},u)-Z_{h}(v_{H},u))\leq
0\right\\}$ $\displaystyle=$
$\displaystyle\left\\{Z^{\prime}=\max\left(0,\max_{u\sim v_{H},u\neq
v_{H-1}}(w(v_{H},u)-Z_{h}(v_{H},u))\right)=0,w(v_{H},v_{H-1})-Z_{h}(v_{H},v_{H-1})\leq
0\right\\}$ $\displaystyle=$ $\displaystyle\left\\{Z^{\prime}=0,w_{H}\leq
Z_{h}(v_{H},v_{H-1})\right\\}.$

We will show in Corollary 3 that $\mathbb{P}(Z^{\prime}=0)=h(0)$ is invariant
for $h=h_{1}$ or $h=h_{2}$ , which then implies that:

$\displaystyle\mathbb{P}(w_{h}\leq Z_{h}(v_{H},v_{H-1}))$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(w_{H}\leq\max\left(0,w_{H-1}-\max\left(0,w_{H-2}-....-\max\left(0,w_{1}-\max\left(0,w_{0}-Z\right)\right)...\right)\right)\right).$

is invariant for $h=h_{1}$ or $h=h_{2}$. The probability in the previous
display can be written as the following integral:

$G(w_{i}):=\int_{\mathbb{R}_{+}}\mathbbm{1}_{\left(w_{H}\leq\max\left(0,w_{H-1}-\max\left(0,w_{H-2}-....-\max\left(0,w_{1}-\max\left(0,w_{0}-x\right)\right)...\right)\right)\right)}\mathrm{d}\mathbb{P}_{h}(x).$

To simplify notations we will denote the function integrated by

$g(x,w_{i}):=g(x_{,}w_{0},...,w_{H})=\mathbbm{1}_{\left(w_{H}\leq\max\left(0,w_{H-1}-\max\left(0,w_{H-2}-....-\max\left(0,w_{1}-\max\left(0,w_{0}-x\right)\right)...\right)\right)\right)},$

so that

$G(w_{i})=\int_{\mathbb{R}_{+}}g(x,w_{i})\mathrm{d}\mathbb{P}_{h}(x).$

To prove Theorem 2, we will show that for any
$x_{0}\in[0,\sup(\mathrm{supp}(\omega))]$, for $\varepsilon>0$ small enough,
we can recover:

$\displaystyle\mathbb{P}(x_{0}\leq Z<x_{0}+\varepsilon)$

as a difference $G(w_{i})-G(w_{i}^{\prime})$ for $(w_{i})$ and
$(w_{i}^{\prime})$ chosen according to the following Lemma, which suffices to
recover the law of $h$.

…$b$$0$$\overline{u}_{0}$$\underline{u}_{1}$$\overline{u}_{1}$$\underline{u}_{2}$$\overline{u}_{\frac{H}{2}-1}$$\overline{u}_{\frac{H}{2}}=x_{0}$$\underline{u}_{\frac{H}{2}}$$g$
does not change elsewhere if $w_{H}$is modified by $\varepsilon$$g=0$$g=1$
Figure 17: Illustration of Lemma 24 and its consequences.

######  Lemma 24.

Fix $a,b\in\mathbb{R}_{+}$ with $a<b$, $x_{0}\in]0,b[$. There exists $H>0$,
even if $x_{0}>\frac{b}{2}$ and odd if not, and a sequence
$(w_{0},w_{1},....,w_{H})\in[a,b]^{H+1}$ satisfying the following:

  1. 1.

$\sum_{i=0}^{H}(-1)^{i}w_{H-i}=x_{0}.$

  2. 2.

The sequence $\overline{u}_{k}:=\sum_{i=0}^{2k}(-1)^{i}x_{i}$ is positive
decreasing.

  3. 3.

The sequence $\underline{u}_{k}:=\sum_{i=0}^{2k+1}(-1)^{i}x_{i}$ is
increasing.

  4. 4.

For any $1<k\leq H$, $\sum_{i=k}^{H}(-1)^{i}w_{H-i}\neq 0$.

  5. 5.

Finally, $\overline{u}_{H}>\underline{u}_{H}$.

###### Proof of Lemma 24.

Let’s first show the lemma while disregarding condition 4. Let us assume
$x_{0}>\frac{b}{2}$, the other case being symmetrical. Take
$N=\lfloor\frac{(b-x_{0})}{b-a}\rfloor$, for $k<N$, pick $w_{2k}=a$ and
$w_{2k+1}=b$. Then $\overline{u}_{k}=b-k(b-a)$ is in decreasing and
$\underline{u}_{k}=k(b-a)$ is increasing. Finally, pick
$w_{2N}=x_{0}+\underline{u}_{N}=x_{0}+\lfloor\frac{(b-x_{0})}{b-a}\rfloor(b-a)$.
This choice is possible as $(b-x_{0})-(b-a)<\underline{u}_{N}\leq(b-x_{0})$.
Then $\overline{u}_{N}=w_{2N}-\underline{u}_{N}=x_{0}$ by construction, and
$u_{N}<u_{N-1}$. The assumption $x_{0}>\frac{b-a}{2}$ also implies that
$\overline{u}_{N}>\underline{u}_{N}$.

Now if we want to obtain condition 4. , we just need to pick
$w_{2k}=a+\epsilon_{k}$ and $w_{2k+1}=b-\epsilon_{k}^{\prime}$ with
$(\epsilon_{k},\epsilon_{k}^{\prime})$ very small but linearly independent
over $\mathbb{Z}$. The distance loss can just be recovered by doing two more
steps on $N$. ∎

We are now ready to prove the uniqueness in law of the variables $Z$:

###### Proof of Theorem 2.

By assumption on $\omega$ take $b=\sup(\mathrm{supp}(\omega))$ and $a$ such
that $[a,b]\subset\mathrm{supp}(\omega)$. Now for any $h$, take any
$x_{0}\in[0,b]$ and take $H>0$ and a sequence $(w_{0},....,w_{H})$ given by
Lemma 24. We will reuse the notations $\overline{u}_{k}$ and
$\underline{u}_{k}$ from Lemma 24. We will only treat the case when
$x_{0}>\frac{b}{2}$ and $H$ even, the other case being similar.

Recall
$g(x,w_{0},...,w_{H})=g(x_{,}w_{i})=\mathbbm{1}_{\left(w_{H}\leq\max\left(0,w_{H-1}-\max\left(0,w_{H-2}-....-\max\left(0,w_{1}-\max\left(0,w_{0}-x\right)\right)...\right)\right)\right)}$.
Decompose the invariant integral we found earlier:

$\displaystyle\int_{\mathbb{R}_{+}}g(x,w_{i})\mathrm{d}\mathbb{P}_{h}(x)$
$\displaystyle=\int_{0}^{\underline{u}_{0}}g(x,w_{i})\mathrm{d}\mathbb{P}_{h}(x)+\sum_{k=0}^{\frac{H}{2}-1}\int_{\underline{u}_{k}}^{\underline{u}_{k+1}}g(x,w_{i})\mathrm{d}\mathbb{P}_{h}(x)$
$\displaystyle\qquad+\int_{\underline{u}_{\frac{H}{2}-1}}^{\overline{u}_{\frac{H}{2}}}g(x,w_{i})\mathrm{d}\mathbb{P}_{h}(x)$
$\displaystyle\qquad+\sum_{k=0}^{\frac{H}{2}-1}\int_{\overline{u}_{\frac{H}{2}-k}}^{\overline{u}_{\frac{H}{2}-1-k}}g(x,w_{i})\mathrm{d}\mathbb{P}_{h}(x)+\int_{\overline{u}_{0}}^{b}g(x,w_{i})\mathrm{d}\mathbb{P}_{h}(x).$

Our goal is to show that:

  1. 1.

$g$ evaluates to $0$ on the middle interval:

$\forall
x\in\left(\underline{u}_{\frac{H}{2}-1},\overline{u}_{\frac{H}{2}}\right),\,g(x,w_{i})=0.$

  2. 2.

$g$ evaluates to $1$ on the interval just above:

$\forall
x\in\left[\overline{u}_{\frac{H}{2}},\overline{u}_{\frac{H}{2}-1}\right),g(x,w_{i})=1.$

  3. 3.

If we modified $w_{H}$ to $w_{H}+\varepsilon$ for

$\varepsilon<\min_{k\leq H}\left|\sum_{i=k}^{H}(-1)^{i}w_{H-i}\right|,$

then none of the $g(x,w_{i})$’s value would change on the other intervals.

First, in the middle, we have the system of inequalities:

$\displaystyle\forall k\leq\frac{H}{2},\overline{u}_{k}$
$\displaystyle=\sum_{i=0}^{2k}(-1)^{i}w_{i}>x,$ (30) $\displaystyle\forall
k\leq\frac{H}{2},\underline{u}_{k}$
$\displaystyle=\sum_{i=0}^{2k-1}(-1)^{i+1}w_{i}<x.$ (31)

Looking at the inequality for $\overline{u}_{0}=w_{0}>x$ it means that the
last nested $\max(0,w_{0}-x)$ intervening in $g(x,w_{i})$ evaluates at
$w_{0}-x$.

Then looking at the next inequality $\underline{u}_{1}=w_{0}-w_{1}<x$, it is
equivalent to $w_{1}-w_{0}+x>0$ so the next nested $\max(0,w_{1}-w_{0}+x)$
evaluates at $w_{1}-w_{0}+x$.

Unravelling the maximums, we end up with the inequality inside $g$ being:

$w_{H}\leq\sum_{i=0}^{H-1}(-1)^{i}w_{H-1-i}+x.$