## Modulus of Path Families on Graphs

These notes approximately follow a presentation Mario Bonk gave at the Workshop on Discrete and Complex Analysis, Montana State University, July 19-23, 2010. We follow the paper of Haïssinsky “Empilements de cercles et modules combinatoires”. Ann. Inst. Fourier (Grenoble) 59 (2009), no. 6, 2175–2222. (French).

1. Graph modulus

1.1. Path families on graphs

Let ${G=(V,E)}$ be a finite (${|V|=N}$), simple (at most one undirected edge between any two distinct vertices and no loops), connected graph, where ${V}$ is the set of vertices and ${E}$ the set of edges. It will be convenient to number the vertices and identify ${V}$ with ${\{1,2,\dots,N\}}$. Then ${E\subset {V\choose 2}}$, where ${{V\choose2}}$ is the set of unordered pairs from ${V}$.

A path ${\gamma}$ in ${G}$ is simply a connected subgraph (there are finitely many).

A ${\rho}$metric is a function ${\rho: V\rightarrow [0,+\infty )}$ which is not identically zero. Given ${p>1}$, the energy (or mass) of ${\rho}$ is ${M_{p} (\rho)= \sum_{i=1}^{N}\rho (i)^{p}}$. Given a curve ${\gamma}$ its ${\rho}$length is ${\sum_{v\in\gamma}\rho (v)}$.

We will identify the space of all real-valued functions on the finite set ${V}$ with the space of column vectors in ${N}$ coordinates, namely ${{\mathbb R}^{N}}$. So given a ${\rho}$-metric, we will think of it as a vector ${(\rho (1),\rho (2),\dots,\rho (N))^{T}}$.

To a path ${\gamma}$ in ${G}$ we will associate its indicator function ${\mathbb{I}_\gamma}$ which equals ${1}$ at vertices in ${\gamma}$ and ${0}$ otherwise. It will be useful to think of ${\mathbb{I}_{\gamma}}$ as a row vector belonging to the dual of ${{\mathbb R}^{N}}$.

With these notations the ${\rho}$-length of ${\gamma}$ is simply the inner product

$\displaystyle \langle \rho, \mathbb{I}_{\gamma} \rangle.$

Given a path family ${\Gamma}$, we say that ${\rho}$ is admissible for ${\Gamma}$ if ${\langle \rho, \mathbb{I}_{\gamma} \rangle \geq 1}$ for every ${\gamma\in \Gamma}$. The set $\mathcal{A}$ of all admissible metrics for ${\Gamma}$ is therefore an intersection of half-planes, hence a convex set:

$\displaystyle \mathcal{A} = \bigcap_{\gamma \in\Gamma}\{x\in {\mathbb R}^N: \langle x,\mathbb{I}_{\gamma}\rangle\geq 1\}$

and ${\Gamma}$ becomes the set of directions of such half-planes. This is a standard construction in convex analysis.

The ${p}$modulus of ${\Gamma}$ is

$\displaystyle \mathrm{Mod}_{p} (\Gamma)= \min_{\rho\in \mathcal{A}}M_{p} (\rho)$

Metrics ${\rho}$ that attain the minimum will be called extremal metrics.

Notice that ${M_{p} (\cdot)}$ is strictly convex on ${{\mathbb R}^{N}}$ when ${p>1}$, since it’s the ${p}$-th power of the ${\ell_{p}}$ norm on ${{\mathbb R}^{N}}$. In particular this implies that extremal metrics are unique.

An easy computation shows that the gradient of ${M_{p} (\rho )=\|\rho\|_{p}^{p}}$ is a vector whose ${j}$-th coordinate is ${p\rho_{j}|\rho_{j}|^{p-2}}$. For simplicity we will normalize it by dividing by ${p}$ and write

$\displaystyle \nabla M_{p} (\rho )=\rho |\rho |^{p-2} \ \ \ \ \ (1)$

where we are thinking of ${\rho}$ has a real-valued function on ${V}$.

1.2. Beurling’s Criterion for extremal metrics

Suppose now that ${\rho}$ is an admissible metric for a path family ${\Gamma}$. Define

