A few more large sets of t-designs

We construct several new large sets of t-designs that are invariant under Frobenius groups, and discuss their consequences. These large sets give rise to further new large sets by means of known recursive constructions including an infinite family of large sets of 3 − (v, 4, λ) designs. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 293–308, 1998     

An Assmus–Mattson-Type Approach for Identifying 3-Designs from Linear Codes over Z 4

The complete weight enumerator of the Delsarte–Goethals code over Z ₄ is derived and an Assmus–Mattson-type approach at identifying t-designs in linear codes over Z ₄ is presented. The Assmus–Mattson-type approach, in conjunction with the complete weight enumerator are together used to show that the codewords of constant Hamming weight in both the Goethals code over Z ₄ as well as the Delsarte–Goethals code over Z ₄ yield 3-designs, possibly with repeated blocks.     

On the Existence of Large Sets of <Emphasis Type="Italic">t</Emphasis>-designs of Prime Sizes

In this paper, we employ the known recursive construction methods to obtain some new existence results for large sets of t-designs of prime sizes. We also present a new recursive construction which leads to more comprehensive theorems on large sets of sizes two and three. As an application, we show that for infinitely many values of block size, the trivial necessary conditions for the existence of large sets of 2-designs of size three are sufficient.AMS Classification: 05B05Communicated by:L. TeirlinckThis research was in part supported by a grant from IPM (No. 83050312).     

McLaren’s improved snub cube and other new spherical designs in three dimensions

Evidence is presented to suggest that, in three dimensions, spherical 6-designs withN points exist forN=24, 26,≥28; 7-designs forN=24, 30, 32, 34,≥36; 8-designs forN=36, 40, 42,≥44; 9-designs forN=48, 50, 52,≥54; 10-designs forN=60, 62, ≥64; 11-designs forN=70, 72,≥74; and 12-designs forN=84,≥86. The existence of some of these designs is established analytically, while others are given by very accurate numerical coordinates. The 24-point 7-design was first found by McLaren in 1963, and—although not identified as such by McLaren—consists of the vertices of an “improved” snub cube, obtained from Archimedes' regular snub cube (which is only a 3-design) by slightly shrinking each square face and expanding each triangular face. 5-designs with 23 and 25 points are presented which, taken together with earlier work of Reznick, show that 5 designs exist forN=12, 16, 18, 20,≥22. It is conjectured, albeit with decreasing confidence fort≥9, that these lists oft-designs are complete and that no other exist. One of the constructions gives a sequence of putative sphericalt-designs withN=12m points (m≥2) whereN=1/2t ²(1+o(1)) ast→∞.     

A problem of combinatorial designs related to authentication codes

The strong partially balanced t-designs can be used to construct authentication codes, whose probabilities P_r of successful deception in an optimum spoofing attack of order r for r = 0, 1, …, t − 1, achieve their information-theoretic lower bounds. In this paper a new family of strong partially balanced t-designs are constructed by means of rational normal curves over finite fields. Thus based on this new partially balanced t-designs a new class of authentication codes is obtained. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 417–429, 1998     

Systematic Construction of <Emphasis Type="Italic">q</Emphasis>-Analogs of <Emphasis Type="Italic">t</Emphasis>−(<Emphasis Type="Italic">v</Emphasis>,<Emphasis Type="Italic">k</Emphasis>,λ)-Designs

In the present paper we consider a q-analog of t–(v,k,)-designs. It is canonic since it arises by replacing sets by vector spaces over GF(q), and their orders by dimensions. These generalizations were introduced by Thomas [Geom.Dedicata vol. 63, pp. 247–253 (1996)] they are called t –(v,k,;q)- designs. A few of such q-analogs are known today, they were constructed using sophisticated geometric arguments and case-by-case methods. It is our aim now to present a general method that allows systematically to construct such designs, and to give complete catalogs (for small parameters, of course) using an implemented software package. &nbsp; In order to attack the (highly complex) construction, we prepare them for an enormous data reduction by embedding their definition into the theory of group actions on posets, so that we can derive and use a generalization of the Kramer-Mesner matrix for their definition, together with an improved version of the LLL-algorithm. By doing so we generalize the methods developed in a research project on t –(v,k,)-designs on sets, obtaining this way new results on the existence of t–(v,k,;q)-designs on spaces for further quintuples (t,v,k,;q) of parameters. We present several 2–(6,3,;2)-designs, 2–(7,3,;2)-designs and, as far as we know, the very first 3-designs over GF(q).classification 05B05     

