Search

The theory of cyclotomy dates back to Gauss and has a number of applications in combinatorics, coding theory, and cryptography. Cyclotomy over a residue class ring \BBZv can be divided into classical cyclotomy or generalized cyclotomy, depending on v prime or composite. In this paper, we introduce a generalized cyclotomy of order d over \BBZp1^{e1p2^{e2},\ldots, pn^{en}}, which includes Whiteman's and Ding-Helleseth's generalized cyclotomy as special cases. Here, p1,p2,\ldots,pn are pairwise distinct odd primes satisfying d\vert (pi-1) for all 1\leq i\leq n and e1,e2,\ldots,en are positive integers. We derive some basic properties of the corresponding cyclotomic numbers and obtain a general formula to compute them via classical cyclotomic numbers. As applications, we completely solve an open problem and a conjecture on Whiteman's generalized cyclotomy of order four over \BBZp1p2. Besides, we also construct an infinite series of near-optimal codebooks over \BBZp1p2, as well as some infinite series of asymptotically optimal difference systems of sets over \BBZp1^{e1p2^{e2},\ldots,pn^{en}}. [ABSTRACT FROM AUTHOR]

Abstract: A group divisible design (GDD) with three groups and block size 4 is called even, odd, or mixed if the sizes of the non-empty intersections of any of its blocks with any of the three groups are always even, always odd, or always mixed. It has been shown that the necessary conditions for the existence of GDDs of these three types are also sufficient except possibly for the minimal case of mixed designs for group size (). In this paper, we complete the undetermined families of mixed GDDs using two constructions based on idempotent self-orthogonal Latin squares and skew Room squares. [Copyright &y& Elsevier]

Motivated by applications in combinatorial group testing for consecutive positives, we investigate a block sequence of a maximum packing MP(t, k, v) which contains the blocks exactly once such that the collection of all blocks together with all unions of two consecutive blocks of this sequence forms an error correcting code with minimum distance d. Such a sequence is usually called a block sequence with consecutive unions having minimum distance d, and denoted by BSCU(t, k, v∣d). In this paper, we show that the necessary conditions for the existence of BSCU(3, 4, v∣4)s of Steiner quadruple systems, namely, v Ξ 2,4 (mod 6) and v ≥ 4, are also sufficient, excepting v = 8, 10. [ABSTRACT FROM AUTHOR]

For a v-set V , let A be a collection of r × c arrays with elements in V. A pair (V,A) is called an r × c grid-block design if every two distinct elements i and j in V occur exactly once in the same row or in the same column of an array in A. This design originated from the use of DNA library screening. In this paper, we show the existence of r × 4 grid-block designs with r = 3, 4. We settle completely for the case of r = 4 and almost completely for the case of r = 3, leaving 15 orders undetermined. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we investigate the existence of resolvable group divisible designs (RGDDs) with block size four, group-type and general index . The necessary conditions for the existence of such a design are , and . These necessary conditions are shown to be sufficient for all , with the definite exceptions of . The known existence result for is also improved. [Copyright &y& Elsevier]

We show that if G is a finite Abelian group and the block size is 3, then the necessary conditions for the existence of a ( v,3,λ; G) GBRD are sufficient. These necessary conditions include the usual necessary conditions for the existence of the associated ( v,3,λ) BIBD plus λ≡ 0 (mod| G|), plus some extra conditions when | G| is even, namely that the number of blocks be divisible by 4 and, if v = 3 and the Sylow 2-subgroup of G is cyclic, then also λ≡ 0 (mod2| G|). [ABSTRACT FROM AUTHOR]

Abstract: Frames are useful in dealing with resolvable designs such as resolvable balanced incomplete block designs and triplewhist tournaments. Z-cyclic triplewhist tournament frames are also useful in the constructions of Z-cyclic triplewhist tournaments. In this paper, the concept of an -regular Z-cyclic triplewhist tournament frame is defined, and used to establish several quite general recursive constructions for Z-cyclic triplewhist tournaments. As corollaries, we are able to unify many known constructions for Z-cyclic triplewhist tournaments. As an application, some new Z-cyclic triplewhist tournament frames and Z-cyclic triplewhist tournaments are obtained. The known existence results of such designs are then extended. [Copyright &y& Elsevier]

Abstract: Frequency-hopping multiple-access (FHMA) spread-spectrum communication systems employing multiple frequency shift keying as data modulation technique were investigated by Fuji-Hara, Miao and Mishima [R. Fuji-Hara, Y. Miao, M. Mishima, Optimal frequency hopping sequences: A combinatorial approach, IEEE Trans. Inform. Theory 50 (2004) 2408–2420] from a combinatorial approach, where a correspondence between frequency-hopping (FH) sequences and partition-type cyclic difference packings was established, and several combinatorial constructions were provided for FHMA systems with a single optimal FH sequence. In this paper, by means of this correspondence, we describe more combinatorial constructions for such optimal FH sequences. As a consequence, more new infinite series of optimal FH sequences are obtained. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate the existence of resolvable group divisible designs (RGDDs) with block size four, group-type and index three. The necessary conditions for the existence of such a design are and . These necessary conditions are shown to be sufficient except for and possibly excepting . [Copyright &y& Elsevier]

