But this is precisely the opposite of $\overline{u}_{\frac{H}{2}}>x$, hence
$g(x,w_{i})=0$.

Second, if $x$ is between $\overline{u}_{\frac{H}{2}}$ and
$\overline{u}_{\frac{H}{2}-1}$, then the unravelling we did in the previous
case stays true, the only inequality that becomes reversed is the final one,
so we have:

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

which is the event on which $g=1$, hence $g=1$ on this interval.

Third, if $x$ is not in the previous two intervals, then let
$i_{0}=i_{0}(x,w_{i})$ be the last time the nested maximums evaluate to zero.
Then $g$ being one is equivalent to:

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

and $i_{0}$’s value does not depend on the last values of $w_{i}$, so it does
not depend on $w_{H}$ on those intervals (one can see $i_{0}$ as a stopping
time on $x$ and $w_{i}$). By condition 4. of the lemma, none of these
inequalities change when we modify $w_{H}$ by the prescribed $\varepsilon$, so
$g(x,w_{i})$’s value does not change either.

To conclude, for each of those choices of $w_{i}$, the integral is invariant
for $h=h_{1}$ and$h=h_{2}$, so the variation of the integral by modifying
$w_{H}$ is also the same for both. From what we have just seen, the only
change in the integral occurs around $x_{0}$, hence for all $\varepsilon$
small enough:

$\mathbb{P}_{Z_{h_{1}}\sim\zeta_{h_{1}}}(x_{0}\leq
Z_{h_{1}}<x_{0}+\varepsilon)=\mathbb{P}_{Z_{h_{2}}\sim\zeta_{h_{2}}}(x_{0}\leq
Z_{h_{2}}<x_{0}+\varepsilon).$

This being true for all $x_{0}\in\mathrm{supp}(Z_{h_{1}})$ or
$x_{0}\in\mathrm{supp}(Z_{h_{2}})$, this shows that $Z_{1}$ and $Z_{2}$ must
be of the same law, hence $h_{1}=h_{2}$.

If $\hat{\pi}_{1}=0$, take the smallest $p\geq 1$ such that $\hat{\pi}_{p}>0$
then condition on a sequence of $p$ children at each step up to depth $H$, by
choosing the weights on the other $p-1$ children correctly at each step so
that the $\max$ evaluates on the first children, we can recover the previous
reasoning as the other branches will not intervene in the recursion. ∎

######  Remark.

It should not be too hard to lessen the hypothesis on this proof, the open
question would be whether it remains true had we picked an entirely singular
distribution for $\omega$.

##  6 Applications

In this section, we show a few applications of Theorem 1. Namely, we compute
asymptotics of local statistics using the local convergence.

###  6.1 Optimal matching performance and density

In this entire subsection, we reuse the previous notation: $(G_{n})$ is a
sequence of random graphs that converges locally to a UBGW of reproduction law
$\pi$ and weight law $\omega$ on the edges with $\pi$ and $\omega$ integrable
and $\omega$ atomless. Let $\phi$ be the generating function of $\pi$ and
$\hat{\phi}$ be $\frac{\phi^{\prime}}{\phi^{\prime}(1)}$. In particular,
$\mathbb{E}_{N\sim\pi}[N]=\phi^{\prime}(1)$. The function $h$ is the solution
to Equation 9, and the family $Z_{h}(u,v)$ is the associated process on
$\mathbb{T}$. Finally, $\zeta_{h}$ the law for which $h$ is the cumulative
distribution function.

Let $\mathbb{M}_{\mathrm{opt}}(G_{n})$ be any optimal matching on $G_{n}$ then
applying the theorem to the local function
$f=w(o)\mathbbm{1}_{o\in\mathbb{M}}$ and $f=\mathbbm{1}_{o\in\mathbb{M}}$
gives Corollary 3, which we restate with slightly more detail:

######  Corollary 25.

The asymptotics of the average cost per edge and edge density can be computed
on the limiting tree. Let $W$ of law $\omega$, $Z$ and $Z^{\prime}$ of law
$\zeta_{h}$ such that $(W,Z_{h},Z_{h}^{\prime})$ are mutually independent.
Then:

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

In particular, this implies the not-so-obvious fact that every solution $h$ to
Equation (9) shares the same value for $h(0)$.

###### Proof.

