Minimum embedding of Steiner triple systems into -designs I

A (K₄-e)-design on v+w points embeds a Steiner triple system (STS) if there is a subset of v points on which the graphs of the design induce the blocks of a STS. It is established that wv/3, and that when equality is met that such a minimum embedding of an STS(v) exists, except when v=15.     

Sequencing partial Steiner triple systems

A partial Steiner triple system of order $n$ is sequenceable if there is a sequence of length $n$ of its distinct points such that no proper segment of the sequence is a union of point‐disjoint blocks. We prove that if a partial Steiner triple system has at most three point‐disjoint blocks, then it is sequenceable.     

A proof of Lindner's conjecture on embeddings of partial Steiner triple systems

Lindner's conjecture that any partial Steiner triple system of order u can be embedded in a Steiner triple system of order v if and is proved. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 63–89, 2009     

On the number of partial Steiner systems

We give a simple proof of the result of Grable on the asymptotics of the number of partial Steiner systems S(t,k,m). © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 347–352, 2000     

Doyen–Wilson theorem for nested Steiner triple systems

The obvious necessary conditions for the existence of a nested Steiner triple system of order v containing a nested subsystem of order w are v ≥ 3w + 4 and v ≡ w ≡ 1 (mod 6). We show that these conditions are also sufficient. © 2004 Wiley Periodicals, Inc.     

A construction of 2-designs from Steiner systems and extendable designs

We give a construction of a 2-(mn²+1,mn,(n+1)(mn−1)) design starting from a Steiner system S(2,m+1,mn²+1) and an affine plane of order n. This construction is applied to known classes of Steiner systems arising from affine and projective geometries, Denniston designs, and unitals. We also consider the extendability of these designs to 3-designs.     

Uniform two‐class regular partial Steiner triple systems

A 2‐class regular partial Steiner triple system is a partial Steiner triple system whose points can be partitioned into 2‐classes such that no triple is contained in either class and any two points belonging to the same class are contained in the same number of triples. It is uniform if the two classes have the same size. We provide necessary and sufficient conditions for the existence of uniform 2‐class regular partial Steiner triple systems.     

Embedding partial Steiner triple systems so that their automorphisms extend

It is shown that there is a function g on the natural numbers such that a partial Steiner triple system U on u points can be embedded in a Steiner triple system V on ν points, in such a way that all automorphisms of U can be extended to V, for every admissible ν satisfying ν > g(u). We find exponential upper and lower bounds for g. © 2005 Wiley Periodicals, Inc. J Combin Designs.     

A probably fast,provably optimal algorithm for rectilinear Steiner trees

We use the technique of divide-and-conquer to construct a rectilinear Steiner minimal tree on a set of sites in the plane. A well-known optimal algorithm for this problem by Dreyfus and Wagner [10] is used to solve the problem in the base case. The run time of our optimal algorithm is probabilistic in nature: for all ? > 0, there exists b > 0 such that Prob[T(n) > 2^{b√n log n]>1–?, for n log n} > 1 – ?, for n sites uniformly distributed on a rectangle. The key fact in the run-time argument is the existence of probable bounds on the number of edges of an optimal tree crossing our subdivision lines. We can test these bounds in low-degree polynomial time for any given set of sites. © 1994 John Wiley & Sons, Inc.     

Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete

Deciding whether an arbitrary partial commutative quasigroup can be completed is known to be NP-complete. Here, we prove that it remains NP-complete even if the partial quasigroup is constructed, in the standard way, from a partial Steiner triple system. This answers a question raised by Rosa in [A. Rosa, On a class of completable partial edge-colourings, Discrete Appl. Math. 35 (1992) 293-299]. To obtain this result, we prove necessary and sufficient conditions for the existence of a partial Steiner triple system of odd order having a leave L such that E(L)=E(G) where G is any given graph.     

Cyclic resolvability of cyclic Steiner 2-designs

In this article, direct and recursive constructions for a cyclically resolvable cyclic Steiner 2-design are given. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 177–187, 1997     

