Some Indecomposable t-Designs

The existence of large sets of 5-(14,6,3) designs is in doubt. There are five simple 5-(14,6,6) designs known in the literature. In this note, by the use of a computer program, we show that all of these designs are indecomposable and therefore they do not lead to large sets of 5-(14,6,3) designs. Moreover, they provide the first counterexamples for a conjecture on disjoint t-designs which states that if there exists a t-(v, k, λ) design (X, D) with minimum possible value of λ, then there must be a t-(v, k, λ) design (X, D′) such that D∩ D′ = Ø.     

On Defining Sets of Full Designs with Block Size Three

A defining set of a t-(v, k, λ) design is a subcollection of its blocks which is contained in no other t-design with the given parameters, on the same point set. A minimal defining set is a defining set, none of whose proper subcollections is a defining set. The spectrum of minimal defining sets of a design D is the set {|M| | M is a minimal defining set of D}. We show that if a t-(v, k, λ) design D is contained in a design F, then for every minimal defining set d _D of D there exists a minimal defining set d _F of F such that \({d_D = d_F\cap D}\). The unique simple design with parameters \({{\left(v,k, {v-2\choose k-2}\right)}}\) is said to be the full design on v elements; it comprises all possible k-tuples on a v set. Every simple t-(v, k, λ) design is contained in a full design, so studying minimal defining sets of full designs gives valuable information about the minimal defining sets of all t-(v, k, λ) designs. This paper studies the minimal defining sets of full designs when t = 2 and k = 3. Several families of non-isomorphic minimal defining sets of these designs are found. For given v, a lower bound on the size of the smallest and an upper bound on the size of the largest minimal defining set are given. The existence of a continuous section of the spectrum comprising approximately v values is shown, where just two values were known previously.     

On three-designs of small order

For positive integers t?k?v and λ we define a t-design, denoted B_i[k,λ;v], to be a pair (X,B) where X is a set of points and B is a family, (B_i:i?I), of subsets of X, called blocks, which satisfy the following conditions: (i) |X|=v, the order of the design, (ii) |B_i|=k for each i?I, and (iii) every t-subset of X is contained in precisely λ blocks. The purpose of this paper is to investigate the existence of 3-designs with 3?k?v?32 and λ>0.Wilson has shown that there exists a constant N(t, k, v) such that designs B_t[k,λ;v] exist provided λ>N(t,k,v) and λ satisfies the trivial necessary conditions. We show that N(3,k,v)=0 for most of the cases under consideration and we give a numerical upper bound on N(3, k, v) for all 3?k?v?32. We give explicit constructions for all the designs needed.     

On Minimal Defining Sets of Full Designs and Self-Complementary Designs, and a New Algorithm for Finding Defining Sets of t-Designs

A defining set of a t-(v, k, λ) design is a partial design which is contained in a unique t-design with the given parameters. A minimal defining set is a defining set, none of whose proper partial designs is a defining set. This paper proposes a new and more efficient algorithm that finds all non-isomorphic minimal defining sets of a given t-design. The complete list of minimal defining sets of 2-(6, 3, 6) designs, 2-(7, 3, 4) designs, the full 2-(7, 3, 5) design, a 2-(10, 4, 4) design, 2-(10, 5, 4) designs, 2-(13, 3, 1) designs, 2-(15, 3, 1) designs, the 2-(25, 5, 1) design, 3-(8, 4, 2) designs, the 3-(12, 6, 2) design, and 3-(16, 8, 3) designs are given to illustrate the efficiency of the algorithm. Also, corrections to the literature are made for the minimal defining sets of four 2-(7, 3, 3) designs, two 2-(6, 3, 4) designs and the 2-(21, 5, 1) design. Moreover, an infinite class of minimal defining sets for 2-((v) || 3){v\choose3} designs, where v ≥ 5, has been constructed which helped to show that the difference between the sizes of the largest and the smallest minimal defining sets of 2-((v) || 3){v\choose3} designs gets arbitrarily large as v → ∞. Some results in the literature for the smallest defining sets of t-designs have been generalized to all minimal defining sets of these designs. We have also shown that all minimal defining sets of t-(2n, n, λ) designs can be constructed from the minimal defining sets of their restrictions when t is odd and all t-(2n, n, λ) designs are self-complementary. This theorem can be applied to 3-(8, 4, 3) designs, 3-(8, 4, 4) designs and the full 3-(8 || 4)3-{8 \choose 4} design using the previous results on minimal defining sets of their restrictions. Furthermore we proved that when n is even all (n − 1)-(2n, n, λ) designs are self-complementary.     

Block-transitive designs in affine spaces

