Enumeration of t-Designs Through Intersection Matrices

In this paper, we exploit some intersection matrices to empower a backtracking approach based on Kramer–Mesner matrices. As an application, we consider the interesting family of simple t-(t + 8,t + 2,4) designs, 1 ≤ t ≤ 4, and provide a complete classification for t = 1,4, as well as a classification of all non-rigid designs for t = 2,3. We also enumerate all rigid designs for t = 2. The computations confirm the results obtained in Denny and Mathon [4] through the new approach which is much simpler. Finally a list of other designs constructed by this method is provided.     

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 the BIB design having the minimum p-rank

It is shown that (i) among BIB designs with parameters (2^t+1 ? 1, 2^t+1 ? 1, 2^t ? 1, 2^t ? 1, 2^t?1 ? 1), the incidence matrix of the BIB design PG(t, 2):t ? 1 derived from a finite projective geometry PG(t, 2) has the minimum 2-rank and (ii) among BIB designs with parameters (2^t, 2^t+1 ? 2, 2^t ? 1, 2^?1, 2^t?1 ? 1), the incidence matrix of the BIB design EG(t, 2):t ? 1 derived from an affine geometry EG(t, 2) has the minimum 2-rank.     

Studying designs via multisets

A new method to study families of finite sets, in particular t-designs, by studying families of multisets (also called lists) and their relationships with families of sets, is developed. Notion of the tag for a subset defined earlier by one of the authors is extended to a submultiset. A new concept t-(v, k, λ) list design is defined and studied. Basic existence theory for designs is extended to a new set up of list designs. In particular tags are used to prove that signed t-list designs exist whenever necessary conditions are satisfied. The concepts of homomorphisms and block spreading are extended to this new set up.     

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.     

New classes of complete balanced Howell rotations

Complete balanced Howell rotations (CBHR) owe their origins to duplicate bridge tournaments but have since been shown to possess of deep combinatorial properties. They include many other combinatorial designs as special cases, such as: balanced Howell rotations, weak complete balanced Howell rotations, Room squares, Howell designs, and a class of balanced incomplete block designs.All known CBHR's are for n partnerships such that n = 2^t(p^r + 1), where p^r is an odd prime power and t a natural number. In most cases, p^r ≡ 3(mod 4) is also assumed. Berlekamp and Hwang gave constructions of CBHR's for each such n > 3 with t = 0; Schellenberg gave constructions for each such n with t = 1. In this paper, we construct CBHR for each such n with t arbitrary.     

Non-trivial t-designs without repeated blocks exist for all t

We study several classes of arrays generalizing designs and orthogonal arrays. We use these to construct non-trivial t-designs without repeated blocks for all t.     

Hypergraphical t-designs

We introduce a theory of hypergraphical t-designs. We show the existence of these designs and prove a finiteness theorem on these designs for infinitely many parameter sets. We also give effective bounds on the number of points in these cases. These results generalize some results on graphical t-designs of Alltop, Chee and Betten-Klin-Laue-Wassermann.     

New proof of a theorem of Szekeres

A Hadamard matrix H of order 16t² is constructed for all t for which there is a Hadamard matrix of order 4t, in such a way that each row of H contains exactly 8t² + 2t ones. As a consequence a new method of constructing the symmetric block designs with parameters (16t², 8t² + 2t, 4t² + 2t) for all t for which there is a Hadamard matrix of order 4t is given.     

Orthogonal designs II

Orthogonal designs are a natural generalization of the Baumert-Hall arrays which have been used to construct Hadamard matrices. We continue our investigation of these designs and show that orthogonal designs of type (1,k) and ordern exist for everyk < n whenn = 2 ^t+2?3 andn = 2 ^t+2?5 (wheret is a positive integer). We also find orthogonal designs that exist in every order 2n and others that exist in every order 4n. Coupled with some results of earlier work, this means that theweighing matrix conjecture ‘For every ordern ≡ 0 (mod 4) there is, for eachk ?n, a square {0, 1, ? 1} matrixW = W(n, k) satisfyingWW ^t =kIn’ is resolved in the affirmative for all ordersn = 2^t+1?3,n = 2^t+1?5 (t a positive integer). The fact that the matrices we find are skew-symmetric for allk < n whenn ≡ 0 (mod 8) and because of other considerations we pose three other conjectures about weighing matrices having additional structure and resolve these conjectures affirmatively in a few cases. In an appendix we give a table of the known results for orders ? 64.     

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.     

Construction of D-optimal designs for N ≡ 2 mod 4 using block-circulant matrices

Circulant matrices of order t with elements circulant matrices of order s are used for the construction of D-optimal saturated designs of order N = 2st. A number of new designs are so constructed. The optimal design for N = 66 is constructed for the first time.     

Partial geometric designs and two-class partially balanced designs

It is shown that a partial geometric design with parameters (r, k, t, c) satisfying certain conditions is equivalent to a two-class partially balanced incomplete block design. This generalizes a result concerning partial geometric designs and balanced incomplete block designs.     

On extensions of some block designs

There are some results concerning t-designs in which the number of points in the intersection of two blocks takes less than t values. For example, if t = 2, then the design is symmetric (in such a design, v = b or, equivalently, k = r). In 1974, B. Gross described t-(v, k, l) designs that, for some integer s, 0 < s < t, do not contain two blocks intersecting at exactly s points. Below, it is proved that potentially infinite series of designs from the claim of Gross’ theorem are finite. Gross’ theorem is substantially sharpened.     

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.     

On lower bounds on the size of designs in compact symmetric spaces of rank 1

The concept of t-designs in compact symmetric spaces of rank 1 is a generalization of the theory of classical t-designs. In this paper we obtain new lower bounds on the cardinality of designs in projective compact symmetric spaces of rank 1. With one exception our bounds are the first improvements of the classical bounds by more than one. We use the linear programming technique and follow the approach we have proposed for spherical codes and designs. Some examples are shown and compared with the classical bounds.     

Incidence matrices of t-designs

We point out a generalization of the matrix equation NN^T=(r? λ)I+λJ to t-designs with t>2 and derive extensions of Fisher's, Connor's, and Mann's inequalities for block designs.     

Quasi-symmetric 2-(31, 7, 7) designs and a revision of Hamada's conjecture

It is proved by use of the classification of the doubly even (32, 16) codes, that in addition to the design formed by the planes in PG(4, 2), there are exactly four other nonisomorphic quasi-symmetric 2-(31, 7, 7) designs, and they all have 2-rank 16. This shows that the “only if” part of the following conjecture due to Hamada, is not true in general: “If N(D) is an incidence matrix of a design D with the parameters of a design G defined by the flats of a given dimension in PG(t, q) or AG(t, q), then rank_q N(D) ⩾ rank_q N(G), with equality if and only if D is isomorphic with G.” The five quasi-symmetric 2-(31, 7, 7) designs are extendable to nonisomorphic 3-(32, 8, 7) designs having 2-rank 16, one of which is formed by the 3-flats in AG(5, 2), thus the designs arising from a finite affine geometry also are not characterized by their ranks in general. A quasi-symmetric 2-(45, 9, 8) design yielding a pseudo-geometric strongly regular graph with parameters (r, k, t) = (15, 10, 6) is also constructed on the base of the known extremal doubly even (48, 24) code.     

Nonexistence of nontrivial tight 8-designs

Tight t-designs are t-designs whose sizes achieve the Fisher type lower bound. We give a new necessary condition for the existence of nontrivial tight designs and then use it to show that there do not exist nontrivial tight 8-designs.