Balanced incomplete block designs with block size 8

The necessary conditions for the existence of a balanced incomplete block design on υ ≥ k points, with index λ and block size k, are that: For k = 8, these conditions are known to be sufficient when λ = 1, with 38 possible exceptions, the largest of which is υ = 3,753. For these 38 values of υ, we show (υ, 8, λ ) BIBDs exist whenever λ > 1 for all but five possible values of υ, the largest of which is υ = 1,177, and these five υ's are the only values for which more than one value of λ is open. For λ>1, we show the necessary conditions are sufficient with the definite exception of two further values of υ, and the possible exception of 7 further values of υ, the largest of which is υ=589. In particular, we show the necessary conditions are sufficient for all λ> 5 and for λ = 4 when υ ≠ 22. We also look at (8, λ) GDDs of type 7^m. Our grouplet divisible design construction is also refined, and we construct and exploit α ‐ frames in constructing several other BIBDs. In addition, we give a PBD basis result for {n: n ≡ 0, 1; mod 8, n ≥ 8}, and construct a few new TDs with index > 1. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 233–268, 2001     

Matrices and set intersections

The incidence matrix of a (υ, k, λ)-design is a (0, 1)-matrix A of order υ that satisfies the matrix equation AA^T=(k?λ)I+λJ, where A^T denotes the transpose of the matrix A, I is the identity matrix of order υ, J is the matrix of 1's of order υ, and υ, k, λ are integers such that 0<λ<k<υ?1. This matrix equation along with various modifications and generalizations has been extensively studied over many years. The theory presents an intriguing joining together of combinatorics, number theory, and matrix theory. We survey a portion of the recent literature. We discuss such varied topics as integral solutions, completion theorems, and λ-designs. We also discuss related topics such as Hadamard matrices and finite projective planes. Throughout the discussion we mention a number of basic problems that remain unsolved.     

Addition sets in a finite group

Addition sets with parameters (υ,k,λ,α) are defined in a finite group G of order υ, where α: G → G is a homomorphism or anti-homomorphism. It is shown that addition sets in a finite group have similar properties to that of (υ,k,λ,g) cyclic addition sets. The case α = I, where I: G → G is the identity automorphism, is studied and it is shown that no (υ,k,λ,I) group addition sets exist in an Abelian group of order υ, where ether υ is odd, υ≡2 (mod 4), or in certain cases when υ≡0 (mod 4). Many examples of group addition sets in both Abelian and non-Abelian groups are provided.     

Small embeddings of partial directed triple systems and partial triple systems with even λ

In 1976, Lindner and Rosa (Ars Combin. 1 (1976), 159–166) showed that a partial triple system with λ > 1 can be embedded in a finite triple system with the same λ. This result is improved in the case when λ is even by embedding a partial triple system on υ symbols in a triple system on t symbols, t ≡ 0,1 (mod 3), for all t >/ 3(λυ² + υ(2 ? λ) + 1). In the process, it is shown that for any λ >/ 1, a partial directed triple system on υ symbols can be embedded in a directed triple system on t symbols, t ≡ 0, 1 (mod 3), for all t ? 6λv² + 6v(1 ? λ) + 3, thus generalizing a result of Hamm (Proceedings, 14th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Boca Raton, Florida, 1983).     

Resolvable BIBDs with block size 8 and index 7

The necessary conditions for the existence of a resolvable BIBD RB(k,λ; v) are λ(v ? 1) = 0(mod k ? 1) and v = 0(mod k). In this article, it is proved that these conditions are also sufficient for k = 8 and λ = 7, with at most 36 possible exceptions. © 1994 John Wiley & Sons, Inc.     

A note on 3-blocked designs

