Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFairest edge usage and minimum expected overlap for random spanning trees
128
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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 Kruskals or Prims.
rate research
Read More
Chemical tagging of stellar debris from disrupted open clusters and associations underpins the science cases for next-generation multi-object spectroscopic surveys. As part of the Galactic Archaeology project TraCD (Tracking Cluster Debris), a preliminary attempt at reconstructing the birth clouds of now phase-mixed thin disk debris is undertaken using a parametric minimum spanning tree (MST) approach. Empirically-motivated chemical abundance pattern uncertainties (for a 10-dimensional chemistry-space) are applied to NBODY6-realised stellar associations dissolved into a background sea of field stars, all evolving in a Milky Way potential. We demonstrate that significant population reconstruction degeneracies appear when the abundance uncertainties approach 0.1 dex and the parameterised MST approach is employed; more sophisticated methodologies will be required to ameliorate these degeneracies.
A rainbow spanning tree in an edge-colored graph is a spanning tree in which each edge is a different color. Carraher, Hartke, and Horn showed that for $n$ and $C$ large enough, if $G$ is an edge-colored copy of $K_n$ in which each color class has size at most $n/2$, then $G$ has at least $lfloor n/(Clog n)rfloor$ edge-disjoint rainbow spanning trees. Here we strengthen this result by showing that if $G$ is any edge-colored graph with $n$ vertices in which each color appears on at most $deltacdotlambda_1/2$ edges, where $deltageq Clog n$ for $n$ and $C$ sufficiently large and $lambda_1$ is the second-smallest eigenvalue of the normalized Laplacian matrix of $G$, then $G$ contains at least $leftlfloorfrac{deltacdotlambda_1}{Clog n}rightrfloor$ edge-disjoint rainbow spanning trees.
The minimum degree spanning tree (MDST) problem requires the construction of a spanning tree $T$ for graph $G=(V,E)$ with $n$ vertices, such that the maximum degree $d$ of $T$ is the smallest among all spanning trees of $G$. In this paper, we present two new distributed approximation algorithms for the MDST problem. Our first result is a randomized distributed algorithm that constructs a spanning tree of maximum degree $hat d = O(dlog{n})$. It requires $O((D + sqrt{n}) log^2 n)$ rounds (w.h.p.), where $D$ is the graph diameter, which matches (within log factors) the optimal round complexity for the related minimum spanning tree problem. Our second result refines this approximation factor by constructing a tree with maximum degree $hat d = O(d + log{n})$, though at the cost of additional polylogarithmic factors in the round complexity. Although efficient approximation algorithms for the MDST problem have been known in the sequential setting since the 1990s, our results are first efficient distributed solutions for this problem.
Given a collection of graphs $mathbf{G}=(G_1, ldots, G_m)$ with the same vertex set, an $m$-edge graph $Hsubset cup_{iin [m]}G_i$ is a transversal if there is a bijection $phi:E(H)to [m]$ such that $ein E(G_{phi(e)})$ for each $ein E(H)$. We give asymptotically-tight minimum degree conditions for a graph collection on an $n$-vertex set to have a transversal which is a copy of a graph $H$, when $H$ is an $n$-vertex graph which is an $F$-factor or a tree with maximum degree $o(n/log n)$.
Let G be a connected, loopless multigraph. The sandpile group of G is a finite abelian group associated to G whose order is equal to the number of spanning trees in G. Holroyd et al. used a dynamical process on graphs called rotor-routing to define a simply transitive action of the sandpile group of G on its set of spanning trees. Their definition depends on two pieces of auxiliary data: a choice of a ribbon graph structure on G, and a choice of a root vertex. Chan, Church, and Grochow showed that if G is a planar ribbon graph, it has a canonical rotor-routing action associated to it, i.e., the rotor-routing action is actually independent of the choice of root vertex. It is well-known that the spanning trees of a planar graph G are in canonical bijection with those of its planar dual G*, and furthermore that the sandpile groups of G and G* are isomorphic. Thus, one can ask: are the two rotor-routing actions, of the sandpile group of G on its spanning trees, and of the sandpile group of G* on its spanning trees, compatible under plane duality? In this paper, we give an affirmative answer to this question, which had been conjectured by Baker.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