In this paper, we present a systematic approach to some new direct constructions of block designs. Several examples of non-uniform group divisible designs, resolvable group divisible designs and optimal packings are illustrated to show the advantage of the construction method. [Copyright &y& Elsevier]

As a crucial technique for integrated circuits (IC) test response compaction, X-compact employs a special kind of codes called X-codes for reliable compressions of the test response in the presence of unknown logic values (Xs). From a combinatorial view point, Fujiwara and Colbourn introduced an equivalent definition of X-codes and studied X-codes of small weights that have good detectability and X-tolerance. An $({\it\text { m, n, d, x}})~\text {X}$ -code is an $\text {m}\times \text {n}$ binary matrix with column vectors as its codewords. The parameters ${\it\text { d, x}}$ correspond to the test quality of the code. In this paper, bounds and constructions for constant weighted X-codes are investigated. First, we obtain a general result on the maximum number of codewords n for an $({\it\text { m, n, d, x}})~\text {X}$ -code of weight w, and we further improve this lower bound for the case with $\text {x}=2$ and $\text {w}=3$ through the probabilistic method. Then, using tools from additive combinatorics and finite fields, we present some explicit constructions for constant weighted X-codes with $\text {d}=3,7$ and $\text {x}=2$ , which are optimal for the case when $\text {d}=3, \text {w}=4$ and nearly optimal for the case when $\text {d}=3,\text {w}=3$. We also consider a special class of X-codes introduced by Fujiwara and Colbourn and improve the best known lower bound on the maximum number of codewords for this kind of X-codes. [ABSTRACT FROM AUTHOR]

Frameproof codes are used to fingerprint digital data. They can prevent copyrighted materials from unauthorized use. In this paper, we study upper and lower bounds for $w$ -frameproof codes of length N$ over an alphabet of size q$ . The upper bound is based on a combinatorial approach and the lower bound is based on a probabilistic construction. Both bounds can improve one of the previous results when q$ is small compared with w$ , say cq\leq w$ for some constant c\leq q$ . Furthermore, we pay special attention to binary frameproof codes. We show a binary w . [ABSTRACT FROM PUBLISHER]

Various kinds of secure codes and their related hash families are broadly studied combinatorial structures for protecting copyrighted materials. The codewords in such a structure can be regarded as a subset of Q^N , the set of all $q$ -ary vectors of given length $N$ , satisfying some constraints. We use a hypergraph model to characterize the combinatorial structure. By applying a result of Duke et al. on the lower bound of the independence number of hypergraphs, we provide a new approach to evaluate the lower bounds for several kinds of secure codes and related hash families. In particular, the general method is illustrated via the examples of existence results on some perfect hash families, frameproof codes, and separable codes. [ABSTRACT FROM PUBLISHER]

In this paper, we investigate the existence of pairwise balanced designs on v points having blocks of size five, with a distinguished block of size w, briefly (v,{5,w*},1)-PBDs. The necessary conditions for the existence of a (v,{5,w*},1)-PBD with a distinguished block of size w are that v⩾4w+1, v≡w≡1 (mod 4) and either v≡w (mod 20) or v+w≡6 (mod 20). Previously, w⩽33 has been studied, and the necessary conditions are known to be sufficient for w=1, 5, 13 and 21, with 8 possible exceptions when w⩽33. In this article, we eliminate 3 of these possible exceptions, showing sufficiency for w=25 and 33. Our main objective is the study of 37⩽w⩽97, where we establish sufficiency for w=73, 81, 85 and 93, with 67 possible exceptions with 37⩽w⩽97. For w≡13 (mod 20), we show that the necessary existence conditions are sufficient except possibly for w=53,133,293 and 453. For w≡1,5 (mod 20), we show the necessary existence conditions are sufficient for w⩾1281,1505, and for w≡9,17 (mod 20), we show that w⩾2029,2477 is sufficient with one possible exceptional series, namely v=4w+9 when w≡17 (mod 20). We know of no example where v=4w+9. In this article, we also study the 4-RBIBD embedding problem for small subdesigns (up to 52 points) and update some results of Bennett et al. on PBDs containing a 5-line. As an application of our results for w=33 and 97, we establish the smallest number of blocks in a pair covering design with k=5 when v≡1 (mod 4) with 37 open cases, the largest being for v=489; hitherto, there were 104 open cases, the largest being v=2249. [Copyright &y& Elsevier]

For given positive integers t ≤ s , what is the maximum number of t -by- t invertible submatrices in an invertible binary matrix of order s ? This purely combinatorial problem is posedrecently by D’Arco, Esfahani and Stinson. The motivation is related to all-or-nothing transforms (AONTs) suggested by Rivest as a preprocessing for encrypting data with a block cipher, which has been widely applied in cryptography and security. For the case t = 2 , let R 2 ( s ) denote the maximal proportion of 2-by-2 invertible submatrices of s -by- s invertible matrices. D’Arco, Esfahani and Stinson ask whether lim s → ∞ R 2 ( s ) exists or not. If it does exist, then their results indicate that the limit is between 0.494 and 0.625. In this paper we completely solve the problem by showing that lim s → ∞ R 2 ( s ) = 0 . 5 . [ABSTRACT FROM AUTHOR]