A blocking set of a design different from a 2-(λ + 2, λ + 1, λ) design has at least 3 points. The aim of this note is to establish which 2-(v, k, λ) designs D with r ≥ 2λ may contain a blocking 3-set. The main results are the following. If D contains a blocking 3-set, then D is one of the following designs: a 2-(2λ + 3, λ + 1, λ), a 2-(2λ + 1), λ + 1, λ), a 2-(2λ - 1, λ, λ), a 2-(4λ + 3, 2λ + 1, λ) Hadamard design with λ odd, or a 2-(4λ - 1, 2λ, λ) Hadamard design. Moreover a blocking 3-set in a 2-(4λ + 3, 2λ + 1, λ) Hadamard design exists if and only if there is a line with three points. In the case of 2- (4λ - 1, 2λ, λ) Hadamard design with λ odd, we give necessary and sufficient conditions for the existence of a blocking 3-set, while in the case λ even, a necessary condition is given. © 1997 John Wiley & Sons, Inc.     

Resolvable perfect cyclic designs

Let k, λ, and υ be positive integers. A perfect cyclic design in the class PD(υ, k, λ) consists of a pair (Q, B) where Q is a set with |Q| = υ and B is a collection of cyclically ordered k-subsets of Q such that every ordered pair of elements of Q are t apart in exactly λ of the blocks for t = 1, 2, 3,…, k?1. To clarify matters the block [a₁, a₂, …, a_k] has cyclic order a₁ < a₂ < a₃ … < a_k < a₁ and a_i and a_i+1 are said to be t apart in the block where i + t is taken mod k. In this paper we are interested only in the cases where λ = 1 and υ ≡ 1 mod k. Such a design has $\text{υ(υ ? 1)}\text{k}$ blocks. If the blocks can be partitioned into υ sets containing $\text{(υ ? 1)}\text{k}$ pairwise disjoint blocks the design is said to be resolvable, and any such partitioning of the blocks is said to be a resolution. Any set of $\text{υ ? 1)}\text{k}$ pairwise disjoint blocks together with a singleton consisting of the only element not in one of the blocks is called a parallel class. Any resolution of a design yields υ parallel classes. We denote by RPD(υ, k, 1) the class of all resolvable perfect cyclic designs with parameters υ, k, and 1. Associated with any resolvable perfect cyclic design is an orthogonal array with k + 1 columns and υ rows with an interesting conjugacy property. Also a design in the class RPD(υ, k, 1) is constructed for all sufficiently large υ with υ ≡ 1 mod k.     

Construction of steiner quadruple systems having a prescribed number of blocks in common

Let q_υ=υ(υ–1)(υ–2)/24 and let I_υ={0, 1, 2, …, q_{υ–14}∪{qυ}–12, q_υ–8, q_υ}, for υ?8 Further, let J[υ] denote the set of all k such that there exists a pair of Steiner quadruple systems of order υ having exactly k blocks in common. We determine J[υ] for all υ=2ⁿ, n?2, with the possible exception of 7 cases for υ=16 and of 5 cases for each υ?32. In particular we show: J[υ]?I_υ for all υ≡2 or 4 (mod 6) and υ?8, J[4]={1}, J[8]=I₈={0, 2, 6, 14}, I₁₆?{103, 111, 115, 119, 121, 122, 123}?J[16], and I_υ? {q_υ–h:h=17, 18, 19, 21, 25}?J[υ] for all υ=2ⁿ, n?5.     

A hole‐size bound for incomplete t‐wise balanced designs

An incomplete t‐wise balanced design of index λ is a triple (X,H,??) where X is a υ–element set, H is a subset of X called the hole, and B is a collection of subsets of X called blocks, such that, every t‐element subset of X is either in H or in exactly λ blocks, but not both. If H is a hole in an incomplete t‐wise balanced design of order υ and index λ, then |H| ≤ υ/2 if t is odd and |H| ≤ (υ ? 1)/2 if t is even. In particular, this result establishes the validity of Kramer's conjecture that the maximal size of a block in a Steiner t‐wise balanced design is at most υ/2 if t is odd and at most (υ?1)/2 when t is even. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 269–284, 2001     

Embedding partial steiner triple systems is NP-complete

It is known that any partial Steiner triple system of order υ can be embedded in a Steiner triple system of order w whenever w?4υ+1, and w≡1, 3 (mod 6); moreover, it is conjectured that the same is true whenever w?2υ+1. By way of contrast, it is proved that deciding whether a partial Steiner triple system of order υ can be embedded in a Steiner triple system of order w for any w?2υ?1 is NP-complete. In so doing, it is proved that deciding whether a partial commutative quasigroup can be completed to a commutative quasigroup is NP-complete.     