$\displaystyle \Gamma_{0} (\rho)=\{\gamma \in \Gamma : \langle \rho, \mathbb{I}_\gamma \rangle=1 \}. \ \ \ \ \ (2)$

Notice that if ${\rho}$ is extremal for ${\Gamma}$, then necessarily ${\Gamma_{0} (\rho)}$ is not empty. Namely, in the language of convex analysis, ${\Gamma_{0} (\rho)}$ is the set of “supporting planes” for ${\mathcal{A}}$ at ${\rho}$.

The classical Beurling’s Criterion in the continuous case gives a sufficient condition for a metric ${\rho}$ to be extremal. The proof passes to the graph case unchanged.

Theorem 1 (Beurling’s Criterion)
Given a path family ${\Gamma}$ in a finite connected graph ${G}$ as above. Let ${\rho}$ be an admissible metric for ${\Gamma}$ and define ${\Gamma_{0} (\rho)}$ as in (2). Suppose that there is a subfamily ${\tilde{\Gamma}\subset\Gamma_{0} (\rho)}$ with the property that whenever ${h:V\rightarrow {\mathbb R}}$ (i.e. ${h\in {\mathbb R}^{N}}$) satisfies

$\displaystyle \langle h, \mathbb{I}_{\gamma}\rangle\geq 0 \qquad \forall \gamma \in\tilde{\Gamma}, \ \ \ \ \ (3)$

this implies that

$\displaystyle \langle h, \nabla M_{p} (\rho)\rangle\geq 0. \ \ \ \ \ (4)$

Then ${\rho}$ is extremal for ${\Gamma}$.

Proof: If ${\sigma\in \mathcal{A}}$, then ${h=\sigma -\rho}$ satisfies (3). So using the explicit form of (1),

$\begin{array}{lll} \|\rho \|_{p}^{p} & = \langle\rho , \nabla M_{p} (\rho)\rangle & \qquad \mathrm{by}\ (1)\\ &&\\ & \leq \langle \sigma ,\nabla M_{p} (\rho)\rangle & \qquad \mathrm{by}\ (4)\\ &&\\ & \leq \|\sigma \|_{p}\|\nabla M_{p}(\rho)\|_{p/ (p-1)} & \qquad \mathrm{by}\ \mathrm{Holder}\\ &&\\ & = \|\sigma \|_{p}\|\rho\|_{p}^{p-1} & \qquad \mathrm{by}\ (1) \end{array}$

Since ${\|\rho \|_{p}}$ is non-zero and finite (${\rho}$ is admissible), we can divide and obtain that ${M_{p} (\rho )=\|\rho\|_{p}^{p}\leq \|\sigma \|_{p}^{p}=M_{p} (\sigma)}$.

$\Box$

1.3. A converse to Beurling’s Criterion

In the graph case one can prove a converse to Beurling’s Criterion.

Theorem 2 (A Converse to Beurling’s Criterion)
Given a path family ${\Gamma}$ in a finite connected graph ${G}$ as above. Let ${\rho}$ be an admissible metric for ${\Gamma}$ and define ${\Gamma_{0} (\rho)}$ as in (2). If ${\rho}$ is extremal for ${\Gamma}$, then whenever ${h:V\rightarrow {\mathbb R}}$ (i.e. ${h\in {\mathbb R}^{N}}$) satisfies

$\displaystyle \langle h, \mathbb{I}_{\gamma}\rangle\geq 0 \qquad \forall \gamma \in\Gamma_{0} (\rho), \ \ \ \ \ (5)$

this implies that

$\displaystyle \langle h, \nabla M_{p} (\rho)\rangle\geq 0. \ \ \ \ \ (6)$

The proof hinges on Lagrange Multipliers as we will see below during the proof of the following lemma.

Lemma 3
Suppose ${G}$, ${p}$, ${\Gamma}$ are defined as above and assume that ${\rho}$ is an extremal metric for ${\Gamma}$. Define ${\Gamma_{0} (\rho)}$ as in (2).

Then ${\nabla M_{p} (\rho)}$ is contained in the positive cone generated by the normal vectors ${\{\mathbb{I}_{\gamma} \}_{\gamma\in \Gamma_{0}}}$, i.e. there are constants ${\lambda_{\gamma}\geq 0}$ for ${\gamma\in\Gamma_{0}}$ such that

