Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Maximum Distance Problem and Minimal Spanning Trees
369
0
0.0
(
0
)
Added by
Bala Krishnamoorthy
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given a compact $E subset mathbb{R}^n$ and $s > 0$, the maximum distance problem seeks a compact and connected subset of $mathbb{R}^n$ of smallest one dimensional Hausdorff measure whose $s$-neighborhood covers $E$. For $Esubset mathbb{R}^2$, we prove that minimizing over minimum spanning trees that connect the centers of balls of radius $s$, which cover $E$, solves the maximum distance problem. The main difficulty in proving this result is overcome by the proof of Lemma 3.5, which states that one is able to cover the $s$-neighborhood of a Lipschitz curve $Gamma$ in $mathbb{R}^2$ with a finite number of balls of radius $s$, and connect their centers with another Lipschitz curve $Gamma_ast$, where $mathcal{H}^1(Gamma_ast)$ is arbitrarily close to $mathcal{H}^1(Gamma)$. We also present an open source package for computational exploration of the maximum distance problem using minimum spanning trees, available at https://github.com/mtdaydream/MDP_MST.
rate research
Read More
We review results on the scaling of the optimal path length in random networks with weighted links or nodes. In strong disorder we find that the length of the optimal path increases dramatically compared to the known small world result for the minimum distance. For ErdH{o}s-Renyi (ER) and scale free networks (SF), with parameter $lambda$ ($lambda >3$), we find that the small-world nature is destroyed. We also find numerically that for weak disorder the length of the optimal path scales logaritmically with the size of the networks studied. We also review the transition between the strong and weak disorder regimes in the scaling properties of the length of the optimal path for ER and SF networks and for a general distribution of weights, and suggest that for any distribution of weigths, the distribution of optimal path lengths has a universal form which is controlled by the scaling parameter $Z=ell_{infty}/A$ where $A$ plays the role of the disorder strength, and $ell_{infty}$ is the length of the optimal path in strong disorder. The relation for $A$ is derived analytically and supported by numerical simulations. We then study the minimum spanning tree (MST) and show that it is composed of percolation clusters, which we regard as super-nodes, connected by a scale-free tree. We furthermore show that the MST can be partitioned into two distinct components. One component the {it superhighways}, for which the nodes with high centrality dominate, corresponds to the largest cluster at the percolation threshold which is a subset of the MST. In the other component, {it roads}, low centrality nodes dominate. We demonstrate the significance identifying the superhighways by showing that one can improve significantly the global transport by improving a very small fraction of the network.
We study an extension of the Falconer distance problem in the multiparameter setting. Given $ellgeq 1$ and $mathbb{R}^{d}=mathbb{R}^{d_1}timescdots timesmathbb{R}^{d_ell}$, $d_igeq 2$. For any compact set $Esubset mathbb{R}^{d}$ with Hausdorff dimension larger than $d-frac{min(d_i)}{2}+frac{1}{4}$ if $min(d_i) $ is even, $d-frac{min(d_i)}{2}+frac{1}{4}+frac{1}{4min(d_i)}$ if $min(d_i) $ is odd, we prove that the multiparameter distance set of $E$ has positive $ell$-dimensional Lebesgue measure. A key ingredient in the proof is a new multiparameter radial projection theorem for fractal measures.
A spanning tree of an edge-colored graph is rainbow provided that each of its edges receives a distinct color. In this paper we consider the natural extremal problem of maximizing and minimizing the number of rainbow spanning trees in a graph $G$. Such a question clearly needs restrictions on the colorings to be meaningful. For edge-colorings using $n-1$ colors and without rainbow cycles, known in the literature as JL-colorings, there turns out to be a particularly nice way of counting the rainbow spanning trees and we solve this problem completely for JL-colored complete graphs $K_n$ and complete bipartite graphs $K_{n,m}$. In both cases, we find tight upper and lower bounds; the lower bound for $K_n$, in particular, proves to have an unexpectedly chaotic and interesting behavior. We further investigate this question for JL-colorings of general graphs and prove several results including characterizing graphs which have JL-colorings achieving the lowest possible number of rainbow spanning trees. We establish other results for general $n-1$ colorings, including providing an analogue of Kirchoffs matrix tree theorem which yields a way of counting rainbow spanning trees in a general graph $G$.
We present here a topological characterization of the minimal spanning tree that can be obtained by considering the price return correlations of stocks traded in a financial market. We compare the minimal spanning tree obtained from a large group of stocks traded at the New York Stock Exchange during a 12-year trading period with the one obtained from surrogated data simulated by using simple market models. We find that the empirical tree has features of a complex network that cannot be reproduced, even as a first approximation, by a random market model and by the one-factor model.
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)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