This paper deals with block-transitive t-(v, k, λ) designs in affine spaces for large t, with a focus on the important index λ = 1 case. We prove that there are no non-trivial 5-(v, k, 1) designs admitting a block-transitive group of automorphisms that is of affine type. Moreover, we show that the corresponding non-existence result holds for 4-(v, k, 1) designs, except possibly when the group is 1-D affine. Our approach involves a consideration of the finite 2-homogeneous affine permutation groups.     

Further results on the existence of nested orthogonal arrays

Nested orthogonal arrays provide an option for designing an experimental setup consisting of two experiments, the expensive one of higher accuracy being nested in a larger and relatively less expensive one of lower accuracy. We denote by OA_(λ, μ)(t, k, (v, w)) (or OA(t, k, (v, w)) if λ = μ = 1) a (symmetric) orthogonal array OA _λ (t, k, v) with a nested OA _μ (t, k, w) (as a subarray). It is proved in this article that an OA(t, t + 1,(v, w)) exists if and only if v ≥ 2w for any positive integers v, w and any strength t ≥ 2. Some constructions of OA_(λ, μ)(t, k, (v, w))′s with λ ≠ μ and k ? t > 1 are also presented.     

Computational complexity of reconstruction and isomorphism testing for designs and line graphs

Graphs with high symmetry or regularity are the main source for experimentally hard instances of the notoriously difficult graph isomorphism problem. In this paper, we study the computational complexity of isomorphism testing for line graphs of t-(v,k,λ) designs. For this class of highly regular graphs, we obtain a worst-case running time of O(vlogv+O(1)) for bounded parameters t, k, λ.In a first step, our approach makes use of the Babai-Luks algorithm to compute canonical forms of t-designs. In a second step, we show that t-designs can be reconstructed from their line graphs in polynomial-time. The first is algebraic in nature, the second purely combinatorial. For both, profound structural knowledge in design theory is required. Our results extend earlier complexity results about isomorphism testing of graphs generated from Steiner triple systems and block designs.     

A symmetric design with parameters 2-(49, 16, 5)

A symmetric 2-design with parameters (v, k, λ) = (49, 16, 5) is constructed. Both this design and its residual, a design with parameters (v, b, r, k, λ) = (33, 48, 16, 11, 5), seem to be new. The derived designs do not have repeated blocks. The group of the design is cyclic of order 15. There is no polarity.     

Divisible design graphs

A divisible design graph is a graph whose adjacency matrix is the incidence matrix of a divisible design. Divisible design graphs are a natural generalization of (v,k,λ)-graphs, and like (v,k,λ)-graphs they make a link between combinatorial design theory and algebraic graph theory. The study of divisible design graphs benefits from, and contributes to, both parts. Using information of the eigenvalues of the adjacency matrix, we obtain necessary conditions for existence. Old results of Bose and Connor on symmetric divisible designs give other conditions and information on the structure. Many constructions are given using various combinatorial structures, such as (v,k,λ)-graphs, distance-regular graphs, symmetric divisible designs, Hadamard matrices, and symmetric balanced generalized weighing matrices. Several divisible design graphs are characterized in terms of the parameters.     

On defining sets of full designs

A defining set of a t-(v,k,λ) design is a subcollection of its blocks which is contained in a unique t-design with the given parameters on a given v-set. A minimal defining set is a defining set, none of whose proper subcollections is a defining set. The spectrum of minimal defining sets of a design D is the set {|M|∣M is a minimal defining set of D}. The unique simple design with parameters is said to be the full design on v elements; it comprises all possible k-tuples on a v set. We provide two new minimal defining set constructions for full designs with block size k≥3. We then provide a generalisation of the second construction which gives defining sets for all k≥3, with minimality satisfied for k=3. This provides a significant improvement of the known spectrum for designs with block size three. We hypothesise that this generalisation produces minimal defining sets for all k≥3.     

On the construction of handcuffed designs

A handcuffed design with parameters ν, k, λ consists of a set of ordered k-subsets of a v-set, called handcuffed blocks; in a block (a₁, a₂, a_k) each element is assumed to be “handcuffed” to its neighbors. A block, therefore, contains k ? 1 handcuffed pairs, the pairs being considered unordered. Each element of the v-set appears in exactly r blocks, and each pair of distinct elements of the v-set is handcuffed in exactly A blocks of the design.These designs have been studied recently by Hung and Mendelsohn [1], who construct a number of families of such designs by recursive methods. In this paper we show how difference methods can be applied to the construction of handcuffed designs. The methods are powerful, and a number of families of designs are constructed. A main new result is the determination of necessary and sufficient conditions for the existence of handcuffed designs for all parameter sets in which v is an odd prime power.     

A. translation of J. X. Lu's “an existence theory for resolvable balanced incomplete block designs”

