Gradient-constrained minimum networks (II). Labelled or locally minimal Steiner points

A gradient-constrained minimum network T is a minimum length network, spanning a given set of nodes N in space with edges whose gradients are all no more than an upper bound m. The nodes in T but not in N are referred to as Steiner points. Such networks occur in the underground mining industry where the typical maximal gradient is about 1:7 (≈ 0.14). Because of the gradient constraint the lengths of edges in T are measured by a special metric, called the gradient metric. An edge in T is labelled as a b-edge, or an m-edge, or an f-edge if the gradient between its endpoints is greater than, or equal to, or less than m respectively. The set of edge labels at a Steiner point is called its labelling. A Steiner point s with a given labelling is called labelled minimal if T cannot be shortened by a label-preserving perturbation of s. Furthermore, s is called locally minimal if T cannot be shortened by any perturbation of s even if its labelling is not preserved. In this paper we study the properties of labelled minimal Steiner points, as well as the necessary and sufficient conditions for Steiner points to be locally minimal. It is shown that, with the exception of one labelling, a labelled minimal Steiner point is necessarily unique with respect to its adjacent nodes, and that the locally minimal Steiner point is always unique, even though the gradient metric is not strictly convex.     

Locally minimal topological groups 2

We continue in this paper the study of locally minimal groups started in Außenhofer et al. (2010) [4]. The minimality criterion for dense subgroups of compact groups is extended to local minimality. Using this criterion we characterize the compact abelian groups containing dense countable locally minimal subgroups, as well as those containing dense locally minimal subgroups of countable free-rank. We also characterize the compact abelian groups whose torsion part is dense and locally minimal. We call a topological group G almost minimal if it has a closed, minimal normal subgroup N such that the quotient group G/N is uniformly free from small subgroups. The class of almost minimal groups includes all locally compact groups, and is contained in the class of locally minimal groups. On the other hand, we provide examples of countable precompact metrizable locally minimal groups which are not almost minimal. Some other significant properties of this new class are obtained.     

带梯子的曲折线上的最短树问题

Abstract. In this paper,Steiner minimal trees for point sets with special structure are studied.These sets consist of zigzag lines and equidistant points lying on them.     

Locally minimal topological groups 1

The aim of this paper is to go deeper into the study of local minimality and its connection to some naturally related properties. A Hausdorff topological group (G,τ) is called locally minimal if there exists a neighborhood U of 0 in τ such that U fails to be a neighborhood of zero in any Hausdorff group topology on G which is strictly coarser than τ. Examples of locally minimal groups are all subgroups of Banach-Lie groups, all locally compact groups and all minimal groups. Motivated by the fact that locally compact NSS groups are Lie groups, we study the connection between local minimality and the NSS property, establishing that under certain conditions, locally minimal NSS groups are metrizable. A symmetric subset of an abelian group containing zero is said to be a GTG set if it generates a group topology in an analogous way as convex and symmetric subsets are unit balls for pseudonorms on a vector space. We consider topological groups which have a neighborhood basis at zero consisting of GTG sets. Examples of these locally GTG groups are: locally pseudoconvex spaces, groups uniformly free from small subgroups (UFSS groups) and locally compact abelian groups. The precise relation between these classes of groups is obtained: a topological abelian group is UFSS if and only if it is locally minimal, locally GTG and NSS. We develop a universal construction of GTG sets in arbitrary non-discrete metric abelian groups, that generates a strictly finer non-discrete UFSS topology and we characterize the metrizable abelian groups admitting a strictly finer non-discrete UFSS group topology. Unlike the minimal topologies, the locally minimal ones are always available on “large” groups. To support this line, we prove that a bounded abelian group G admits a non-discrete locally minimal and locally GTG group topology iff |G|?c.     

Locally uniformly rotund points in convex-transitive Banach spaces

Almost transitive superreflexive Banach spaces have been considered in [C. Finet, Uniform convexity properties of norms on superreflexive Banach spaces, Israel J. Math. 53 (1986) 81–92], where it is shown that they are uniformly convex and uniformly smooth. We characterize such spaces as those convex transitive Banach spaces satisfying conditions much weaker than that of uniform convexity (for example, that of having a weakly locally uniformly rotund point). We note that, in general, the property of convex transitivity for a Banach space is weaker than that of almost transitivity.     

Locally uniformly convex norms in Banach spaces and their duals

It is shown that a Banach space with locally uniformly convex dual admits an equivalent norm that is itself locally uniformly convex.     

The Minimal Submanifolds in a Locally Symmetric and Conformally Flat Riemannian Manifold

In this paper,we extend two important theorem in[1],[2]to the minimal submanifolds in aLocally symmetric and conformally flat Riemannian mainfold N~(+p).When N~(+p)is a space S_(1)~(+p) of constantcurvature,our theorems reduce to the theorems of[1],[2].     

局部Cauchy列和局部完备性的性质

利用完备化的方法,给出了局部凸分离空间（X,T）中序列{xn}是局部Cauchy列当且仅当存在单调增且趋于正无穷大的正实数列{an},使得min{an,am}（xn-xm）→0（m,n→∞）,并得到局部凸分离空间（X,T）是局部完备的当且仅当X中每个丁局部Cauchy列的绝对凸闭包是丁紧的,以及一些局部完备性的相关性质．     