$\displaystyle \nabla M_{p} (\rho)=\sum_{\gamma \in \Gamma_{0}}\lambda_{\gamma}\mathbb{I}_{\gamma}.$

Assuming Lemma 3, we can prove the converse to Beurling’s Criterion.

Proof of Theorem 2:
Suppose ${\rho}$ is extremal for ${\Gamma}$. Let ${\Gamma_{0} (\rho)}$ as in (2). Assume that ${h:V\rightarrow {\mathbb R}}$ satisfies (5). Then

$\begin{array}{lll} \langle h, \nabla M_{p} (\rho)\rangle & = \sum_{v\in V}h (v)\sum_{\gamma \in \Gamma_{0} (\rho)}\lambda_{\gamma}\mathbb{I}_{\gamma} (v) & \qquad\text{by Lemma 3}\\ &&\\ &= \sum_{\gamma \in \Gamma_{0} (\rho)}\lambda_{\gamma}\sum_{v\in V} h (v)\mathbb{I}_{\gamma} (v)\geq 0 & \qquad\text{by (5)} \end{array}$

$\Box$

Proof of Lemma 3:
Assume that ${\Gamma \setminus \Gamma_{0}}$ is not empty. Then

$\displaystyle \delta= \min_{\gamma \in \Gamma \setminus \Gamma_{0}} \langle \rho , \mathbb{I}_{\gamma} \rangle - 1 > 0$

because ${\Gamma}$ is finite.

Also let

$\displaystyle \Delta=\bigcap_{\gamma\in \Gamma_{0}}\{x\in \mathbb{R}^{N}: \langle x, \mathbb{I}_{\gamma} \rangle= 1\},$

i.e., the intersection of the so-called supporting planes at ${\rho}$. Clearly ${\rho \in \Delta}$, by construction and ${M_{p}}$ restricted to ${\Delta}$ will admit a unique minimizer which we will call ${\rho_{1}}$.

Claim 1
${\rho_{1}=\rho}$.

Proof of Claim 1:
A priori we do not know how ${\rho_{1}}$ behaves on paths ${\gamma \in \Gamma\setminus \Gamma_{0}}$. So consider the convex combinations ${\rho_{t}=t\rho_{1}+ (1-t)\rho}$ for ${0\leq t\leq 1}$. Since both ${\rho}$ and ${\rho_{1}}$ are in ${\Delta}$ and ${\Delta}$ is convex, ${\rho_{t}\in\Delta}$ for all ${t}$. For ${\gamma \in \Gamma \setminus \Gamma_{0}}$,

$\displaystyle \langle \rho_{t} , \mathbb{I}_{\gamma} \rangle \geq t \langle \rho_{1} , \mathbb{I}_{\gamma} \rangle+ (1-t) (1+\delta) =1+\delta +O (t)$