The only thing to prove is the last equality
$\mathbb{E}\left[\mathbbm{1}_{Z_{h}+Z_{h}^{\prime}<W}\right]=\frac{1-\phi(\hat{\phi}^{-1}(h(0)))}{\phi^{\prime}(1)}$.
Let $g(u)=\hat{\phi}(1-u)$, $g^{-1}(u)=1-\hat{\phi}^{-1}(u)$,
$G(u)=-\frac{\phi(1-u)}{\phi^{\prime}(1)}$ be a antiderivative of $g$:

$\displaystyle\mathbb{P}(Z_{h}+Z_{h}^{\prime}<W)$
$\displaystyle=\mathbb{E}_{W}[P(Z_{h}+Z_{h}^{\prime}<W)]$
$\displaystyle=\mathbb{E}_{W}\left[\int_{\mathbb{R}}\mathbb{P}(Z_{h}+s<W)\mathrm{d}\mathbb{P}_{Z_{h}^{\prime}}(s)\right]$
$\displaystyle=\mathbb{E}_{W}\left[\int_{\mathbb{R}}\mathbb{P}(Z_{h}<W-s)\mathrm{d}h(s)\right]$
$\displaystyle=\mathbb{E}_{W}\left[\int_{\mathbb{R}}h(W-s)\mathrm{d}h(s)\right]$
$\displaystyle=\int_{\mathbb{R}}\mathbb{E}_{W}[h(W-s)]\mathrm{d}h(s)$

Using the fact that $h$ is solution to Equation 9 we get

$\displaystyle\mathbb{P}(Z_{h}+Z_{h}^{\prime}<W)$
$\displaystyle=\int_{\mathbb{R}_{+}}(1-\hat{\phi}^{-1}(h(s)))\mathrm{d}h(s).$

From there, elementary calculus gives

$\displaystyle\mathbb{P}(Z_{h}+Z_{h}^{\prime}<W)$
$\displaystyle=\int_{\mathbb{R}_{+}}g^{-1}(h(s))\mathrm{d}h(s)$
$\displaystyle=h(0)g^{-1}(h(0))+\int_{h(0)}^{1}g^{-1}(u)\mathrm{d}u$
$\displaystyle=h(0)g^{-1}(h(0))+\left[ug^{-1}(u)-G(g^{-1}(u))\right]_{h(0)}^{1}$
$\displaystyle=-G(0)+G(g^{-1}(h(0)))$
$\displaystyle=\frac{\phi(1)}{\phi^{\prime}(1)}-\frac{\phi(1-(1-\hat{\phi}^{-1}(h(0))))}{\phi^{\prime}(1)}$
$\displaystyle=\frac{1-\phi(\hat{\phi}^{-1}(h(0)))}{\phi^{\prime}(1)}.$

∎

To the best of our knowledge, not many nice formulas like the previous one
exist. We can however state the following, which generalises Corollary 26.

######  Corollary 26.

We can compute the asymptotic of the conditional law of a vertex being matched
in $\mathbb{M}_{\mathrm{opt}}(G_{n})$ when its degree is conditioned to be
$(k+1)$, for a vertex $v$ chosen uniformly in $G_{n}$:

$\lim_{n\rightarrow\infty}\mathbb{P}\left(v\text{ is matched in
}\mathbb{M}_{\mathrm{opt}}(G_{n})|\deg(v)=k+1\right)=1-\hat{\phi}^{-1}(h(0))^{k+1}.$
(34)

Equivalently, for the edge-rooted version, let $(u,v)$ be an uniform directed
edge of $G_{n}$:

$\lim_{n\rightarrow\infty}\mathbb{P}\left((u,v)\in\mathbb{M}_{\mathrm{opt}}(G_{n})|\deg(v)=k+1\right)=\frac{1-\hat{\phi}^{-1}(h(0))^{k+1}}{k+1}.$
(35)

###### Proof.

We will prove the edge-rooted Equation (35). Convergence is obtained by
applying Theorem 1 to the local function
$f=\mathbbm{1}_{o=(o_{-},o_{+})\in\mathbb{M}\deg(o_{+})=k}$. The function $f$
is $1-$local so we condition on the $1-$neighbourhood.