Constructions of Spherical 3-Designs

 Spherical t-designs are Chebyshev-type averaging sets on the d-sphere which are exact for polynomials of degree at most t. This concept was introduced in 1977 by Delsarte, Goethals, and Seidel, who also found the minimum possible size of such designs, in particular, that the number of points in a 3-design on S ^d must be at least . In this paper we give explicit constructions for spherical 3-designs on S ^d consisting of n points for d=1 and ; d=2 and ; d=3 and ; d=4 and ; and odd or even. We also provide some evidence that 3-designs of other sizes do not exist. We will introduce and apply a concept from additive number theory generalizing the classical Sidon-sequences. Namely, we study sets of integers S for which the congruence mod n, where and , only holds in the trivial cases. We call such sets Sidon-type sets of strength t, and denote their maximum cardinality by s(n, t). We find a lower bound for s(n, 3), and show how Sidon-type sets of strength 3 can be used to construct spherical 3-designs. We also conjecture that our lower bound gives the true value of s(n, 3) (this has been verified for n≤125). Received: June 19, 1996     

Undetected error probability of q-ary constant weight codes

In this paper, we introduce a new combinatorial invariant called q-binomial moment for q-ary constant weight codes. We derive a lower bound on the q-binomial moments and introduce a new combinatorial structure called generalized (s, t)-designs which could achieve the lower bounds. Moreover, we employ the q-binomial moments to study the undetected error probability of q-ary constant weight codes. A lower bound on the undetected error probability for q-ary constant weight codes is obtained. This lower bound extends and unifies the related results of Abdel-Ghaffar for q-ary codes and Xia-Fu-Ling for binary constant weight codes. Finally, some q-ary constant weight codes which achieve the lower bounds are found.      

A census of highly symmetric combinatorial designs

As a consequence of the classification of the finite simple groups, it has been possible in recent years to characterize Steiner t-designs, that is t-(v,k,1) designs, mainly for t=2, admitting groups of automorphisms with sufficiently strong symmetry properties. However, despite the finite simple group classification, for Steiner t-designs with t>2 most of these characterizations have remained long-standing challenging problems. Especially, the determination of all flag-transitive Steiner t-designs with 3≤t≤6 is of particular interest and has been open for about 40 years (cf. Delandtsheer (Geom. Dedicata 41, p. 147, 1992 and Handbook of Incidence Geometry, Elsevier Science, Amsterdam, 1995, p. 273), but presumably dating back to 1965). The present paper continues the author’s work (see Huber (J. Comb. Theory Ser. A 94, 180–190, 2001; Adv. Geom. 5, 195–221, 2005; J. Algebr. Comb., 2007, to appear)) of classifying all flag-transitive Steiner 3-designs and 4-designs. We give a complete classification of all flag-transitive Steiner 5-designs and prove furthermore that there are no non-trivial flag-transitive Steiner 6-designs. Both results rely on the classification of the finite 3-homogeneous permutation groups. Moreover, we survey some of the most general results on highly symmetric Steiner t-designs.      

Ring-Valued Assignments to the Points of a t-Design

We introduce the method of assigning values in a ring to the points of a t-design. We give the notion of an -design. We give a generalization of the concept of association scheme, and obtain a method to construct some of them from t-designs that generalizes the well-known construction for the case of ordinary association schemes.     

Trades and Graphs

The trade spectrum of a simple graph G is defined to be the set of all t for which it is possible to assemble together t copies of G into a simple graph H, and then disassemble H into t entirely different copies of G. Trade spectra of graphs have applications to intersection problems, and defining sets, of G-designs. In this investigation, we give several constructions, both for specific families of graphs, and for graphs in general. Received: October 3, 1997 Final version received: May 7, 1999     

On the structure of 1-designs with at most two block intersection numbers

We introduce the notion of an unrefinable decomposition of a 1-design with at most two block intersection numbers, which is a certain decomposition of the 1-designs collection of blocks into other 1-designs. We discover an infinite family of 1-designs with at most two block intersection numbers that each have a unique unrefinable decomposition, and we give a polynomial-time algorithm to compute an unrefinable decomposition for each such design from the family. Combinatorial designs from this family include: finite projective planes of order n; SOMAs, and more generally, partial linear spaces of order (s, t) on (s + 1)² points; as well as affine designs, and more generally, strongly resolvable designs with no repeated blocks.      

