On steiner systems

Steiner’s “combinatorial problems” have so far been solved only fork=3 [5, 3] and fork=4 [1,2]. In this paper a complete solution of the problem is given for “closed” Steiner systems, i.e. systems havingn=2 ^k−1−1 elements. Use is made of methods developed by Zaremba [7] for abelian groups. This research was supported by the United States Air Force under Grant No. AF-EOAR-6360 and monitored by the European Office of Aerospace Research.     

On steiner ratio conjectures

LetM be a metric space andP a finite set of points inM. The Steiner ratio inM is defined to be(M)=inf{L _s(P)/L _m(P) |P M}, whereL _s(P) andL _m(P) are the lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. In this paper, we study various conjectures on(M). In particular, we show that forn-dimensional Euclidean space _n ,( _n )>0.615.Supported in part by the National Science Foundation of China.     

On S-cyclic steiner systems

In this paper we investigate the structure of S-cyclic Steiner quadruple systems and derive a necessary condition on thier existence which might turn out to be sufficient. In the third chapter we prove a necessary condition on the existence of general S-cyclic Steiner systems. It turns out that S-cyclicityis a very restrictive property that hardly any systems with t ≠ 3 can have.     

On steiner points of convex bodies

Ifs is a mapping from the set of all convex bodies in Euclidean spaceE ^d toE ^d which is additive (in the sense of Minkowski), equivariant with respect to proper motions, and continuous, thens(K) is the Steiner point of the convex bodyK.     

On the extendability of steiner t-designs

Necessary and sufficient conditions for the extendability of residual designs of Steiner systems S(t,t + 1,v) are studied. In particular, it is shown that a residual design with respect to a single point is uniquely extendable, and the extendability of a residual design with respect to a pair of points is equivalent to a bipartition of the block graph of a related design. © 1993 John Wiley & Sons, Inc.     

From steiner centers to steiner medians

The Steiner distance of set S of vertices in a connected graph G is the minimum number of edges in a connected subgraph of G containing S. For n ≥ 2, the Steiner n-eccentricity e_n(v) of a vertex v of a graph G is the maximum Steiner distance among all sets S of n vertices of G that contain v. The Steiner n-center of G is the subgraph induced by those vertices of G having minimum n-eccentricity. The Steiner n-distance of a vertex v of G is defined as . The Steiner n-median of G is the subgraph of G induced by the vertices of G of minimum Steiner n-distance. Known algorithms for finding the Steiner n-centers and Steiner n-medians of trees are used to show that the distance between the Steiner n-centre and Steiner n-median of a tree can be arbitrarily large. Centrality measures that allow every vertex on a shortest path from the Steiner n-center to the Steiner n-median of a tree to belong to the “center” with respect to one of these measures are introduced and several proeprties of these centrality measures are established. © 1995 John Wiley & Sons, Inc.     

On the number of steiner triple systems

We obtain a new lower estimate for the number N(n) of nonisomorphic Steiner triple systems of order n: $$N(n) \geqslant n^{\frac{{n^2 }}{{12}} - O\left( {\frac{{n^2 }}{{logn}}} \right)} .$$ This makes it possible to show that log N(n) is of order n² log n.     

On angle sums and steiner points of polyhedra

In the first part, the Euler-Gram formula for the angle sum of a convex polytope is extended to cellular decompositions of arbitrary polyhedra. The second part contains an attempt to define Steiner points for unions of finitely many convex compact sets, and states some of their properties. Research supported by a fellowship of the Swiss National Foundation.     

On intersections of pairs of steiner triple systems

Numerous articles exist in the literature concerning the intersection properties of collections of Steiner triple systems based on the same point set ([4], [5], [11], [12], [14], [15], [16], [19], [20]). In this paper we discuss several methods, first used by the authors in [7], for treating such problems. We apply these methods to reprove some known results and to furnish several new results.     

On large sets of disjoint steiner triple systems I

Let D(v) denote the maximum number of pairwise disjoint Steiner triple systems of order v. In this paper, it is proved that if D(2 + n) = n, p is a prime number, p ≡ 7 (mod 8) or p? {5, 17, 19, 2}, and (p, n) ≠ (5, 1), then D(2 + pn) = pn.     

