Constructing t-designs from t-wise balanced designs

John P. McSorley and Leonard H. Soicher

Abstract

We give a construction to obtain a t-design from a t-wise balanced design. More precisely, given a positive integer k and a t- (v, {k_{1}, k_{2}, …, k_{s}}, λ) design D, with with all block-sizes k_{i} occurring in D and 1 ≤ t ≤ k ≤ k_{1} < k_{2} < ⋯ < k_{s}, the construction produces a t-(v, k, nλ) design D^{∗}, with n = lcm(\binom{k_{1}−t}{k−t}, …, \binom{k_{s}−t}{k−t}). We prove that Aut(D) is a subgroup of Aut(D^{∗}), with equality when both λ = 1 and t < k. We employ our construction in another construction, which, given a t-(v, k, λ) design with 1 ≤ t < k < v, and a point of this design, yields a t-(v − 1, k − 1, (k − t)λ) design. Many of the t-designs coming from our constructions appear to be new.

1 Introduction

For t a positive integer, a t-wise balanced design D is an ordered pair (X, B), where X is a finite non-empty set (of points) and B is a finite non-empty multiset of subsets of X (called blocks), such that every t-subset of X is contained in a constant number λ > 0 of blocks. If v = |X| and K is the set of sizes of the blocks, then we call D a t-(v, K, λ) design. If all blocks of D have the same size k (i.e. K = {k}), then D is called a t-design or a t-(v, k, λ) design.

In this note we give a construction (the ∗-construction) to obtain a tdesign from a t-wise balanced design. More precisely, given a positive integer k and a t-(v, {k_{1}, k_{2}, …, k_{s}}, λ) design D, with with all block-sizes k_{i} occurring in D and 1 ≤ t ≤ k ≤ k_{1} < k_{2} < ⋯ < k_{s}, the ∗-construction produces a t-(v, k, nλ) design D^{∗}, with n = lcm(\binom{k_{1}−t}{k−t}, …, \binom{k_{s}−t}{k−t}). We prove that Aut(D) is a subgroup of Aut(D^{∗}), with equality when both λ = 1 and t < k.