Let us call $Z_{-,i}$ the outwards $Z$ on the minus side and $Z_{+,i}$ the
same on the plus side. They are an i.i.d family of law $\zeta_{h}$. Let us
also write $w_{+,i}$ and $w_{-,i}$ the weights of the corresponding edges that
are also i.i.d of law $\omega$. Finally, let us write $N_{-}$ the number of
children of $o_{-}$ and $N_{+}$ the number of children of $o_{+}$, the family
$(Z_{+,i},w_{+,i},N_{+},Z_{-,i},w_{-,i},N_{-})$ is independent. Refer to
Figure 18 for an illustration.

Figure 18: Illustration of the notations in the proof of Corollary 26.

The limiting quantity is thus

$\mathbb{E}\left[\mathbbm{1}_{Z(o_{-},o_{+})+Z(o_{+},o_{-})<w(o)}|N_{+}=k\right].$

$N_{-}$ is unrestricted so $Z(o_{+},o_{-})$ is simply of law $\zeta_{h}$,
whereas $Z(o_{-},o_{+})=\max_{1\leq i\leq N_{+}}(0,w_{+,i}-Z_{+,i})$. Then the
cdf of $Z_{o_{-},o_{+}}$ conditionally on $N_{+}=k$ satisfies:

$h_{N}(t)=\mathbbm{1}_{t\geq 0}\left(1-\mathbb{E}_{W}[h(W-t)]\right)^{k}$

Indeed,

$\displaystyle\mathbb{P}(Z(o_{-},o_{+})\leq t)$
$\displaystyle=\mathbb{P}\left(\max_{1\leq i\leq N_{+}}(0,w_{+,i}-Z_{+,i})\leq
t|N_{+}=k\right)$ $\displaystyle=\mathbb{P}\left(t\geq
0\right)\prod_{i=1}^{k}\mathbb{P}\left(w_{+,i}-Z_{+,i}\leq t\right)$
$\displaystyle=\mathbbm{1}_{t\geq
0}\left(1-\mathbb{E}_{W}[h(W-t)]\right)^{k}.$

Notice that $1-\mathbb{E}_{W}[h(W-t)]=\hat{\phi}^{-1}(h(t))$ by Equation (9).
Thus:

$h_{N}(t)=\mathbbm{1}_{t\geq 0}\hat{\phi}^{-1}(h(t))^{k}.$

Now we integrate with respect to the value of $Z_{o_{-},o_{+}}$:

$\displaystyle\mathbb{E}\left[\mathbbm{1}_{Z(o_{-},o_{+})+Z(o_{+},o_{-})<w(o)}|N_{+}=k\right]$
$\displaystyle=\hat{\phi}^{-1}(h(0))^{k}\mathbb{P}(Z_{o_{+},o_{-}}<w(o))+\int_{0}^{1}\mathbb{P}\left(Z_{o_{-},o_{+}}+s<w(o)\right)h_{k}^{\prime}(s)\mathrm{d}s.$
$\displaystyle=\hat{\phi}^{-1}(h(0))^{k}\mathbb{E}_{W}[h(W)]+\int_{0}^{1}\mathbb{E}_{W}[h(W-s)]k\frac{h^{\prime}(s)}{\hat{\phi}^{\prime}(h(s))}\hat{\phi}^{-1}(h(s))^{k-1}\mathrm{d}s.$
$\displaystyle=\hat{\phi}^{-1}(h(0))^{k}\left(1-\hat{\phi}^{-1}(h(0))\right)+\int_{0}^{1}\mathbb{E}_{W}\left(1-\hat{\phi}^{-1}(h(s))\right)k\frac{h^{\prime}(s)}{\hat{\phi}^{\prime}(h(s))}\hat{\phi}^{-1}(h(s))^{k-1}\mathrm{d}s.$
$\displaystyle=\hat{\phi}^{-1}(h(0))^{k}\left(1-\hat{\phi}^{-1}(h(0))\right)+\int_{\hat{\phi}^{-1}(h(0))}^{1}k(1-u)u^{k-1}\mathrm{d}u$
$\displaystyle=\hat{\phi}^{-1}(h(0))^{k}\left(1-\hat{\phi}^{-1}(h(0))\right)+\left[u^{k}-\frac{k}{k+1}u^{k+1}\right]_{\hat{\phi}^{-1}(h(0))}^{1}$
$\displaystyle=\hat{\phi}^{-1}(h(0))^{k}\left(1-\hat{\phi}^{-1}(h(0))\right)+\left(1-\frac{k}{k+1}\right)-\left(\left(\hat{\phi}^{(-1)}(h(0))\right)^{k}-\frac{k}{k+1}\left(\hat{\phi}^{(-1)}(h(0))\right)^{k+1}\right)$
$\displaystyle=\frac{1}{k+1}-\frac{1}{k+1}\left(\hat{\phi}^{-1}(h(0))\right)^{k+1}$
$\displaystyle=\frac{1-\left(\hat{\phi}^{-1}(h(0))\right)^{k+1}}{k+1}.$

