اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOptimal realisations of two-dimensional, totally-decomposable metrics
103
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A realisation of a metric $d$ on a finite set $X$ is a weighted graph $(G,w)$ whose vertex set contains $X$ such that the shortest-path distance between elements of $X$ considered as vertices in $G$ is equal to $d$. Such a realisation $(G,w)$ is called optimal if the sum of its edge weights is minimal over all such realisations. Optimal realisations always exist, although it is NP-hard to compute them in general, and they have applications in areas such as phylogenetics, electrical networks and internet tomography. In [Adv. in Math. 53, 1984, 321-402] A.~Dress showed that the optimal realisations of a metric $d$ are closely related to a certain polytopal complex that can be canonically associated to $d$ called its tight-span. Moreover, he conjectured that the (weighted) graph consisting of the zero- and one-dimensional faces of the tight-span of $d$ must always contain an optimal realisation as a homeomorphic subgraph. In this paper, we prove that this conjecture does indeed hold for a certain class of metrics, namely the class of totally=decomposable metrics whose tight-span has dimension two. As a corollary, it follows that the minimum Manhattan network problem is a special case of finding optimal realisations of two-dimensional totally-decomposable metrics.
قيم البحث
اقرأ أيضاً
We study minimax estimation of two-dimensional totally positive distributions. Such distributions pertain to pairs of strongly positively dependent random variables and appear frequently in statistics and probability. In particular, for distributions
with $beta$-Holder smooth densities where $beta in (0, 2)$, we observe polynomially faster minimax rates of estimation when, additionally, the total positivity condition is imposed. Moreover, we demonstrate fast algorithms to compute the proposed estimators and corroborate the theoretical rates of estimation by simulation studies.
A linearly constrained framework in $mathbb{R}^d$ is a point configuration together with a system of constraints which fixes the distances between some pairs of points and additionally restricts some of the points to lie in given affine subspaces. It
is globally rigid if the configuration is uniquely defined by the constraint system, and is rigid if it is uniquely defined within some small open neighbourhood. Streinu and Theran characterised generic rigidity of linearly constrained frameworks in $mathbb{R}^2$ in 2010. We obtain an analagous characterisation for generic global rigidity in $mathbb{R}^2$. More precisely we show that a generic linearly constrained framework in $mathbb{R}^2$ is globally rigid if and only if it is redundantly rigid and `balanced. For generic frameworks which are not balanced, we determine the precise number of solutions to the constraint system whenever the underlying rigidity matroid of the given framework is connected. We also obtain a stress matrix sufficient condition and a Hendrickson type necessary condition for a generic linearly constrained framework to be globally rigid in $mathbb{R}^d$.
It is presented the simplest known disproof of the Borsuk conjecture stating that if a bounded subset of n-dimensional Euclidean space contains more than n points, then the subset can be partitioned into n+1 nonempty parts of smaller diameter. The
argument is due to N. Alon and is a remarkable application of combinatorics and algebra to geometry. This note is purely expository and is accessible for students.
Given a rigid realisation of a graph $G$ in ${mathbb R}^2$, it is an open problem to determine the maximum number of pairwise non-congruent realisations which have the same edge lengths as the given realisation. This problem can be restated as findin
g the number of solutions of a related system of quadratic equations and in this context it is natural to consider the number of solutions in ${mathbb C}^2$ rather that ${mathbb R}^2$. We show that the number of complex solutions, $c(G)$, is the same for all generic realisations of a rigid graph $G$, characterise the graphs $G$ for which $c(G)=1$, and show that the problem of determining $c(G)$ can be reduced to the case when $G$ is $3$-connected and has no non-trivial $3$-edge-cuts. We consider the effect of the Henneberg moves and the vertex-splitting operation on $c(G)$. We use our results to determine $c(G)$ exactly for two important families of graphs, and show that the graphs in both families have $c(G)$ pairwise equivalent generic real realisations. We also show that every planar isostatic graph on $n$ vertices has at least $2^{n-3}$ pairwise equivalent real realisations.
A bar-joint framework $(G,p)$ in $mathbb{R}^d$ is rigid if the only edge-length preserving continuous motions of the vertices arise from isometries of $mathbb{R}^d$. It is known that, when $(G,p)$ is generic, its rigidity depends only on the underlyi
ng graph $G$, and is determined by the rank of the edge set of $G$ in the generic $d$-dimensional rigidity matroid $mathcal{R}_d$. Complete combinatorial descriptions of the rank function of this matroid are known when $d=1,2$, and imply that all circuits in $mathcal{R}_d$ are generically rigid in $mathbb{R}^d$ when $d=1,2$. Determining the rank function of $mathcal{R}_d$ is a long standing open problem when $dgeq 3$, and the existence of non-rigid circuits in $mathcal{R}_d$ for $dgeq 3$ is a major contributing factor to why this problem is so difficult. We begin a study of non-rigid circuits by characterising the non-rigid circuits in $mathcal{R}_d$ which have at most $d+6$ vertices.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