Stable minimal hypersurfaces in locally symmetric spaces

LetM be a complete non‐compact stable minimal hypersurface in a locally symmetric space N of nonnegative Ricci curvature. We prove that if the integral of square norm of the second fundamental form is finite, i.e., ∫_M |A |² dv < ∞, then M must be totally geodesic. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

关于Steiner问题的一个注记——连接五点之最小网络的一种寻优方案

本文讨论如何寻找连接平面上五个给定点的最小网络这一问题．通过发展越民义证明Pollack在1978年所给出的一个关于寻找连接平面上四个给定点的最小网络的重要结论的方法,我们给出了一个采用简单几何作图方法快速求解该问题的方案．     

Quasi-median hulls in Hamming space are Steiner hulls

A Hamming space Λⁿ consists of all sequences of length n over an alphabet Λ and is endowed with the Hamming distance. In particular, any set of aligned DNA sequences of fixed length constitutes a subspace of a Hamming space with respect to mismatch distance. The quasi-median operation returns for any three sequences u,v,w the sequence which in each coordinate attains either the majority coordinate from u,v,w or else (in the case of a tie) the coordinate of the first entry, u; for a subset of Λⁿ the iterative application of this operation stabilizes in its quasi-median hull. We show that for every finite tree interconnecting a given subset X of Λⁿ there exists a shortest realization within Λⁿ for which all interior nodes belong to the quasi-median hull of X. Hence the quasi-median hull serves as a Steiner hull for the Steiner problem in Hamming space.     

Steiner Minimal Trees in Rectilinear and Octilinear Planes

This paper considers the Steiner Minimal Tree （SMT） problem in the rectilinear and octilinear planes. The study is motivated by the physical design of VLSI： The rectilinear case corresponds to the currently used M-architecture, which uses either horizontal or vertical routing, while the octilinear case corresponds to a new routing technique, X-architecture, that is based on the pervasive use of diagonal directions. The experimental studies show that the X-architecture demonstrates a length reduction of more than 10-20%. In this paper, we make a theoretical study on the lengths of SMTs in these two planes. Our mathematical analysis confirms that the length reduction is significant as the previous experimental studies claimed, but the reduction for three points is not as significant as for two points. We also obtain the lower and upper bounds on the expected lengths of SMTs in these two planes for arbitrary number of points.     

Minimum Networks for Four Points in Space

The minimum network problem (Steiner tree problem) in space is much harder than the one in the Euclidean plane. The Steiner tree problem for four points in the plane has been well studied. In contrast, very few results are known on this simple Steiner problem in 3D-space. In the first part of this paper we analyze the difficulties of the Steiner problem in space. From this analysis we introduce a new concept — Simpson intersections, and derive a system of iteration formulae for computing Simpson intersections. Using Simpson intersections the Steiner points can be determined by solving quadratic equations. As well this new computational method makes it easy to check the impossibility of computing Steiner trees on 4-point sets by radicals. At the end of the first part we consider some special cases (planar and symmetric 3D-cases) that can be solved by radicals. The Steiner ratio problem is to find the minimum ratio of the length of a Steiner minimal tree to the length of a minimal spanning tree. This ratio problem in the Euclidean plane was solved by D. Z. Du and F. K. Hwang in 1990, but the problem in 3D-space is still open. In 1995 W.D. Smith and J.M. Smith conjectured that the Steiner ratio for 4-point sets in 3D-space is achieved by regular tetrahedra. In the second part of this paper, using the variational method, we give a proof of this conjecture.     

关于Steiner问题的一个注记—连接五点之最小网络的一种寻优方案(英文)

本文讨论如何寻找连接平面上五个给定点的最小网络这一问题.通过发展越民义证明Pollack在1978年所给出的一个关于寻找连接平面上四个给定点的最小网络的重要结论的方法,我们给出了一个采用简单几何作图方法快速求解该问题的方案.     

Listing minimal edge-covers of intersecting families with applications to connectivity problems

Let G=(V,E) be a directed/undirected graph, let s,t∈V, and let F be an intersecting family on V (that is, X∩Y,X∪Y∈F for any intersecting X,Y∈F) so that s∈X and t∉X for every X∈F. An edge set I⊆E is an edge-cover of F if for every X∈F there is an edge in I from X to V−X. We show that minimal edge-covers of F can be listed with polynomial delay, provided that, for any I⊆E the minimal member of the residual family F_I of the sets in F not covered by I can be computed in polynomial time. As an application, we show that minimal undirected Steiner networks, and minimal k-connected and k-outconnected spanning subgraphs of a given directed/undirected graph, can be listed in incremental polynomial time.     

Locally nilpotent linear groups with restrictions on their subgroups of infinite central dimension

Let F be a field and V a vector space over F. If G is a subgroup of GL(V, F), then we define the central dimension of G (denoted by centdim _F G) as the F-dimension of the factor-space V/C _V (G). In this paper, we continue the study of locally nilpotent linear groups satisfying the weak minimal or the weak maximal condition on their subgroups of infinite central dimension started in Kurdachenko et al. (Publ Mat 52:151–169, 2008). Supported by Proyecto MTM2007-60994 of Dirección General de Investigación MEC (Spain).     

An integer programming formulation of the Steiner problem in graphs

A succinct integer linear programming model for the Steiner problem in networks is presented.