∎

If we push the conditioning further, the expressions depend on the entire
shape of the function $h$:

######  Corollary 27.

We can compute the asymptotic of the conditional law of a "gap" on one side of
an edge of $\mathbb{M}_{\mathrm{opt}}(G_{n})$ when the side of the gap is
conditioned to be of degree k, let $h_{w}$ be the cdf of $\omega$, then:

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{P}\left(\text{no children of
}v\text{ in }T^{v}\text{ is matched by
}\mathbb{M}_{\mathrm{opt}}(G_{n})|\deg(v)=k+1,(u,v)\in\mathbb{M}_{\mathrm{opt}}(G_{n})\right)$
$\displaystyle=\frac{h(0)^{k}}{1-\hat{\phi}^{-1}(h(0))^{k}}k\mathbb{E}_{(W,Z)\sim\omega\otimes\zeta_{h}}[\mathbbm{1}_{W-Z\geq
0}(h_{w}(W-Z))^{k}].$

###### Proof of Corollary 27.

Figure 19: Illustration of the notations used in the proof of Corollary 27.

Apply Theorem 1 to the corresponding $2-$local function as we have done before
to obtain convergence. Write $v_{i}$ the children of $o_{-}$ in
$\mathbb{T}^{o_{-}}$, $w_{i}$ the weight of $(o_{-},v_{i})$, $v_{i,j}$ the
children of $v_{i}$ and $w_{i,j}$ the weight of $(v_{i},v_{i,j})$,
$Z_{i,j}=Z(v_{i},v_{i,j})$, $Z_{i}=Z(o_{-},v_{i})$,
$Z_{o_{+},o_{-}}=Z(o_{+},o_{-})$ and $w_{o}=w(o_{+},o_{-})$. Finally, write
$N$ the number of children of $o_{-}$ and $N_{i}$ the number of children of
$v_{i}$. See Figure 19 for an illustration. Fix $k\in\mathbb{N}$, the
condition rewrites as :

$B=\left\\{Z_{o_{+},o_{-}}+Z(o_{-},o_{+})<w_{o},N=k\right\\}$

Now, apply the recursive equation on $Z_{o_{+},o_{-}}$ twice to obtain:

$\displaystyle B$
$\displaystyle=\left\\{Z(o_{+},o_{-})+Z(o_{-},o_{+})<w_{o},N=k\right\\}$
$\displaystyle=\left\\{\max\left(0,\max_{i=1}^{k}\left(w_{i}-Z_{i}\right)\right)+Z(o_{-},o_{+})<w_{o},N=k\right\\}$
$\displaystyle=\left\\{\max\left(0,\max_{i=1}^{k}\left(w_{i}-\max\left(0,\max_{i=1}^{N_{i}}\left(w_{i,j}-Z_{i,j}\right)\right)\right)\right)+Z(o_{-},o_{+})<w_{o},N=k\right\\}.$

The event we are interested in is:

$A=\bigcap_{i\leq N}\left\\{\max_{u\sim
v_{i}}(w(v_{i},u)-Z(v_{i},u))<0\right\\}.$

On $B$, we know that $N=k$, but we also know that either
$w(v_{i},o_{-})-Z_{(}v_{i},o)<\max_{u\sim v_{i}}(w(v_{i},u)-Z(v_{i},u))$, or
both are negative, because else, $v_{i}$ would be matched with $o_{-}$ who is
already matched to $o_{+}$. So $A\cap B$ can be rewritten as:

$\bigcap_{i\leq
k}\left\\{\max_{i=1}^{N_{i}}\left(w_{i,j}-Z_{i,j}\right)<0\right\\}\cap B.$

This means that the maximum inside the maximums in the expression in $B$ is
simply 0, so $A\cap B$ can be rewritten as :