Orthogonal steiner systems

Aequationes mathematicae -     

On large sets of disjoint steiner triple systems,V

In a previous paper (J. Combin. Theory Ser. A34 (1983), 156–182), to construct large sets of disjoint STS(3n)'s (i.e., LTS(3n)'s), a kind of combinatorial design, denoted by LD(n), where n is the order of design, was introduced and it was shown that if there exist both an LD(n) and an LTS(n + 2), then there exists an LTS(3n) also. In this paper, after having established some recursive theorems of LD(n), the following result was proved: If n is a positive integer such that n≡11 (mod 12), then there exists an LD(n), except possibly n ∈ {23, 47, 59, 83, 107, 167, 179, 227, 263, 299, 347, 383, 719, 767, 923, 1439}.     

A deep-submicron steiner tree

An A-Tree is a rectilinear Steiner tree in which every sink is connected to a driver by a shortest length path, while simultaneously minimizing total wire length. This paper presents a polynomial approximation algorithm for the generalized version of an A-Tree problem with upper-bounded delays along each path from the driver to the sinks and with restrictions on the number of Steiner nodes. We refer to it as “Deep-submicron Steiner tree”, as minimizing the number of Steiner nodes is crucial for signal integrity issues in deep-submicron Very-Large-Scaled-Integrated-circuit (VLSI) designs. The idea behind the algorithm is to control two parameters in order to construct a feasible (with respect to the paths delays and the number of Steiner nodes) tree of small cost.The simulation results show the high efficiency of our approach.     

Anti-mitre steiner triple systems

A mitre in a Steiner triple system is a set of five triples on seven points, in which two are disjoint. Recursive constructions for Steiner triple systems containing no mitre are developed, leading to such anti-mitre systems for at least 9/16 of the admissible orders. Computational results for small cyclic Steiner triple systems are also included.     

On large sets of disjoint steiner triple systems,VI

Let D(v) denote the maximum number of pairwise disjoint Steiner triple systems of order v. In this paper, we prove that D(v) = v ? 2 holds for all v ≡ 1, 3 (mod 6) (v>7), except possibly v = 141, 283, 501, 789, 1501, 2365.     

Skew-orthogonal steiner triple systems

Two Steiner triple systems, S₁=(V,ℬ︁₁) and S₂=(V,ℬ︁₂), are orthogonal (S₁ ⟂ S₂) if ℬ︁₁ ∩ ℬ︁₂=∅︁ and if {u,ν} ≠ {x,y}, uνw,xyw ∈ ℬ︁₁, uνs, xyt ∈ ℬ︁₂ then s ≠ t. The solution to the existence problem for orthogonal Steiner triple systems, (OSTS) was a major accomplishment in design theory. Two orthogonal triple systems are skew-orthogonal (SOSTS, written S₁∼S₂) if, in addition, we require uνw, xys ∈ ℬ︁₁ and uνt, xyw∈ ℬ︁₂ implies s ≠ t. Orthogonal triple systems are associated with a class of Room squares, with the skew orthogonal triple systems corresponding to skew Room squares. Also, SOSTS are related to separable weakly union-free TTS. SOSTS are much rarer than OSTS; for example SOSTS(ν) do not exist for ν=3,9,15. Furthermore, a fundamental construction for the earlier OSTS proofs when ν ≡ 3 (mod 6) cannot exist. In the case ν≡ 1 ( mod 6) we are able to show existence except possibly for 22 values, the largest of which is 1315. There are at least two non-isomorphic OSTS(19)s one of which is SOSTS(19) and the other not. A SOSTS(27) was found, implying the existence of SOSTS(ν) for ν ≡ 3 (mod 6) with finitely many possible exceptions.     

On loop spaces of configuration spaces

This article gives an analysis of topological and homological properties for loop spaces of configuration spaces. The main topological results are given by certain choices of product decompositions of these spaces, as well as ``twistings" between the factors. The main homological results are given in terms of extensions of the ``infinitesimal braid relations" or ``universal Yang-Baxter Lie relations".