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.     

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.     

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).     

Resolvable balanced bipartite designs

A block B denotes a set of k = k₁ + k₂ elements which are divided into two subsets, B¹ and B², where ∣Bⁱ∣ = k_i, i = 1 or 2. Two elements are said to be linked in B if and only if they belong to different subsets of B. A balanced bipartite design, BBD(v, k₁, k₂, λ), is an arrangement of v elements into b blocks, each containing k elements such that each element occurs in exactly r blocks and any two distinct elements are linked in exactly λ blocks. A resolvable balanced bipartite design, RBBD(v, k₁, k₂, λ), is a BBD(v, k₁, k₂, λ), the b blocks of which can be divided into r sets which are called complete replications, such that each complete replication contains all the v elements of the design.Necessary conditions for the existence of RBBD(v, 1, k₂, λ) and RBBD(v, n, n, λ) are obtained and it is shown that some of the conditions are also sufficient. In particular, necessary and sufficient conditions for the existence of RBBD(v, 1, k₂, λ), where k₂ is odd or equal to two, and of RBBD(v, n, n, λ), where n is even and 2n ? 1 is a prime power, are given.     

A direct method to construct triple systems

A triple system is a balanced incomplete block design D(v, k, λ, b, r) with k = 3. Although it has been shown that triple systems exist for all values of the parameters satisfying the necessary conditions:

$\text{λ(ν ? 1) ≡ 0 (}\text{mod 2}\text{), λν(ν ? 1) ≡ 0 (}\text{mod 6}\text{),}$

direct methods (nonrecursive) of construction are not available in general. In this paper we give a direct method to construct a triple system for all values of the parameters satisfying the necessary conditions.     

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     

Some paranormed sequence spaces of non-absolute type derived by weighted mean

The sequence spaces ?_∞(p), c(p) and c₀(p) were introduced and studied by Maddox [I.J. Maddox, Paranormed sequence spaces generated by infinite matrices, Proc. Cambridge Philos. Soc. 64 (1968) 335-340]. In the present paper, the sequence spaces λ(u,v;p) of non-absolute type which are derived by the generalized weighted mean are defined and proved that the spaces λ(u,v;p) and λ(p) are linearly isomorphic, where λ denotes the one of the sequence spaces ?_∞, c or c₀. Besides this, the β- and γ-duals of the spaces λ(u,v;p) are computed and the basis of the spaces c₀(u,v;p) and c(u,v;p) is constructed. Additionally, it is established that the sequence space c₀(u,v) has AD property and given the f-dual of the space c₀(u,v;p). Finally, the matrix mappings from the sequence spaces λ(u,v;p) to the sequence space μ and from the sequence space μ to the sequence spaces λ(u,v;p) are characterized.     

EXISTENCE OF OPTIMAL STRONG PARTIALLY BALANCED DESIGNS

A strong partially balanced design SPBD（v, b, k; λ,0） whose b is the maximum number of blocks in all SPBD（v, b, k; λ, 0）, as an optimal strong partially balanced design, briefly OSPBD（v, k, λ） is studied. In investigation of authentication codes it has been found that the strong partially balanced design can be used to construct authentication codes. This note investigates the existence of optimal strong partially balanced design OSPBD（v, k, 1） for k = 3 and 4, and shows that there exists an OSPBD（v, k, 1） for any v ≥ k.     

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.     

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.     

Spreads, arcs, and multiple wavelength codes

We present several new families of multiple wavelength (2-dimensional) optical orthogonal codes (2D-OOCs) with ideal auto-correlation λ_a=0 (codes with at most one pulse per wavelength). We also provide a construction which yields multiple weight codes. All of our constructions produce codes that are either optimal with respect to the Johnson bound (J-optimal), or are asymptotically optimal and maximal. The constructions are based on certain pointsets in finite projective spaces of dimension k over GF(q) denoted PG(k,q).     

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.     

Optimum super-simple mixed covering arrays of type <Emphasis Type="Italic">a</Emphasis><Superscript>1</Superscript><Emphasis Type="Italic">b</Emphasis><Superscript><Emphasis Type="Italic">k</Emphasis>−1</Superscript>

A mixed covering array (MCA) of type (_v 1, v ₂,..., v _k ), denoted by MCA_λ (N; t, k, (v ₁, v ₂,..., v _k )), is an N × k array with entries in the i-th column from a set _{V i} of v _i symbols and has the property that each N × t sub-array covers all the t-tuples at least λ times, where 1 ≤ i ≤ k. An MCA _λ (N; t, k, (_v 1, v ₂,..., v _k )) is said to be super-simple, if each of its N × (t + 1) sub-arrays contains each (t + 1)-tuple at most once. Recently, it was proved by Tang, Yin and the author that an optimum super-simple MCA of type (a, b, b,..., b) is equivalent to a mixed detecting array (DTA) of type (a, b, b,..., b) with optimum size. Such DTAs can be used to generate test suites to identify and determine the interaction faults between the factors in a component-based system. In this paper, some combinatorial constructions of optimum super-simple MCAs of type (a, b, b,..., b) are provided. By employing these constructions, some optimum super-simple MCAs are then obtained. In particular, the spectrum across which optimum super-simple MCA₂(2b ²; 2, 4, (a, b, b, b))′s exist, is completely determined, where 2 ≤ a ≤ b.     

On counting Sperner families

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

Neighbor designs

A neighbor design is an arrangement of r copies of each of v varieties into b circular blocks of size k > 1 such that neighboring objects in each block are distinct and every pair of distinct varieties appears as neighbors in the set of circular blocks exactly λ times. Necessary conditions for the existence of a neighbor design with these parameters v, k, λ, r, b are that $\text{r =}\text{λ(v ? 1)}\text{2}$, and $\text{b =}\text{λv(v ? 1)}\text{2k}$ be integers for k > 2 and v > 2; and for k = 2 or v = 2, it is also necessary that λ be even or k be even, respectively. In this paper we show that these necessary conditions are also sufficient by giving a method to construct a neighbor design for all values of the parameters satisfying the necessary conditions.     

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     

On the uniqueness of embedding a residual design

We prove that if a residual $\text{2-(k(k+λ?1)}\text{λ,k,λ)}$ design R has more than one embedding into a symmetric design then k ? λ(λ?1)². If equality holds then R has exactly two embeddings and the corresponding derived design is in both cases λ ? 1 identical copies of the design of points and lines of PG(3, λ ? 1). Using the main proposition from which these results follow we also prove that if a symmetric2-(v,k, λ) design has an axial non-central or central non-axial automorphism then k?λ(λ² ? 2λ + 2).     

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.     

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.     

Covering the alternating groups by products of cycle classes

Given integers k,l?2, where either l is odd or k is even, we denote by n=n(k,l) the largest integer such that each element of An is a product of k cycles of length l. For an odd l, k is the diameter of the undirected Cayley graph Cay(An,Cl), where Cl is the set of all l-cycles in An. We prove that if k?2 and l?9 is odd and divisible by 3, then . This extends earlier results by Bertram [E. Bertram, Even permutations as a product of two conjugate cycles, J. Combin. Theory 12 (1972) 368-380] and Bertram and Herzog [E. Bertram, M. Herzog, Powers of cycle-classes in symmetric groups, J. Combin. Theory Ser. A 94 (2001) 87-99].