$\bigcap_{i\leq
k}\left\\{\max_{i=1}^{N_{i}}\left(w_{i,j}-Z_{i,j}\right)<0\right\\}\cap\left\\{\max\left(0,\max_{i=1}^{k}w_{i}\right)+Z(o_{-},o_{+})<w_{o},N=k\right\\}.$

Finally, we can notice by the recursive equation on $Z$ that the left event
can be rewritten for $i\leq N$ into

$\left\\{Z_{i}=0\right\\}.$

We also notice that the event on the right can be broken down into:

$\left\\{0<w_{o}-Z(o_{-},o_{+}),N=k\right\\}\cap\bigcap_{i=1}^{k}\left\\{w_{i}<w_{o}-Z(o_{-},o_{+})\right\\}.$

In the end, we have obtained that:

$A\cap
B=\left\\{0<w_{o}-Z(o_{-},o_{+}),N=k\right\\}\cap\bigcap_{i=1}^{k}\left\\{w_{i}<w_{o}-Z(o_{-},o_{+}),Z_{i}=0\right\\}.$

Every variable appearing in this expression are now independent, $w_{i},w_{o}$
of law $\omega$, $N$ of law $\hat{\pi}$, $Z_{i},Z(o_{-},o_{+})$ of law
$\zeta_{h}$. So we can compute its probability.

$\displaystyle\mathbb{P}(A\cap B)$
$\displaystyle=\mathbb{P}(N=k)\mathbb{E}_{(W,Z)\sim\omega\otimes\zeta_{h}}[\mathbbm{1}_{W-Z\geq
0}(h_{w}(W-Z))^{k}]\prod_{i=1}^{k}\mathbb{P}\left(Z_{i}=0\right)$
$\displaystyle=\hat{\pi}_{k}h(0)^{k}\mathbb{E}_{(W,Z)\sim\omega\otimes\zeta_{h}}[\mathbbm{1}_{W-Z\geq
0}(h_{w}(W-Z))^{k}].$

By Corollary 26,

$\mathbb{P}(B)=\frac{1-\hat{\phi}^{-1}(h(0))^{k}}{k}\mathbb{P}(N=k)=\frac{\hat{\pi}_{k}\left(1-\hat{\phi}^{-1}(h(0))^{k}\right)}{k}.$

In the end,

$\mathbb{P}(A|B)=\frac{h(0)^{k}}{1-\hat{\phi}^{-1}(h(0))^{k}}k\mathbb{E}_{(W,Z)\sim\omega\otimes\zeta_{h}}[\mathbbm{1}_{W-Z\geq
0}(h_{w}(W-Z))^{k}].$

∎

###  6.2 Exponential edge weights

To the best of our knowledge, the case where $\omega$ is an exponential law is
the only case where $h$ is explicitly computable, and it is no surprise that
this case has already been solved by Gamarnik et al. in [7] in the case of
Erdös-Renyi graphs and $d-$regular graphs. Indeed let us look at Equation (9)
when $W$ is of law $\text{Exp}(1)$.

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

Write

$\mathbb{E}[h(W-t)]=\int_{\mathbb{R}_{+}}h(w-t)e^{-w}\mathrm{d}w=\int_{-t}^{+\infty}h(u)e^{-u-t}\mathrm{d}u=e^{-t}\int_{\mathbb{R}_{+}}h(u)e^{-u}\mathrm{d}u.$

Set

$K=\int_{\mathbb{R}_{+}}h(u)e^{-u}\mathrm{d}u,$

then

$h(t)=\mathbbm{1}_{t\geq 0}\hat{\phi}(1-e^{-t}K),$

and $K$ has to solve

$K=\int_{\mathbb{R}_{+}}\hat{\phi}(1-e^{-u}K)e^{-u}\mathrm{d}u.$

Now, consider the map
$f:x\in[0,1]\mapsto\int_{\mathbb{R}_{+}}\hat{\phi}(1-e^{-u}x)e^{-u}\mathrm{d}u$.
We have
$f(0)=1,f(1)=\int_{\mathbb{R}_{+}}\hat{\phi}(1-e^{-u})e^{-u}\mathrm{d}u<1$ as
long $\hat{\phi}\neq 1$ (in which case the tree is empty), and $f$ is strictly
decreasing. Thus, there exists a unique $K$ satisfying the equation and the
solution $h$ is unique and explicit, as expected.