as ${t\rightarrow 0}$. Therefore, for ${t}$ small ${\rho_{t}}$ is an admissible metric for ${\Gamma}$. On the other hand, if ${\rho \neq\rho_{1}}$ then by strict convexity ${M_{p} (\rho_{t}) for all ${0< t\leq 1}$. This contradicts the fact that ${\rho}$ is extremal for ${\Gamma}$. So ${\rho=\rho_{1}}$ and the Claim is proved.

$\Box$

We now know that ${M_{p}}$ attains its minimum value over ${\Delta}$ at ${\rho}$. By Lagrange Multipliers, ${\nabla M_{p} (\rho)}$ must be orthogonal to the affine space ${\Delta}$, i.e., ${\nabla M_{p} (\rho)}$ must be in the span ${S}$ of ${\{\mathbb{I}_{\gamma} \}_{\gamma \in \Gamma_{0}}}$. We want to show that ${\nabla M_{p} (\rho)}$ is actually in the closure of the positive cone spanned by the ${\mathbb{I}_{\gamma}}$‘s.

Let ${F=\{x\in S: \langle x, \nabla M_{p} (\rho )\rangle= 0 \}}$ be the orthogonal complement of ${\nabla M_{p} (\rho)}$ in ${S}$. Note that, since ${\rho}$ is admissible,

$\displaystyle \langle \nabla M_{p} (\rho ), \mathbb{I}_{\gamma} \rangle= \sum_{v\in\gamma}\rho (v)^{p-1}>0. \ \ \ \ \ (7)$

So the angle between ${\mathbb{I}_{\gamma}}$ and ${\nabla M_{p} (\rho)}$ is in ${(-\pi /2,\pi /2)}$.

Project ${\nabla M_{p} (\rho)}$ onto ${F}$ along the directions ${\mathbb{I}_{\gamma}}$, i.e. find points ${p_{\gamma}\in F}$ and scalars ${a_{\gamma}\in {\mathbb R}}$ such that

$\displaystyle p_{\gamma}+a_{\gamma}\mathbb{I}_{\gamma}=\nabla M_{p} (\rho) \ \ \ \ \ (8)$

Taking the inner product with ${\nabla M_{p} (\rho)}$ and using (7) one finds that ${a_{\gamma}>0}$ for all ${\gamma \in \Gamma_{0}}$.

Notice that ${0}$ is in the convex hull of ${\{p_{\gamma}\}_{\gamma \in \Gamma_{0}}}$ if and only if ${\nabla M_{p} (\rho)}$ is in the positive cone generated by ${\{\mathbb{I}_{\gamma} \}_{\gamma \in \Gamma_{0}}}$. In particular, if ${0}$ is not in the convex hull, then we can find ${\sigma \in F}$ so that

$\displaystyle \langle -\sigma ,p_{\gamma}\rangle > 0\qquad \forall \gamma \in \Gamma_{0},$

Since ${\Gamma_{0}}$ is finite, using (8), we find that there is ${\eta >0}$ such that

$\displaystyle \langle \sigma ,\mathbb{I}_{\gamma}\rangle > \eta >0 \qquad \forall \gamma \in \Gamma_{0}.$

Let ${\sigma_{t}= \rho +t\sigma}$, for ${t\geq 0}$. If ${\gamma \in \Gamma_{0}}$, then

$\displaystyle \langle \sigma_{t} ,\mathbb{I}_{\gamma}\rangle\geq \langle \rho ,\mathbb{I}_{\gamma}\rangle+t\langle \sigma ,\mathbb{I}_{\gamma}\rangle \geq 1+t\eta.$

While if ${\gamma \in \Gamma \setminus \Gamma_{0}}$, then

$\displaystyle \langle \sigma_{t} ,\mathbb{I}_{\gamma}\rangle \geq (1+\delta)+t\langle \sigma ,\mathbb{I}_{\gamma}\rangle \geq 1+t\eta$

for ${t}$ sufficiently small.

Given a node ${v\in V}$ such that ${\rho (v)>0}$, we have ${\sigma_{t} (v)>0}$ for ${t}$ small. Also if ${\rho (v)=0}$, then ${|\sigma_{t} (v)|^{p}=o(t)}$. With this let’s calculate the mass of ${\sigma_{t}}$.

$\displaystyle \begin{array}{rcl} M_{p} (\sigma_{t}) & = & \sum_{v\in V}|\rho (v)+t\sigma (v)|^{p}\\ &&\\ & = & \sum_{v: \rho (v)>0}\rho (v)^{p}\left (1+t\frac{\sigma (v)}{\rho (v)}\right)^{p}+o (t)\\ &&\\ & = & \sum_{v: \rho (v)>0}\rho (v)^{p}\left ( 1+tp\frac{\sigma (v)}{\rho (v)}\right)+o (t)\\ &&\\ & = & M_{p} (\rho)+t\sum_{v: \rho (v)>0}p\rho (v)^{p-1}\sigma (v)+o (t)\\ &&\\ & = & M_{p} (\rho)+tp\langle \sigma ,\nabla M_{p} (\rho)\rangle +o (t)=M_{p} (\rho)+o (t) \end{array}$

Thus for ${t}$ small, the metric ${\sigma_{t}/ (1+\eta t)}$ is admissible and has mass ${M_{p} (\rho)-\eta M_{p} (\rho)t+o (t). This contradicts the extremality of ${\rho}$.

$\Box$