The existence spectrum of golf designs

In this note, a golf design of order 41 is constructed. Combined Colbourn and Nonay's result, the existence spectrum of golf design of order υ is the set {υ: υ≡1 (mod 2), υ ≥ 3, υ ≠ 5}. © 2005 Wiley Periodicals, Inc. J Combin Designs 15: 84–89, 2007     

The spectrum for large sets of disjoint mendelsohn triple systems with any index

The spectrum for LMTS(v,1) has been obtained by Kang and Lei (Bulletin of the ICA, 1993). In this article, firstly, we give the spectrum for LMTS(v,3). Furthermore, by the existence of LMTS(v,1) and LMTS(v,3), the spectrum for LMTS(v,λ) is completed, that is v ≡ 2 (mod λ), v ≥ λ + 2, if λ ? 0(mod 3) then v ? 2 (mod 3) and if λ = 1 then v ≠ 6. © 1994 John Wiley & Sons, Inc.     

Covering pairs by quintuples with index λ  0 (mod 4)

A (v, k. λ) covering design of order v, block size k, and index λ is a collection of k-element subsets, called blocks, of a set V such that every 2-subset of V occurs in at least λ blocks. The covering problem is to determine the minimum number of blocks, α(v, k, λ), in a covering design. It is well known that $ \alpha \left({\nu,\kappa,\lambda } \right) \ge \left\lceil {\frac{\nu}{\kappa}\left\lceil {\frac{{\nu - 1}}{{\kappa - 1}}\lambda} \right\rceil} \right\rceil = \phi \left({\nu,\kappa,\lambda} \right) $, where [χ] is the smallest integer satisfying χ ≤ χ. It is shown here that α (v, 5, λ) = ?(v, 5, λ) + ? where λ ≡ 0 (mod 4) and e= 1 if λ (v?1)≡ 0(mod 4) and λv (v?1)/4 ≡ ?1 (mod 5) and e= 0 otherwise With the possible exception of (v,λ) = (28, 4). © 1993 John Wiley & Sons, Inc.     

All directed BIBDs with k = 3 exist

A directed BIBD with parameters ($\text{υ, b, r, k, λ}{}^1$) is a BIBD with parameters ($\text{υ, b, r, k, 2λ}{}^1$) in which each ordered pair of varieties occurs together in exactly $\text{λ}{}^1$ blocks. It is shown that $\text{λ}{}^1\text{υ(υ ? 1) ≡ 0}$ (mod 3) is a necessary and sufficient condition for the existence of a directed ($\text{υ, b, r, k, λ}{}^1$) BIBD with k = 3.     

A general recursive construction for quadruple systems

A Steiner-quadruple system of order υ is an ordered pair (X, Q), where X is a set of cardinality υ, and Q is a set of 4-subsets of X, called blocks, with the property that every 3-subset of X is contained in a unique block. In this paper we show that if there exists a quadruple system of order V with a subsystem of order υ, then there exists a quadruple system of order 3V ? 2υ with subsystems of orders V and υ. Hanani has given a proof of this result for υ = 1, and in a previous paper, the author has proved the case when V ≡ 2υ(mod 6). The construction given here proves all remaining cases, and has many applications to other existence problems for 3-designs.     

Existence of GBRDs with block size 4 and BRDs with block size 5