###  6.3 Extensions

To conclude this work, we now give a few possible generalisations. We only
give the main ideas and stay purposely light on details.

####  6.3.1 Multi-type UBGW tree and Stochastic Block Model

Our results should extend to multi-type UBGW trees which also appear in [6]
but in the unweighted case. These trees appear as local limits for Stochastic
Block Models defined as follows. Let $V_{n}=\\{1,...,n\\}$, and let
$k\in\mathbb{N}^{*}$ be the number of types. Let
$(\alpha_{1},....,\alpha_{k})$ be strictly positive numbers such that
$\sum_{i=1}^{k}\alpha_{k}=1$. For $(i,j)\in\\{1,...,k\\}^{2}$ fix $c_{i,j}>0$.
Partition $V_{n}$ into $V_{n,1}...,V_{n,k}$ such that
$\left||V_{n,i}|-\alpha_{i}n\right|<1$, we may have to add one dummy vertex at
the end to deal with the fact that $\alpha_{i}n$ may not be an integer, but it
doesn’t change the asymptotic behaviour. The (sparse) stochastic block model
is the random graph generated on $V_{n}$ so that independently for $x\in
V_{n,i}$ and $y\in V_{n,j}$, $\mathbb{P}((x,y)\in
E_{n})=p_{i,j}=\frac{c_{i,j}}{n}$.

Then if we follow the same proof, the equation on the $Z(u,v)$ can be
rewritten as a system with $k^{2}$ equations once we condition on the types of
$u$ and $v$. It should be possible to use Schauder’s fixed point theorem on
this system to get existence and then continue with the techniques developed
in this work.

####  6.3.2 Vertex weights

Our results extend to the case where the weights are no longer on the edges
but on the vertices instead. It is equivalent to setting $w(u,v)=w(u)+w(v)$
where the $w(v)$ are i.i.d, the weights on edges are no longer independent as
they are correlated as soon as they share a vertex.

Going back to the heuristic:

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

becomes

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

To recover independence inside the maximum, we introduce the alternative
variables

$\hat{Z}(u,v)=Z(u,v)-w(v),$

then the equation becomes:

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

Now the list of variables inside the maximum is independent, but we can see
that $\hat{Z}(u,v)$ is correlated with $w(v)$ with the correlation structure
appearing in the equation. This leads to the following RDE over a law $\zeta$:
For $W$ of law $\omega$, $N$ of law $\hat{pi}$ and $Z,Z_{i}$ of law $\zeta$,
all independent:

$Z\overset{\mathrm{(law)}}{=}\max(-W,\max_{1\leq i\leq N}(-Z_{i}))$ (37)

Similarly as before we can 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{}\mathbb{P}_{W\sim\omega}(t\geq
W)\hat{\phi}(1-f_{-}(-t))$

with $f_{-}$ the lower continuous version of $f$ and use Schauder’s theorem to
recover a solution to the RDE (37).

We then proceed in a similar fashion as with edge weights by applying
Kolmogorov’s extension Theorem, with the difference that we need to correlate
$\hat{Z}$ on a boundary with the weights of the vertices at the boundary, then
use the recursion to define it on an entire neighbourhood.

We recover $Z$ by setting $Z(u,v)=\hat{Z}(u,v)+w(v)$, the remaining geometric
considerations are then identical as $Z$ still satisfies equation
$\eqref{eq:Z_hrecursion}$.

####  6.3.3 Maximum subgraph satisfying random capacity constraints

As noted by previous authors [3, 9], it is possible to study a slightly more
general type of problem with the approach developed in this work.

Let $\mathcal{C}$ be a law on $\mathbb{N}$ with finite expectation. Consider a
random graph on $G_{n}$ that converges locally to a UBGW tree $\mathbb{T}$. We
decorate $G_{n}$ by adding random independent decorations on vertices $c(v)$
of law $\mathcal{C}$ that we call the capacity of $v$. The local limit is then
the previous tree with additional independent capacities drawn on its
vertices.

The maximum subgraph under capacity constraint is the subgraph $M$ of $G$
maximising

$\sum_{e\in M}w(e)$

subject to

$\deg_{M}(v)\leq c(v),\,\,\,\forall v\in V.$

In the deterministic case, when $c(v)\equiv 1$, we recover a matching, when
$c(v)\equiv k$, a maximal subgraph of degree less than $k$.

