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})<M_{p} (\rho)} 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)<M_{p}(\rho)}. This contradicts the extremality of {\rho}.

\Box

Advertisements
This entry was posted in General. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s