Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTrees, Tight-Spans and Point Configuration
447
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Tight-spans of metrics were first introduced by Isbell in 1964 and rediscovered and studied by others, most notably by Dress, who gave them this name. Subsequently, it was found that tight-spans could be defined for more general maps, such as directed metrics and distances, and more recently for diversities. In this paper, we show that all of these tight-spans as well as some related constructions can be defined in terms of point configurations. This provides a useful way in which to study these objects in a unified and systematic way. We also show that by using point configurations we can recover results concerning one-dimensional tight-spans for all of the maps we consider, as well as extend these and other results to more general maps such as symmetric and unsymmetric maps.
rate research
Read More
An important problem that commonly arises in areas such as internet traffic-flow analysis, phylogenetics and electrical circuit design, is to find a representation of any given metric $D$ on a finite set by an edge-weighted graph, such that the total edge length of the graph is minimum over all such graphs. Such a graph is called an optimal realization and finding such realizations is known to be NP-hard. Recently Varone presented a heuristic greedy algorithm for computing optimal realizations. Here we present an alternative heuristic that exploits the relationship between realizations of the metric $D$ and its so-called tight span $T_D$. The tight span $T_D$ is a canonical polytopal complex that can be associated to $D$, and our approach explores parts of $T_D$ for realizations in a way that is similar to the classical simplex algorithm. We also provide computational results illustrating the performance of our approach for different types of metrics, including $l_1$-distances and two-decomposable metrics for which it is provably possible to find optimal realizations in their tight spans.
A k-dissimilarity map on a finite set X is a function D : X choose k rightarrow R assigning a real value to each subset of X with cardinality k, k geq 2. Such functions, also sometimes known as k-way dissimilarities, k-way distances, or k-semimetrics, are of interest in many areas of mathematics, computer science and classification theory, especially 2-dissimilarity maps (or distances) which are a generalisation of metrics. In this paper, we show how regular subdivisions of the kth hypersimplex can be used to obtain a canonical decomposition of a k-dissimilarity map into the sum of simpler k-dissimilarity maps arising from bipartitions or splits of X. In the special case k = 2, this is nothing other than the well-known split decomposition of a distance due to Bandelt and Dress [Adv. Math. 92 (1992), 47-105], a decomposition that is commonly to construct phylogenetic trees and networks. Furthermore, we characterise those sets of splits that may occur in the resulting decompositions of k-dissimilarity maps. As a corollary, we also give a new proof of a theorem of Pachter and Speyer [Appl. Math. Lett. 17 (2004), 615-621] for recovering k-dissimilarity maps from trees.
A one-to-one correspondence between the infinitesimal motions of bar-joint frameworks in $mathbb{R}^d$ and those in $mathbb{S}^d$ is a classical observation by Pogorelov, and further connections among different rigidity models in various different spaces have been extensively studied. In this paper, we shall extend this line of research to include the infinitesimal rigidity of frameworks consisting of points and hyperplanes. This enables us to understand correspondences between point-hyperplane rigidity, classical bar-joint rigidity, and scene analysis. Among other results, we derive a combinatorial characterization of graphs that can be realized as infinitesimally rigid frameworks in the plane with a given set of points collinear. This extends a result by Jackson and Jord{a}n, which deals with the case when three points are collinear.
We study a family of variants of ErdH os unit distance problem, concerning distances and dot products between pairs of points chosen from a large finite point set. Specifically, given a large finite set of $n$ points $E$, we look for bounds on how many subsets of $k$ points satisfy a set of relationships between point pairs based on distances or dot products. We survey some of the recent work in the area and present several new, more general families of bounds.
In arXiv:math/0603621 we introduced the notion of a partial translation $C^*$-algebra for a discrete metric space. Here we demonstrate that several important classical $C^*$-algebras and extensions arise naturally by considering partial translation algebras associated with subspaces of trees.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
