New metrics on networks arising from modulus and applications of Fulkerson duality

Abstract

This thesis contains six chapters. In the first chapter, the continuous and the discrete cases of p-modulus is introduced. We present properties of p-modulus and its connection to classical quantities. We also introduce use Arne Beurling's criterion for extremality to build insight and intuition regarding the modulus. After building an intuitive understanding of the p-modulus, we then proceed to switch perspectives to that of convex analysis. Using the theory of convex analysis, the uniqueness and existence of extremal densities is shown. We end this chapter with the introduction of the probabilistic interpretation of Modulus. In the second chapter, we introduce the Fulkerson duality. After defining the Fulkerson dual, we will investigate the blocking duality for different families of objects that the NODE research group has been studying and has been established. An important result that connects the Fulkerson dual and modulus is given at the end of this chapter. This important theorem will be used in proving one of the main results that [delta]_p (introduced in Chapter 4) is a metric on graphs. The third chapter will discuss about metrics and ultrametrics on networks. Among these metrics, effective resistance is given special attention because the proof of [delta]p metric also serves as a new proof that effective resistance is a metric on graphs. We define effective resistance and give two different proves that show it is a metric, namely flows and the Laplacian. Two new families of metrics on graphs that arises through modulus are introduced in the fourth chapter. We also show how the two families are related as the d_p metric is viewed as a snowflaked version of the [delta]_p metric. We end this chapter with some numerical examples that proves this connection and also serves as a set of plentiful examples of modulus calculations. Clutters and blockers is also another topic that is very much related to families of objects. While it has different rules and conditions, the study of clutters and blockers can give more insights to both modulus and clutters. We explore these relations in chapter 5. We provide some examples of clutters and blockers and finally reveal the relationship between the blocker and Fulkerson dual. Finally, in chapter 6, we end the thesis by presenting some of the open questions that we would like to explore and find answers in the future.