Blocking duality for p-modulus on networks and applications

No Thumbnail Available
Issue Date
Embargo End Date
Albin, Nathan
Clemens, Jason R.
Fernando, Nethali
Poggi-Corradini, Pietro

Albin, N., Clemens, J., Fernando, N. et al. Annali di Matematica (2019) 198: 973


This paper explores the implications of blocking dualitypioneered by Fulkerson et the context of p-modulus on networks. Fulkerson blocking duality is an analog on networks to the method of conjugate families of curves in the plane. The technique presented here leads to a general framework for studying families of objects on networks; each such family has a corresponding dual family whose p-modulus is essentially the reciprocal of the original family's. As an application, we give a modulus-based proof for the fact that effective resistance is a metric on graphs. This proof immediately generalizes to yield a family of graph metrics, depending on the parameter p, that continuously interpolates among the shortest-path metric, the effective resistance metric, and the min-cut ultrametric. In a second application, we establish a connection between Fulkerson blocking duality and the probabilistic interpretation of modulus. This connection, in turn, provides a straightforward proof of several monotonicity properties of modulus that generalize known monotonicity properties of effective resistance. Finally, we use this framework to expand on a result of Lovasz in the context of randomly weighted graphs.

Table of Content
Click on the DOI link to access the article (may not be free).