We employ the ∗-construction in another construction (the #-construction), which, given a t-(v, k, λ) design with 1 ≤ t < k < v, and a point of this design, yields a t-(v − 1, k − 1, (k − t)λ) design. Many of the t-designs coming from our constructions appear to be new, and although they usually have repeated blocks, they often, via their constructions, have quite large automorphism groups.

2 The ∗-construction

The input to the ∗-construction consists of positive integers t and k, and a t-(v, {k_{1}, k_{2}, …, k_{s}}, λ) design D, with all block-sizes k_{i} occurring in D and 1 ≤ t ≤ k ≤ k_{1} < k_{2} < ⋯ < k_{s}. Now for i = 1, 2, …, s define

n_{i} = \binom{k_{i} − t}{k − t}, n = lcm(n_{1}, n_{2}, …, n_{s}), m_{i} = \frac{n}{n_{i}} .  (1)

The output of the ∗-construction is a block design D^{∗}, which we prove below to be a t-(v, k, nλ) design.

The point-set of D^{∗} is that of D, and to construct the block-multiset B^{∗} of D^{∗} we proceed as follows:

• start by setting B^{∗} to be the empty multiset;

• for each i = 1, 2, …, s and for each block B ∈ B of size k_{i} (including repeats) do:

– insert m_{i} copies of every k-subset of B into B^{∗}.

Clearly, D^{∗} depends on the choice of k as well as on D. Less obviously, since the t-wise balanced design D may be t′-wise balanced for some t′ ≠ t, D^{∗} may depend on the choice of t. When we wish to make these dependencies explicit, we shall use the notation D^{∗}(t, k) instead of D^{∗}.

Theorem 2.1 Let k be a positive integer and let D = (X, B) be a t-(v, {k_{1}, k_{2}, …, k_{s}}, λ) design, with all block-sizes k_{i} occurring in D and 1 ≤ t ≤ k ≤ k_{1} < k_{2} < ⋯ < k_{s}. Then D^{∗} = D^{∗}(t, k) = (X, B^{∗}) is a t-(v, k, nλ) design, where n = lcm(n_{1}, n_{2}, …, n_{s}) and n_{i} = \binom{k_{i}−t}{k−t}.

Proof. Let T be any t-subset of X. Suppose that B is a block of B of size k_{i} containing T. Then the number of k-subsets of B which contain T is n_{i} = \binom{k_{i}−t}{k−t}. Each of these k-subsets is added to B^{∗} exactly m_{i} = n/n_{i} times. Hence B contributes exactly n_{i}m_{i} = n blocks containing T to B^{∗}. Now T is contained in exactly λ blocks in B, and so in exactly nλ blocks in B^{∗}.

We have defined n to be lcm(n_{1}, n_{2}, …, n_{s}). We could have chosen n to be any common multiple of {n_{1}, n_{2}, …, n_{s}}, but, in order to keep nλ as small as possible, we choose the least common multiple. We also remark that the ∗-construction works perfectly well when s = 1, that is, when D is a t-design.

Example 1 Let D be the 2-(11, {3, 5}, 1) design with point-set X = {1, 2, …, 9, T, E} (here T = 10 and E = 11), and block-multiset B =

[167, 18E, 19T, 268, 279, 2T E, 369, 37E, 38T, 46T, 478, 49E, 56E, 57T, 589, 12345]

(see [1, p.187]).

(a) Suppose t = k = 2. Here k_{1} = 3, k_{2} = 5, and each n_{i} = n = m_{i} = 1. So D^{∗}(2, 2) is the 2-(11, 2, 1) design consisting of all the 2-subsets of X.

(b) The case t = 2, k = 3 is more interesting. Here k = k_{1} = 3, k_{2} = 5, n_{1} = 1, n_{2} = 3, n = 3, m_{1} = 3, and m_{2} = 1. So D^{∗} = D^{∗}(2, 3) is a 2- (11, 3, 3) design, an (11, 55, 15, 3, 3)-BIBD. The block-multiset of D^{∗} consists of three copies of each block of D of size 3, together with all the 3-subsets of {1, 2, 3, 4, 5}.

The ∗-construction was found as a result of looking for 2-designs with repeated blocks to help fill up Preece’s catalogue [4]. Many new examples coming from this construction have since gone into the catalogue.

3 The #-construction

Let T = (X, B) be a t-(v, k, λ) design with 1 ≤ t < k < v, and let x ∈ X. We employ the ∗-construction in a new construction (the #-construction) which produces a t-(v − 1, k − 1, (k − t)λ) design when given input T and x. The #-construction proceeds as follows:

Let X′ = X \ {x}, and let B′ be the multiset consisting of all B \ {x} with B ∈ B (counting repeats). Denote the resulting block design (X′, B′) by T \ x, which is a t-(v − 1, {k − 1, k}, λ) design (whose isomorphism class may depend on the choice of x). Next, apply the ∗-construction with input t, k − 1 and T \ x to obtain (T \ x)^{∗}(t, k − 1), a t-(v − 1, k − 1, (k − t)λ) design. We denote this output of the #-construction by T^{#}(t, x).

Example 2 Start with the large Witt design W, the unique (up to isomorphism) 5-(24, 8, 1) design; see [3, Chapter 8], where W is called the Mathieu design M_{24}. Now W is also a 4-(24, 8, 5) design, a 3-(24, 8, 21) design, and a 2-(24, 8, 77) design. Let x be a point of W (it matters not which one, since the automorphism group M_{24} of W acts transitively (in fact 5-transitively) on the point-set of W). Then W^{#}(5, x) is a 5-(23, 7, 3) design, W^{#}(4, x) is a 4-(23, 7, 20) design, W^{#}(3, x) is a 3-(23, 7, 105) design, and W^{#}(2, x) is a 2-(23, 7, 462) design.

Example 3 Start with a projective plane P = (X, B) of order m ≥ 2, a 2-(m^{2} + m + 1, m + 1, 1) design. Now, given any x ∈ X, construct P^{#}(2, x), which is a 2-(m^{2} + m, m, m − 1) design.

4 Automorphism groups

The automorphism group of a t-wise balanced design D = (X, B), denoted Aut(D), is the group consisting of all the permutations of X which leave the block-multiset B invariant. We now investigate the relationship of the automorphism groups of D and D^{∗}(t, k). For a block B ∈ B, we let mult(B) denote its multiplicity in B.

Theorem 4.1 Let k be a positive integer, let D = (X, B) be a t-(v, {k_{1}, k_{2}, …, k_{s}}, λ) design, with all block-sizes k_{i} occurring in D and 1 ≤ t ≤ k ≤ k_{1} < k_{2} < ⋯ < k_{s}, and let D^{∗} = D^{∗}(t, k) = (X, B^{∗}) be the t-design obtained from the ∗-construction. Then

(i) Aut(D) ⊆ Aut(D^{∗}); (ii) if λ = 1 and t < k, then Aut(D) = Aut(D^{∗}).

Proof. (i) Let α ∈ Aut(D). Let B^{∗} be an arbitrary block in B^{∗}, hence there is a block B ∈ B which contains B^{∗} as a k-subset. Suppose that α(B) = C for some block C ∈ B, and that α(B^{∗}) = C^{∗}. Then clearly C^{∗} is a k-subset of C, a block of B, hence C^{∗} ∈ B^{∗}. Now we must show that mult(C^{∗}) = mult(B^{∗}) (in B^{∗}) to conclude that α ∈ Aut(D^{∗}).

Fix i. Let B_{1}, B_{2}, …, B_{d} be the distinct blocks of B of size k_{i} which contain B^{∗}, and let C_{1}, C_{2}, …, C_{e} be the distinct blocks of B of size k_{i} which contain C^{∗}. Now, because α ∈ Aut(D), we must have d = e and for every j with 1 ≤ j ≤ d there must exist a unique j′ with 1 ≤ j′ ≤ d for which α(B_{j}) = C_{j′}. Hence mult(B_{j}) = mult(C_{j′}) since α preserves block multiplicities.

Now let f_{i} be the number of blocks (counting multiplicities) of B of size k_{i} which contain B^{∗}, and let g_{i} be the number of blocks (counting multiplicities) of B of size k_{i} which contain C^{∗}. Then g_{i} = ∑_{j′=1}^{d} mult(C_{j′}) = ∑_{j=1}^{d} mult(B_{j}) = f_{i}, and so, in B^{∗}, we have mult(C^{∗}) = ∑_{i=1}^{s} g_{i}m_{i} = ∑_{i=1}^{s} f_{i}m_{i} = mult(B^{∗}) (m_{i} defined in (1)), as required. Hence α ∈ Aut(D^{∗}).

(ii) We first note that, because λ = 1, then mult(B) = 1 for every block B ∈ B. Secondly, if R^{∗} is an arbitrary block in B^{∗} then, again because λ = 1, there is a unique block R ∈ B, with R^{∗} ⊆ R.

Now let γ ∈ Aut(D^{∗}). We must show that, for every block B ∈ B, we have γ(B) ∈ B. Then, from above, mult(γ(B)) = 1 = mult(B), so γ ∈ Aut(D). This will show that Aut(D^{∗}) ⊆ Aut(D); part (i) then gives the result.

Fix i. Let B be an arbitrary block of B of size k_{i}, and let B^{∗} be an arbitrary k-subset of B, and let γ(B^{∗}) = C^{∗}. Now, because γ ∈ Aut(D^{∗}), then C^{∗} ∈ B^{∗}. So, from above, there is a unique block C ∈ B, with C^{∗} ⊆ C. We will show that γ(B) = C.

First we show that γ(B) ⊆ C. Suppose that γ(B) ⊈ C, then there is an element x ∈ B\B^{∗} with γ(x) ∉ C. Let D be a (k−1)-subset of B^{∗} ⊆ B, then D^{∗} = {x} ∪ D is a k-subset of B ∈ B, so D^{∗} ∈ B^{∗}. Hence E^{∗} = γ(D^{∗}) ∈ B^{∗}, and there is a block E ∈ B with E^{∗} ⊆ E. Now E ≠ C because γ(x) ∈ E but γ(x) ∉ C. Hence E and C are distinct blocks of B. However, γ(D) ⊆ E, and D ⊆ B^{∗} so γ(D) ⊆ γ(B^{∗}) = C^{∗} ⊆ C. Now t < k so t ≤ k − 1 = |γ(D)|. Now let T be any t-subset of γ(D), then the distinct blocks E and C both contain T, a contradiction since λ = 1. Hence γ(B) ⊆ C.

To show that C ⊆ γ(B) we show that γ^{−1}(C) ⊆ B by noting that γ^{−1}(C^{∗}) = B^{∗}, and so the proof follows as above. Hence γ(B) = C and, since i was arbitrary, the result is proved.

Example 4 We take D to be the 2-(11, {3, 5}, 1) design of Example 1. Then |Aut(D)| = 120; indeed Aut(D) is isomorphic to Sym(5), and acts naturally as this group on the subset {1, 2, 3, 4, 5} of the point-set (checked using GAP [2] and its DESIGN package [5]).

(a) D^{∗}(2, 2) is the complete 2-(11, 2, 1) design. Hence Aut(D) ⊆ Aut(D^{∗}(2, 2)) = Sym(11), illustrating Theorem 4.1(i), and also showing that if λ = 1 and t = k then Aut(D) ≠ Aut(D^{∗}(t, k)) is possible (see Theorem 4.1(ii)).

(b) D^{∗} = D^{∗}(2, 3) is a 2-(11, 3, 3) design with |Aut(D^{∗})| = 120 (double checked with the DESIGN package). This illustrates Theorem 4.1(ii).

Example 5 This example shows that if λ > 1 then Aut(D) ≠ Aut(D^{∗}(t, k)) is possible, even when t < k. We apply the #-construction to the projective plane P of order 4, to obtain a 2-(20, 4, 3) design P^{#} = P^{#}(2, x) = (X, B), which has a point-transitive automorphism group of order 5760. Then, we take x ∈ X and obtain a 2-(19, {3, 4}, 3) design D = P^{#} \ x (using the notation of Section 3). (The choice of x does not affect the isomorphism class of D since P^{#} is point-transitive). Finally, construct a 2-(19, 3, 6) design D^{∗} = D^{∗}(2, 3). It turns out that |Aut(D)| = 288, but |Aut(D^{∗})| = 576. The construction of these designs and the determination of their automorphism groups was done using the DESIGN package.

Example 6 The DESIGN package shows that, up to isomorphism, there are exactly four 2-(11, {4, 5}, 2) designs (not counting the unique 2-(11, 5, 2) design). These designs D have automorphism groups of orders 6, 8, 12, and 120, as do the corresponding D^{∗}(2, 4), which are (believed to be new) 2-(11, 4, 6) designs. Note that these examples show that the converse of Theorem 4.1(ii) does not hold.

References

[1] Charles J. Colbourn and Jeffrey H. Dinitz (Editors), The CRC Handbook of Combinatorial Designs, CRC Press, 1996.

[2] The GAP Group, GAP — Groups, Algorithms, and Programming, Version 4.4; Aachen, St Andrews, 2004, http://www.gap-system.org/

[3] D.R. Hughes and F.C. Piper, Design Theory, Cambridge University Press, 1985, paperback edition, 1988.

[4] D. A. Preece, A selection of BIBDs with repeated blocks, r ≤ 20, gcd(b, r, λ) = 1, preprint, 2003.

[5] Leonard H. Soicher, The DESIGN package for GAP, Version 1.1, 2004,

   http://designtheory.org/software/gap_design/