Optimal constant weight covering codes and nonuniform group divisible 3-designs with block size four

Let K _q (n, w, t, d) be the minimum size of a code over Z _q of length n, constant weight w, such that every word with weight t is within Hamming distance d of at least one codeword. In this article, we determine K _q (n, 4, 3, 1) for all n ≥ 4, q = 3, 4 or q = 2 ^m  + 1 with m ≥ 2, leaving the only case (q, n) = (3, 5) in doubt. Our construction method is mainly based on the auxiliary designs, H-frames, which play a crucial role in the recursive constructions of group divisible 3-designs similar to that of candelabra systems in the constructions of 3-wise balanced designs. As an application of this approach, several new infinite classes of nonuniform group divisible 3-designs with block size four are also constructed.     

Cyclotomic Conditions Leading to New Steiner 2-Designs

We improve the constructions of S. Bagchi and B. Bagchi for Steiner 2-designs which are point-regular over the additive group of a Galois ring. As a consequence, we get new cyclotomic conditions leading to point-regular Steiner 2-designs with block sizek {7, 9, 11, 13, 17}.     

Completely Regular Designs of Strength One

We study a class of highly regular t-designs. These are the subsets of vertices of the Johnson graph which are completely regular in the sense of Delsarte [2]. In [9], Meyerowitz classified the completely regular designs having strength zero. In this paper, we determine the completely regular designs having strength one and minimum distance at least two. The approach taken here utilizes the incidence matrix of (t+1)-sets versus k-sets and is related to the representation theory of distance-regular graphs [1, 5].     

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.     

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 new class of 3-fold perfect splitting authentication codes

Restricted strong partially balanced t-designs were first formulated by Pei, Li, Wang and Safavi-Naini in investigation of authentication codes with arbitration. In this article, we will prove that splitting authentication codes that are multi-fold perfect against spoofing can be characterized in terms of restricted strong partially balanced t-designs. We will also investigate the existence of restricted strong partially balanced 3-designs RSPBD 3-(v, b, 3 × 2; λ₁, λ₂, 1, 0)s, and show that there exists an RSPBD 3-(v, b, 3 × 2; λ₁, λ₂, 1, 0) for any v o 9 (mod 16){v\equiv 9\ (\mbox{{\rm mod}}\ 16)} . As its application, we obtain a new infinite class of 3-fold perfect splitting authentication codes.     

Relative <Emphasis Type="Italic">t</Emphasis>-designs in binary Hamming association scheme <Emphasis Type="Italic">H</Emphasis>(<Emphasis Type="Italic">n</Emphasis>, 2)

A relative t-design in the binary Hamming association schemes H(n, 2) is equivalent to a weighted regular t-wise balanced design, i.e., certain combinatorial t-design which allows different sizes of blocks and a weight function on blocks. In this paper, we study relative t-designs in H(n, 2), putting emphasis on Fisher type inequalities and the existence of tight relative t-designs. We mostly consider relative t-designs on two shells. We prove that if the weight function is constant on each shell of a relative t-design on two shells then the subset in each shell must be a combinatorial \((t-1)\)-design. This is a generalization of the result of Kageyama who proved this under the stronger assumption that the weight function is constant on the whole block set. Using this, we define tight relative t-designs for odd t, and a strong restriction on the possible parameters of tight relative t-designs in H(n, 2). We obtain a new family of such tight relative t-designs, which were unnoticed before. We will give a list of feasible parameters of such relative 3-designs with \(n \le 100\), and then we discuss the existence and/or the non-existence of such tight relative 3-designs. We also discuss feasible parameters of tight relative 4-designs on two shells in H(n, 2) with \(n \le 50\). In this study we come up with the connection on the topics of classical design theory, such as symmetric 2-designs (in particular 2-\((4u-1,2u-1,u-1)\) Hadamard designs) and Driessen’s result on the non-existence of certain 3-designs. We believe Problems 1 and 2 presented in Sect. 5.2 open a new way to study relative t-designs in H(n, 2). We conclude our paper listing several open problems.     

Semiregular Large Sets

We develop the notion of t-homogeneous, G-semiregular large sets of t-designs, show that there are infinitely many 3-homogeneous PSL(2, q)-semiregular large sets when q 3 mod 4, two sporadic 3-homogeneous AL(1,32)-semiregular large sets, and no other interesting t-homogeneous G-semiregular large sets for t 3.