Fairest edge usage and minimum expected overlap for random spanning trees

dc.contributor.authorAlbin, Nathan
dc.contributor.authorClemens, Jason R.
dc.contributor.authorHoare, Derek
dc.contributor.authorPoggi-Corradini, Pietro
dc.contributor.authorSit, Brandon
dc.contributor.authorTymochko, Sarah
dc.descriptionClick on the DOI link to access the article (may not be free).en_US
dc.description.abstractRandom 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.en_US
dc.description.sponsorshipNational Science Foundation Funding text: This material is based upon work supported by the National Science Foundation, United States under Grant Nos. 1515810 and 1659123 . The authors are grateful to Professors Marianne Korten and David Yetter at Kansas State University for organizing an exceptional summer undergraduate research program that led to several of the results presented in this paper.en_US
dc.identifier.citationAlbin, 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.112282en_US
dc.relation.ispartofseriesDiscrete Mathematics;Vol. 344, Issue 5
dc.rights.holder© 2021 Elsevier B.V. All rights reserved.en_US
dc.subjectRandom spanning treeen_US
dc.subjectEdge probability p-modulusen_US
dc.subjectHierarchical graph decompositionen_US
dc.titleFairest edge usage and minimum expected overlap for random spanning treesen_US
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
1.59 KB
Item-specific license agreed upon to submission