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 the Cameron-Praeger conjecture

This paper takes a significant step towards confirming a long-standing and far-reaching conjecture of Peter J. Cameron and Cheryl E. Praeger. They conjectured in 1993 that there are no non-trivial block-transitive 6-designs. We prove that the Cameron-Praeger conjecture is true for the important case of non-trivial Steiner 6-designs, i.e. for 6-(v,k,λ) designs with λ=1, except possibly when the group is PΓL(2,pe) with p=2 or 3, and e is an odd prime power.     

A few more Kirkman squares and doubly near resolvable BIBDs with block size 3

A Kirkman square with index λ, latinicity μ, block size k, and v points, KS_k(v;μ,λ), is a t×t array (t=λ(v-1)/μ(k-1)) defined on a v-set V such that (1) every point of V is contained in precisely μ cells of each row and column, (2) each cell of the array is either empty or contains a k-subset of V, and (3) the collection of blocks obtained from the non-empty cells of the array is a (v,k,λ)-BIBD. In a series of papers, Lamken established the existence of the following designs: KS₃(v;1,2) with at most six possible exceptions [E.R. Lamken, The existence of doubly resolvable (v,3,2)-BIBDs, J. Combin. Theory Ser. A 72 (1995) 50-76], KS₃(v;2,4) with two possible exceptions [E.R. Lamken, The existence of KS₃(v;2,4)s, Discrete Math. 186 (1998) 195-216], and doubly near resolvable (v,3,2)-BIBDs with at most eight possible exceptions [E.R. Lamken, The existence of doubly near resolvable (v,3,2)-BIBDs, J. Combin. Designs 2 (1994) 427-440]. In this paper, we construct designs for all of the open cases and complete the spectrum for these three types of designs. In addition, Colbourn, Lamken, Ling, and Mills established the spectrum of KS₃(v;1,1) in 2002 with 23 possible exceptions. We construct designs for 11 of the 23 open cases.     

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.     

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.     

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.     

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 counting Sperner families

It is proved that balanced 3-designs B₃[k, λ, v] exist for k = 5, λ = 30 and every v ? 5.     

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     

A graph isomorphism algorithm using pseudoinverses

For a graph ofm nodes andn edges, an algorithm for testing the isomorphism of graphs is given. The complexity of the algorithm is a maximum ofO(mn ²) in almost all cases, with a considerable reduction if sparsity is exploited. If isomorphism is present, the pseudoinverses of the Laplace matrices of the graphs will be row and column permutations of each other. Advantage can be taken of certain features of the incidence matrices or of properties of the graphs to reduce computation time.     

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.     

Partitioning the planes of AG2m(2) into 2-designs

A t-design S_λ(t, k, v) is an arrangement of v elements in blocks of k elements each such that every t element subset is contained in exactly λ blocks. A t-design S_λ(t, k, v) is called t′-resolvable if the blocks can be partitioned into families such that each family is the block system of a S_λ(t′, k, v). It is shown that the S₁(3, 4, 2^2m) design of planes on an even dimensional affine space over the field of two elements is 2-resolvable. Each S₁(2, 4, 2^2m) given by the resolution is itself 1-resolvable. As a corollary it is shown that every odd dimensional projective space over the field of two elements admits a 1-packing of 1-spreads, i.e. a partition of its lines into families of mutually disjoint lines whose union covers the space. This 1-packing may be generated from any one of its spreads by repeated application of a fixed collineation.     

An existence theory for pairwise balanced designs,III: Proof of the existence conjectures

Given positive integers k and λ, balanced incomplete block designs on v points with block size k and index λ exist for all sufficiently large integers v satisfying the congruences λ(v ? 1) ≡ 0 (mod k ? 1) and λv(v ? 1) ≡ 0 (mod k(k ? 1)). Analogous results hold for pairwise balanced designs where the block sizes come from a given set K of positive integers. We also observe that the number of nonisomorphic designs on v points with given block size k > 2 and index λ tends to infinity as v increases (subject to the above congruences).     

An enumeration of graphical designs

Let Ψ(t,k) denote the set of pairs (v,λ) for which there exists a graphical t‐(v,k,λ) design. Most results on graphical designs have gone to show the finiteness of Ψ(t,k) when t and k satisfy certain conditions. The exact determination of Ψ(t,k) for specified t and k is a hard problem and only Ψ(2,3), Ψ(2,4), Ψ(3,4), Ψ(4,5), and Ψ(5,6) have been determined. In this article, we determine completely the sets Ψ(2,5) and Ψ(3,5). As a result, we find more than 270,000 inequivalent graphical designs, and more than 8,000 new parameter sets for which there exists a graphical design. Prior to this, graphical designs are known for only 574 parameter sets. © 2006 Wiley Periodicals, Inc. J Combin Designs 16: 70–85, 2008     

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.     

Decomposition of λK v into five graphs with six vertices and eight edges

In this paper, we discuss the G-decomposition of ??K _v (G-GD _?? (v)) into five graphs with six vertices and eight edges. We present some recursive structures and a number of G-designs of small orders, holey Gdesigns, and incomplete G-designs are constructed. Finally, the spectrum of the existence of G-GD _?? (v) is determined.     

Parameter dependence of stable manifolds under nonuniform hyperbolicity

For a nonautonomous linear equation v^′=A(t)v in a Banach space with a nonuniform exponential dichotomy, we show that the nonlinear equation v^′=A(t)v+f(t,v,λ) has stable invariant manifolds Vλ which are Lipschitz in the parameter λ provided that f is a sufficiently small Lipschitz perturbation. Since any linear equation with nonzero Lyapunov exponents has a nonuniform exponential dichotomy, the above assumption is very general. We emphasize that passing from a classical uniform exponential dichotomy to a general nonuniform exponential dichotomy requires a substantially new approach.     

Reconstructing edge-disjoint paths

For an undirected graph G=(V,E), the edge connectivity values between every pair of nodes of G can be succinctly recorded in a flow-equivalent tree that contains the edge connectivity value for a linear number of pairs of nodes. We generalize this result to show how we can efficiently recover a maximum set of disjoint paths between any pair of nodes of G by storing such sets for a linear number of pairs of nodes. At the heart of our result is an observation that combining two flow solutions of the same value, one between nodes s and r and the second between nodes r and t, into a feasible flow solution of value f between nodes s and t, is equivalent to solving a stable matching problem on a bipartite multigraph.Our observation, combined with an observation of Chazelle, leads to a data structure, which takes O(n^3.5) time to generate, that can construct the maximum number λ(u,v) of edge-disjoint paths between any pair (u,v) of nodes in time O(α(n,n)λ(u,v)n) time.     

Characterizing geometric designs, II

We provide a characterization of the classical point-line designs PG₁(n,q), where n?3, among all non-symmetric 2-(v,k,1)-designs as those with the maximal number of hyperplanes. As an application of this result, we characterize the classical quasi-symmetric designs PGn−2(n,q), where n?4, among all (not necessarily quasi-symmetric) designs with the same parameters as those having line size q+1 and all intersection numbers at least qn−4+?+q+1. Finally, we also give an explicit lower bound for the number of non-isomorphic designs having the same parameters as PG₁(n,q); in particular, we obtain a new proof for the known fact that this number grows exponentially for any fixed value of q.