Characterizations and Probabilistic Representations of Effective Resistance Metrics

This thesis studies effective resistances of finite and infinite weighted graphs. Classical results state that it is a metric on the set of vertices of the graph and that it can be expressed completely in terms of the graph’s random walk. The first goal of this thesis is to provide a concise and accessible starting point for new scholars interested in the topic. In that spirit, we reproduce existing results and review different approaches to effective resistances using tools from several fields such as linear algebra, probability theory, geometry and functional analysis. The second goal is to characterize which metric spaces are given by the effective resistance of a graph. For the finite case, we begin by reconstructing the associated graph from the effective resistance. This leads to a complete algebraic characterization in terms of triangle inequality defects. A more geometric condition is given by showing that a metric space can only be an effective resistance if its minimal graph realization contains no incomplete cycles. We also show that our algebraic characterization can be applied to the more general theory of resistance forms as defined by Kigami. The third goal of this thesis is to investigate probabilistic representations of effective resistances. Building on the work of Tetali and Barlow, we characterize under which conditions known representations for finite graphs can be extended to infinite graphs.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Leipzig

Year

2020

Author dc:creator

• Weihrauch, Tobias

• effective resistance
• resistance metrics
• weighted graph
• graph laplacian
• random walk