Fairest edge usage and minimum expected overlap for random spanning trees
Albin, Nathan Clemens, Jason R. Hoare, Derek Poggi-Corradini, Pietro Sit, Brandon Tymochko, Sarah
Albin, Nathan
Clemens, Jason R.
Hoare, Derek
Poggi-Corradini, Pietro
Sit, Brandon
Tymochko, Sarah
Citations
Altmetric:
Other Names
Location
Time Period
Advisors
Original Date
Digitization Date
Issue Date
2021-05
Type
Article
Genre
Keywords
Random spanning tree,Edge probability p-modulus,Hierarchical graph decomposition
Subjects (LCSH)
Citation
Albin, N., Clemens, J., Hoare, D., Poggi-Corradini, P., Sit, B., & Tymochko, S. (2021). Fairest edge usage and minimum expected overlap for random spanning trees. Discrete Mathematics, 344(5) doi:10.1016/j.disc.2020.112282
Abstract
Random spanning trees of a graph $G$ are governed by a corresponding probability mass distribution (or "law"), $\mu$ defined on the set of all spanning trees of $G$ This paper addresses the problem of choosing $\mu$ in order to utilize the edges as "fairly" as possible. This turns out to be equivalent to minimizing, with respect to $\mu$ the expected overlap of two independent random spanning trees sampled with law $\mu$ In the process, we introduce the notion of homogeneous graphs. These are graphs for which it is possible to choose a random spanning tree so that all edges have equal usage probability. The main result is a deflation process that identifies a hierarchical structure of arbitrary graphs in terms of homogeneous subgraphs, which we call homogeneous cores. A key tool in the analysis is the spanning tree modulus, for which there exists an algorithm based on minimum spanning tree algorithms, such as Kruskal's or Prim's.
Table of Contents
Description
Click on the DOI link to access the article (may not be free).
Publisher
Elsevier
Journal
Book Title
Series
Discrete Mathematics;Vol. 344, Issue 5
Digital Collection
Finding Aid URL
Use and Reproduction
Archival Collection
PubMed ID
DOI
ISSN
0012-365X