Chaudhry et al. (J Stat Plann Inference 106:303–327, 2002) have examined the existence of BRD(v, 5, λ)s for \({\lambda \in \{4, 10, 20\}}\). In addition, Ge et al. (J Combin Math Combin Comput 46:3–45, 2003) have investigated the existence of \({{\rm GBRD}(v,4,\lambda; \mathbb{G}){\rm s}}\) when \({\mathbb{G}}\) is a direct product of cyclic groups of prime orders. For the first problem, necessary existence conditions are (i) v ≥ 5, (ii) λ(v ? 1) ≡ 0 (mod4), (iii) λ v(v ? 1) ≡ 0 (mod 40), (iv) λ ≡ 0 (mod 2). We show these are sufficient, except for \({v=5, \lambda \in \{4,10\}}\). For the second problem, we improve the known existence results. Five necessary existence conditions are (i) v ≥ 4, (ii) \({\lambda \equiv 0\;({\rm mod}\,|\mathbb{G}|)}\), (iii) λ(v ? 1) ≡ 0 (mod 3), (iv) λ v(v ? 1) ≡ 0 (mod 4), (v) if v = 4 and \({|\mathbb{G}| \equiv 2\;({\rm mod}\,4)}\) then λ ≡ 0 (mod 4). We show these conditions are sufficient, except for \({\lambda = |\mathbb{G}|, (v,|\mathbb{G}|) \in \{(4,3), (10,2), (5,6), (7,4)\}}\) and possibly for \({\lambda = |\mathbb{G}|, (v,|\mathbb{G}|) \in \{(10,2h), (5,6h), (7,4h)\}}\) with h ≡ 1 or 5 (mod 6), h > 1.     

Block designs with large holes and α -resolvable BIBDs

In a (v, k, λ: w) incomplete block design (IBD) (or PBD [v, {k, w^*}. λ]), the relation v ≥ (k ? 1)w + 1 must hold. In the case of equality, the IBD is referred to as a block design with a large hole, and the existence of such a configuration is equivalent to the existence of a λ-resolvable BIBD(v ? w, k ? 1, λ). The existence of such configurations is investigated for the case of k = 5. Necessary and sufficient conditions are given for all v and λ ? 2 (mod 4), and for λ ≡ 2 mod 4 with 11 possible exceptions for v. © 1993 John Wiley & Sons, Inc.     

Resolutions of PG(5, 2) with point‐cyclic automorphism group

A t‐(υ, k, λ) design is a set of υ points together with a collection of its k‐subsets called blocks so that all subsets of t points are contained in exactly λ blocks. The d‐dimensional projective geometry over GF(q), PG(d, q), is a 2‐(q^d + q^d−1 + … + q + 1, q + 1, 1) design when we take its points as the points of the design and its lines as the blocks of the design. A 2‐(υ, k, 1) design is said to be resolvable if the blocks can be partitioned as ℛ = {R₁, R₂, …, R_s}, where s = (υ − 1)/(k−1) and each R_i consists of υ/k disjoint blocks. If a resolvable design has an automorphism σ which acts as a cycle of length υ on the points and ℛ^σ = ℛ, then the design is said to be point‐cyclically resolvable. The design associated with PG(5, 2) is known to be resolvable and in this paper, it is shown to be point‐cyclically resolvable by enumerating all inequivalent resolutions which are invariant under a cyclic automorphism group G = 〈σ〉 where σ is a cycle of length 63. These resolutions are the only resolutions which admit a point‐transitive automorphism group. Furthermore, some necessary conditions for the point‐cyclic resolvability of 2‐(υ, k, 1) designs are also given. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 2–14, 2000     

On a conjecture by B. Grünbaum

Denote by p_k(M) or υ_k(M) the number of k-gonal faces or k-valent of the convex 3-polytope M, respectively. Completely solving a problem by B. Grünbaum, the following theorem is proved: Given sequences of nonnegative integers p = (p₃, p₄,…p_m), υ = (υ₃, υ₄,…,υ_n) satisfying ∑_k?3(6−k)p_k + 2∑_k?3(3−k)υ_k = 12, there exists a convex 3-polytope M with p_k(M) = p_k for all k ≠ 6 and υ_k for all k ≠ 3 if and only if for the sequences p, υ the following does not hold: ∑p_i = 0 for i odd and ∑υ_i = 1 for i ? 0 (mod 3).     

Directed B(K, 1; v) with K = {4, 5} and {4, 6} related to deletion/insertion‐correcting codes

Motivated by the construction of t‐deletion/insertion‐correcting codes, we consider the existence of directed PBDs with block sizes from K = {4, 5} and {4, 6}. The spectra of such designs are determined completely in this paper. For any integer {υ ≥ 4, a DB({4,5} ,1; υ) exists if and only if υ∉{6, 8, 9, 12, 14}, and a DB({4, 6}, 1; υ) exists if and only if υ ≡ 0,1 mod 3 and υ∉{9,15}. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 147–156, 2001