In 1984, J. X. Lu proved the following statement. Given any k and λ, there exists a constant c(k, λ) such that an RB[v,k,λ] exists for all v > c(k,λ) satisfying the usual necessary conditions. Lu's paper was written in Chinese and, unfortunately, its accessibility is limited. We have translated Lu's paper into English and have also given a new interpretation of his constructions for resolvable block designs. © 1995 John Wiley & Sons, Inc.     

Upper bounds on the general covering number Cλ(v,k, t,m)

A collection of k‐subsets (called blocks) of a v‐set X (v) = {1, 2,…, v} (with elements called points) is called a t‐(v, k, m, λ) covering if for every m‐subset M of X (v) there is a subcollection of with such that every block K ∈ has at least t points in common with M. It is required that v ≥ k ≥ t and v ≥ m ≥ t. The minimum number of blocks in a t‐(v, k, m, λ) covering is denoted by C_λ(v, k, t, m). We present some constructions producing the best known upper bounds on C_λ(v, k, t, m) for k = 6, a parameter of interest to lottery players. © 2004 Wiley Periodicals, Inc.     

A new class of splitting 3-designs

Splitting t-designs were first formulated by Huber in recent investigation of optimal (t − 1)-fold secure splitting authentication codes. In this paper, we investigate the construction and existence of splitting t-designs t-(v, u × k, 1) splitting designs and, show that there exists a 3-(v, 3 × 2, 1) splitting design if and only if v ≡ 2 (mod 8). As its application, we obtain a new infinite class of optimal 2-fold secure splitting authentication codes.     

A lower bound for v in a t − (v,k, λ) design

In this paper it is shown that if v ? k + 1 then $\text{v ? t ? 1 + (k ? t + 1)(k ? t + 2)}\text{λ}$, where v, k, λ and t are the characteristic parameters of a t ? (v, k, λ) design. We compare this bound with the known lower bounds on v.     

Incomplete perfect mendelsohn designs with block size 4 and holes of size 2 and 3

Let v, k, and n be positive integers. An incomplete perfect Mendelsohn design, denoted by k-IPMD(v, n), is a triple (X, Y, ??) where X is a v-set (of points), Y is an n-subset of X, and ?? is a collection of cyclically ordered k-subsets of X (called blocks) such that every ordered pair (a, b) ∈ (X × X)\(Y × Y) appears t-apart in exactly one block of ?? and no ordered pair (a,b) ∈ Y × Y appears in any block of ?? for any t, where 1 ≤ t ≤ k ? 1. In this article, the necessary conditions for the existence of a 4-IPMD(v, n), namely (v ? n) (v ? 3n ? 1) ≡ 0 (mod 4) and v ≥ 3n + 1, are shown to be sufficient for the case n = 3. For the case n = 2, these conditions are sufficient except for v = 7 and with the possible exception of v = 14,15,18,19,22,23,26,27,30. The latter result provides a useful application to the problem relating to the packing of perfect Mendelsohn designs with block size 4. © 1994 John Wiley & Sons, Inc.     

Resolvable path designs

A resolvable (balanced) path design, RBPD(v, k, λ) is the decomposition of λ copies of the complete graph on v vertices into edge-disjoint subgraphs such that each subgraph consists of $\text{v}\text{k}$ vertex-disjoint paths of length k ? 1 (k vertices). It is shown that an RBPD(v, 3, λ) exists if and only if v ≡ 9 (modulo 12/gcd(4, λ)). Moreover, the RBPD(v, 3, λ) can have an automorphism of order $\text{v}\text{3}$. For k > 3, it is shown that if v is large enough, then an RBPD(v, k, 1) exists if and only if v ≡ k² (modulo lcm(2k ? 2, k)). Also, it is shown that the categorical product of a k-factorable graph and a regular graph is also k-factorable. These results are stronger than two conjectures of P. Hell and A. Rosa     

Extending symmetric designs

If a symmetric 2-design with parameters (v, k, λ) is extendable, then one of the following holds: v = 4λ + 3, k = 2λ + 1; or v = (λ + 2)(λ² + 4λ + 2), k = λ² + 3λ + 1; or v = 111, k = 11, λ = 1; or v = 495, k = 39, λ = 3. In particular, there are at most three sets of extendable symmetric design parameters with any given value of λ. As a consequence, the only twice-extendable symmetric design is the 21-point projective plane.     

Spectrum of resolvable directed quadruple systems

A t-(v, k, 1) directed design (or simply a t-(v, k, 1)DD) is a pair (S, ℐ), where S is a v-set and ℐ is a collection of k-tuples (called blocks) of S, such that every t-tuple of S belongs to a unique block. The t-(v, k, 1)DD is called resolvable if ℐ can be partitioned into some parallel classes, so that each parallel class is a partition of S. It is proved that a resolvable 3-(v, 4, 1)DD exists if and only if v = 0 (mod 4).