Two finite embedding theorems for partial 3-quasigroups

In this paper it is shown that a finite partial (x, x, y) = y 3-quasigroup can be embedded in a finite (x, x, y) = y 3-quasigroup. This result coupled with the technique of proof is then used to show that a finite partial almost Steiner 3-quasigroup {(x, x, y) = y, (x, y, z) = (x, z, y) = (y, x, z)} can be embedded in a finite almost Steiner 3-quasigroup. Almost Steiner 3-quasigroups are of more than passing interest because just like Steiner 3-quasigroups ( = Steiner quadruple systems) all of their derived quasigroups are Steiner quasigroups.     

USING FINITE GEOMETRIES TO CONSTRUCT 3-PBIB(2) DESIGNS AND 3-DESIGNS

ＵＳＩＮＧＦＩＮＩＴＥＧＥＯＭＥＴＲＩＥＳＴＯＣＯＮＳＴＲＵＣＴ３－ＰＢＩＢ（２）ＤＥＳＩＧＮＳＡＮＤ３－ＤＥＳＩＧＮＳ￥ＹＡＮＧＢＥＮＦＵ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＣｈｅｎｇｄｕＴｅａｃｈｅｒｓＣｏｌｌｅｇｅ，Ｃｈｅｎｇｄｕ...     

Finite embedding theorems for partial Steiner triple systems

Let P be a finite set and (P,

₁), (P,

₂),…, (P,

_k) any collection of mutually disjoint partial Steiner triple systems. Then these partial triple systems can be embedded in finite mutually disjoint triple systems (S,

₁), (S,

₂),…, (S,

_k). This result is then used to prove the following more general result. If (P,

₁), (P,

₂),…, (P,

_k) are any collection of finite partial Steiner triple systems, then these partial triple systems can be embedded in finite triple systems (S,

₁), (S,

_j =

_i ∩

_j for all i ≠ j = 1, 2,…, k.     

A conjecture on small embeddings of partial Steiner triple systems

A well‐known, and unresolved, conjecture states that every partial Steiner triple system of order u can be embedded in a Steiner triple system of order υ for all υ ≡ 1 or 3, (mod 6), υ ≥ 2u + 1. However, some partial Steiner triple systems of order u can be embedded in Steiner triple systems of order υ <2u + 1. A more general conjecture that considers these small embeddings is presented and verified for some cases. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 313–321, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10017     

Unifying some known infinite families of combinatorial 3-designs

In this paper we present a construction of 3-designs by using a 3-design with resolvability. The basic construction generalizes a well-known construction of simple 3-(v,4,3) designs by Jungnickel and Vanstone (1986). We investigate the conditions under which the designs obtained by the basic construction are simple. Many infinite families of simple 3-designs are presented, which are closely related to some known families by Iwasaki and Meixner (1995), Laue (2004) and van Tran (2000, 2001). On the other hand, the designs obtained by the basic construction possess various properties: A theory of constructing simple cyclic 3-(v,4,3) designs by Köhler (1981) can be readily rebuilt from the context of this paper. Moreover many infinite families of simple resolvable 3-designs are presented in comparison with some known families. We also show that for any prime power q and any odd integer n there exists a resolvable 3-(qn+1,q+1,1) design. As far as the authors know, this is the first and the only known infinite family of resolvable t-(v,k,1) designs with t?3 and k?5. Those resolvable designs can again be used to obtain more infinite families of simple 3-designs through the basic construction.     

An embedding theorem for finite planar spaces

LetS be a finite planar space such that any two distinct planes intersect in a line. We show thatk≤n ²+1 for anyk-cap ofS, wheren is the order ofS. Moreover, if a (n ²+1)-cap exists inS, a necessary and sufficient condition is provided forS to be embeddable in a 3-dimensional projective space. Work supported by the National Research Project “Strutture geometriche, Combinatoria e loro applicazioni” of the italian M.U.R.S.T.