The variables $Z$ for this problem can be defined as:

$Z(u,v)=OPT(T^{v})-OPT(T^{v}\text{ where $c(v)$ is decreased by $1$}).$

Let $\overset{[k]}{\max}$ be the operator that returns the $k^{th}$ largest
value of a set. The recursion becomes:

$Z(u,v)=\max\left(0,\underset{\begin{subarray}{c}u^{\prime}\sim v\\\
u^{\prime}\neq
u\end{subarray}}{\overset{[c(v)]}{\max}}\,w(v,u^{\prime})-Z(v,u^{\prime})\right),$

where we set by convention that the $\overset{[0]}{\max}$ of a list is
$+\infty$. Let $c_{l}=\mathbb{P}_{C\sim\mathcal{C}}[C=l]$. This translates
into an equation on its cdf $h$ of the form:

$h(t)=\mathbbm{1}_{t\geq
0}\,\sum_{l=0}^{\infty}c_{l}\sum_{p=0}^{l-1}\frac{\left(\mathbb{E}_{W\sim\omega}\left[h_{-}(W-t)\right]\right)^{p}}{p!}\hat{\phi}^{(p)}(1-\mathbb{E}_{W\sim\omega}\left[h_{-}(W-t)\right])$

Which is still of the form:

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

where $\Phi$ is continuous and decreasing. The decision rule remains:

$(u,v)\in\mathbb{M}_{\mathrm{opt}}\Leftrightarrow Z(u,v)+Z(v,u)<w(u,v).$

## References

  * [1] David Aldous and J. Steele  “The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence”  In _Probability on Discrete Structures_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2004, pp. 1–72  DOI: 10.1007/978-3-662-09444-0_1
  * [2] David J. Aldous  “Asymptotics in the random assignment problem”  In _Probability Theory and Related Fields_ 93, 1992, pp. 507–534
  * [3] David J. Aldous  “The $\zeta(2)$ limit in the random assignment problem”  In _Random Struct. Algorithms_ 18.4, 2001, pp. 381–418  DOI: 10.1002/rsa.1015
  * [4] David J. Aldous and Antar Bandyopadhyay  “A survey of max-type recursive distributional equations”  In _The Annals of Applied Probability_ 15.2 Institute of Mathematical Statistics, 2005  DOI: 10.1214/105051605000000142
  * [5] David J. Aldous and Russell Lyons  “Processes on unimodular random networks”  In _Electron. J. Probab._ 12, 2007, pp. 1454–1508  DOI: 10.1214/EJP.v12-463
  * [6] Charles Bordenave, Marc Lelarge and Justin Salez  “Matchings on infinite graphs”  In _Probab. Theory Relat. Fields_ 157.1-2, 2013, pp. 183–208  DOI: 10.1007/s00440-012-0453-0
  * [7] David Gamarnik, Tomasz Nowicki and Grzegorz Swirszcz  “Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method”  In _Random Struct. Algorithms_ 28.1, 2006, pp. 76–106  DOI: 10.1002/rsa.20072
  * [8] R.. Karp and M. Sipser  “Maximum matching in sparse random graphs”  In _22nd Annual Symposium on Foundations of Computer Science (sfcs 1981)_ , 1981, pp. 364–375  DOI: 10.1109/SFCS.1981.21
  * [9] Justin Salez  “Weighted enumeration of spanning subgraphs in locally tree-like graphs”  In _Random Struct. Algorithms_ 43.3, 2013, pp. 377–397  DOI: 10.1002/rsa.20436

Nathanaël Enriquez<EMAIL_ADDRESS>
Laboratoire de Mathématiques d’Orsay, CNRS, Université Paris-Saclay, 91405,
Orsay, France and DMA, École Normale Supérieure – PSL, 45 rue d’Ulm, F-75230
Cedex 5 Paris, France

Mike Liu<EMAIL_ADDRESS>
ENSAE (Fairplay team), France

Laurent Ménard<EMAIL_ADDRESS>
Modal’X, UMR CNRS 9023, UPL, Univ. Paris-Nanterre, F92000 Nanterre, France and
ENSAE, Criteo AI Lab & Fairplay joint team, France.

Vianney Perchet<EMAIL_ADDRESS>
ENSAE & Criteo AI Lab (Fairplay team), France