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 be a finite (), simple (at most one undirected edge between any two distinct vertices and no loops), connected graph, where is the set of vertices and the set of edges. It will be convenient to number the vertices and identify with . Then , where is the set of unordered pairs from .
A path in is simply a connected subgraph (there are finitely many).
A –metric is a function which is not identically zero. Given , the energy (or mass) of is . Given a curve its –length is .
We will identify the space of all real-valued functions on the finite set with the space of column vectors in coordinates, namely . So given a -metric, we will think of it as a vector .
To a path in we will associate its indicator function which equals at vertices in and otherwise. It will be useful to think of as a row vector belonging to the dual of .
With these notations the -length of is simply the inner product
Given a path family , we say that is admissible for if for every . The set of all admissible metrics for is therefore an intersection of half-planes, hence a convex set:
and becomes the set of directions of such half-planes. This is a standard construction in convex analysis.
The –modulus of is
Metrics that attain the minimum will be called extremal metrics.
Notice that is strictly convex on when , since it’s the -th power of the norm on . In particular this implies that extremal metrics are unique.
An easy computation shows that the gradient of is a vector whose -th coordinate is . For simplicity we will normalize it by dividing by and write
where we are thinking of has a real-valued function on .
1.2. Beurling’s Criterion for extremal metrics
Suppose now that is an admissible metric for a path family . Define
Notice that if is extremal for , then necessarily is not empty. Namely, in the language of convex analysis, is the set of “supporting planes” for at .
The classical Beurling’s Criterion in the continuous case gives a sufficient condition for a metric to be extremal. The proof passes to the graph case unchanged.
Theorem 1 (Beurling’s Criterion)
Given a path family in a finite connected graph as above. Let be an admissible metric for and define as in (2). Suppose that there is a subfamily with the property that whenever (i.e. ) satisfies
this implies that
Then is extremal for .
Proof: If , then satisfies (3). So using the explicit form of (1),
Since is non-zero and finite ( is admissible), we can divide and obtain that .
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 in a finite connected graph as above. Let be an admissible metric for and define as in (2). If is extremal for , then whenever (i.e. ) satisfies
this implies that
The proof hinges on Lagrange Multipliers as we will see below during the proof of the following lemma.
Suppose , , are defined as above and assume that is an extremal metric for . Define as in (2).
Then is contained in the positive cone generated by the normal vectors , i.e. there are constants for such that
Assuming Lemma 3, we can prove the converse to Beurling’s Criterion.
Proof of Theorem 2:
Suppose is extremal for . Let as in (2). Assume that satisfies (5). Then
Proof of Lemma 3:
Assume that is not empty. Then
because is finite.
i.e., the intersection of the so-called supporting planes at . Clearly , by construction and restricted to will admit a unique minimizer which we will call .
Proof of Claim 1:
A priori we do not know how behaves on paths . So consider the convex combinations for . Since both and are in and is convex, for all . For ,
as . Therefore, for small is an admissible metric for . On the other hand, if then by strict convexity for all . This contradicts the fact that is extremal for . So and the Claim is proved.
We now know that attains its minimum value over at . By Lagrange Multipliers, must be orthogonal to the affine space , i.e., must be in the span of . We want to show that is actually in the closure of the positive cone spanned by the ‘s.
Let be the orthogonal complement of in . Note that, since is admissible,
So the angle between and is in .
Project onto along the directions , i.e. find points and scalars such that
Taking the inner product with and using (7) one finds that for all .
Notice that is in the convex hull of if and only if is in the positive cone generated by . In particular, if is not in the convex hull, then we can find so that
Since is finite, using (8), we find that there is such that
Let , for . If , then
While if , then
for sufficiently small.
Given a node such that , we have for small. Also if , then . With this let’s calculate the mass of .
Thus for small, the metric is admissible and has mass . This contradicts the extremality of .