Storage architectures ranging from minimum bandwidth regenerating encoded distributed storage systems to declustered-parity RAIDs can employ dense partial Steiner systems to support fast reads, writes, and recovery of failed storage units. To enhance performance, popularities of the data items should be taken into account to make frequencies of accesses to storage units as uniform as possible. A combinatorial model ranks items by popularity and assigns data items to elements in a dense partial Steiner system so that the sums of ranks of the elements in each block are as equal as possible. By developing necessary conditions in terms of independent sets, we demonstrate that certain Steiner systems must have a much larger difference between the largest and smallest block sums than is dictated by an elementary lower bound. In contrast, we also show that certain dense partial \(S(t,t+1,v)\) designs can be labeled to realize the elementary lower bound. Furthermore, we prove that for every admissible order v , there is a Steiner triple system ( S (2, 3, v )) whose largest difference in block sums is within an additive constant of the lower bound.

We demonstrate that certain Johnson-type bounds are asymptotically exact for a variety of classes of codes, namely, constant-composition codes, nonbinary constant-weight codes, group divisible codes, and multiply constant-weight codes. We achieve this via an application of the theory of decomposition of edge-colored digraphs.

We demonstrate that certain Johnson-type bounds are asymptotically exact for a variety of classes of codes, namely, constant-composition codes, nonbinary constant-weight codes and multiply constant-weight codes. This was achieved via an interesting application of the theory of decomposition of edge-colored digraphs.

The use of multiple frequency shift keying modulation with permutation codes addresses the problem of permanent narrowband noise disturbance in a power line communications (PLC) system. Equitable symbol weight codes was recently demonstrated to optimize the performance against narrowband noise in a general coded modulation scheme. This paper establishes the first infinite family of optimal equitable symbol weight codes with code lengths greater than alphabet size and whose relative narrowband noise error-correcting capabilities do not diminish to zero as the length grows. These families of codes meet the Plotkin bound. The construction method introduced is combinatorial and reveals interesting interplay with an extension of the concept of generalized balanced tournament designs from combinatorial design theory.

One peculiarity with deletion-correcting codes is that perfect t-deletion-correcting codes of the same length over the same alphabet can have different numbers of codewords, because the balls of radius t with respect to the Levenshte[Formula: see text]n distance may be of different sizes. There is interest, therefore, in determining all possible sizes of a perfect t-deletion-correcting code, given the length n and the alphabet size q. In this paper, we determine completely the spectrum of possible sizes for perfect q-ary 1-deletion-correcting codes of length three for all q, and perfect q-ary 2-deletion-correcting codes of length four for almost all q, leaving only a small finite number of cases in doubt.

An optimal constant-composition or constant-weight code of weight $w$ has linear size if and only if its distance $d$ is at least $2w-1$. When $d\geq 2w$, the determination of the exact size of such a constant-composition or constant-weight code is trivial, but the case of $d=2w-1$ has been solved previously only for binary and ternary constant-composition and constant-weight codes, and for some sporadic instances. This paper provides a construction for quasicyclic optimal constant-composition and constant-weight codes of weight $w$ and distance $2w-1$ based on a new generalization of difference triangle sets. As a result, the sizes of optimal constant-composition codes and optimal constant-weight codes of weight $w$ and distance $2w-1$ are determined for all such codes of sufficiently large lengths. This solves an open problem of Etzion. The sizes of optimal constant-composition codes of weight $w$ and distance $2w-1$ are also determined for all $w\leq 6$, except in two cases.

Optimal partitioned cyclic difference packings (PCDPs) are shown to give rise to optimal frequency-hopping sequences and optimal comma-free codes. New constructions for PCDPs, based on almost difference sets and cyclic difference matrices, are given. These produce new infinite families of optimal PCDPs (and hence optimal frequency-hopping sequences and optimal comma-free codes). The existence problem for optimal PCDPs in BBZ3m, withmbase blocks of size three, is also solved for allm≠ 8,16 mod 24.

An $N_2$ resolvable Latin square is a Latin square with no $2\times2$ subsquares that also has an orthogonal mate. In this paper we show that $N_2$ resolvable Latin squares exist for all orders n with $n\neq2,4,6,8$.

For a v-set V, let $\mathcal{A}$ be a collection of $r\times c$ arrays with elements in V. A pair $(V,\mathcal{A})$ is called an $r\times 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 $\mathcal{A}$. This design originated from the use of DNA library screening. In this paper, we show the existence of $r\times 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.

Although prone to fabrication error, the nanowire crossbar is a promising candidate compoent for next generation nanometer-scale circuits. In the nanowire crossbar architecture, nanowires are addressed by controlling voltages on the mesowires. For area efficiency, we are interested in the maximum number of nanowires N(m,e) that can be addressed by m mesowires, in the face of up to e fabrication errors. Asymptotically tight bounds on N(m,e) are established in this paper. In particular, it is shown that N(m,e) = Theta(2m/ mepsiv+1/2). Interesting observations are made on the equivalence between this problem and the problem of constructing optimal EC/AUED codes, superimposed distance codes, pooling designs, and diffbounded set systems. Results in this paper also improve upon those in the EC/AUEC codes literature.

In order to reduce the number of add-drop multiplexers (ADMs) in SONET/WDM networks using wavelength add-drop multiplexing, certain graph decompositions can be used to form a “grooming” that specifies the assignment of traffic to wavelengths. When traffic among nodes is all-to-all and uniform, the drop cost of such a decomposition is the sum, over all graphs in the decomposition, of the number of vertices of nonzero degree in the graph. The number of ADMs required is this drop cost. The existence of such decompositions with minimum cost, when every pair of sites employs no more than $\frac{1}{7}$ of the wavelength capacity, is determined within an additive constant. Indeed when the number n of sites satisfies $n \equiv 1$ (mod 3) and $n \neq 19$, the determination is exact; when $n \equiv 0$ (mod 3), $n \not\equiv 18$ (mod 24), and n is large enough, the determination is also exact; and when $n \equiv 2$ (mod 3) and n is large enough, the gap between the cost of the best construction and the cost of the lower bound is independent of n and does not exceed 4.

This correspondence introduces two new constructive techniques to complete the determination of the sizes of optimal$q$-ary codes of constant weight three and distance four.

The concept of group divisible codes, a generalization of group divisible designs with constant block size, is introduced in this paper. This new class of codes is shown to be useful in recursive constructions for constant-weight and constant-composition codes. Large classes of group divisible codes are constructed which enabled the determination of the sizes of optimal constant-composition codes of weight three (and specified distance), leaving only four cases undetermined. Previously, the sizes of constant-composition codes of weight three were known only for those of sufficiently large length.

The radar array problem arises from the need to design frequency hopping sequences with small out-of-phase autocorrelations. It assumes the reflected signals have negligible Doppler shifts, so the correlations are calculated along the time axis only. In this correspondence, a systematic construction for radar arrays is provided by means of homogeneous uniform difference matrices. A systematic construction for properly centered permutation matrices, a special kind of homogeneous uniform difference matrices, is also provided, which partially solves the open problems posed by Zhang and Tu.

The problem of determining extremal hypergraphs containing at most r isomorphic copies of some element of a given hypergraph family was first studied by Boros et al. in 2001. There are not many hypergraph families for which exact results are known concerning the size of the corresponding extremal hypergraphs, except for those equivalent to the classical Turán numbers. In this paper, we determine the size of extremal k-uniform hypergraphs containing at most one pair of 2-intersecting edges for $k\in\{3,4\}$. We give a complete solution when $k=3$ and an almost complete solution (with eleven exceptions) when $k=4$.

Motivated by the connection between graph decompositions and traffic grooming in optical networks, we continue the investigation of the existence problem for $(K_5 \setminus e)$-designs of order n. It is proved that the necessary conditions for the existence of such designs are also sufficient with 3 definite exceptions $(n=9,10,18)$ and 12 possible exceptions with $n=234$ being the largest. This gives a near solution for the long standing problem posed by Bermond et al. in [Ars Combin., 10 (1980), pp. 211–254]. As a consequence, we also give an optimal grooming on n nodes with $C=9$ when such a $(K_5 \setminus e)$-design of order n exists.

We show an interesting pairwise balanced design (PBD)-closure result for the set of lengths of constant-composition codes whose distance and size meet certain conditions. A consequence of this PBD-closure result is that the size of optimal constant-composition codes can be determined for infinite families of parameter sets from just a single example of an optimal code. As an application, the sizes of several infinite families of optimal constant-composition codes are derived. In particular, the problem of determining the size of optimal constant-composition codes having distance four and weight three is solved for all lengths sufficiently large. This problem was previously unresolved for odd lengths, except for lengths seven and eleven.

Off-chip buses account for a significant portion of the total system power consumed in embedded systems. Bus encoding schemes have been proposed to minimize power dissipation, but none has been demonstrated to be optimal with respect to any measure. In this paper, we give the first provably optimal and explicit (polynomial-time constructible) families of memoryless codes for minimizing bit transitions in off-chip buses. Our results imply that having access to a clock does not make a memoryless encoding scheme that minimizes bit transitions more powerful.

Abstract We construct sets of routings in the complete directed graph $\vec{K}_n$ that tolerate up to f failures of nodes or links. These routings are optimal with respect to several desirable criteria. In addition, our routings have minimum (or close to minimum) possible optical indices, which means that wavelengths can be assigned to the directed paths in the routings in an efficient manner. This property is useful in the context of optical networks. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 47–55 2006

SONET/WDM networks using wavelength add-drop multiplexing can be constructed using certain graph decompositions used to form a grooming, consisting of unions of primitive rings. The cost of such a decomposition is the sum, over all graphs in the decomposition, of the number of vertices of nonzero degree in the graph. The existence of such decompositions with minimum cost, when every pair of sites employs no more than $\frac{1}{6}$ of the wavelength capacity, is determined with a finite number of possible exceptions. Indeed, when the number N of sites satisfies $N \equiv 1 \pmod{3}$, the determination is complete, and when $N \equiv 2 \pmod{3}$, the only value left undetermined is N = 17. When $N \equiv 0 \pmod{3}$, a finite number of values of N remain, the largest being N = 2580. The techniques developed rely heavily on tools from combinatorial design theory.

We develop a connection between permutation arrays that are used in powerline communication and well-studied combinatorial objects, mutually orthogonal latin squares (MOLS). From this connection, many new results on permutation arrays can be obtained.

Component based software development is prone to unexpected interaction faults. The goal is to test as many-potential interactions as is feasible within time and budget constraints. Two combinatorial objects, the orthogonal array and the covering array, can be used to generate test suites that provide a guarantee for coverage of all t-sets of component interactions in the case when the testing of all interactions is not possible. Methods for construction of these types of test suites have focused on two main areas. The first is finding new algebraic constructions that produce smaller test suites. The second is refining computational search algorithms to find smaller test suites more quickly. In this paper we explore one method for constructing covering arrays of strength three that combines algebraic constructions with computational search. This method leverages the computational efficiency and optimality of size obtained through algebraic constructions while benefiting from the generality of a heuristic search. We present a few examples of specific constructions and provide some new bounds for some strength three covering arrays.

MOTIVATION: Oligo arrays are important experimental tools for the high throughput measurement of gene expression levels. During production of oligo arrays, it is important to identify any faulty manufacturing step. RESULTS: We describe a practical algorithm for the construction of optimal quality control designs that identify any faulty manufacturing step. The algorithm uses hillclimbing, a search technique from combinatorial optimization. We also present the results of using this algorithm on all practical quality control design sizes. AVAILABILITY: On request from the authors.

This article obtains new difference triangle sets using affine planes. Difference triangle sets have a number of interesting applications in data communications. In these applications, it is desirable to have difference triangle sets with small scopes.

In the manufacture of oligo arrays for DNA hybridization experiments, manufacturing defects must be detected and their position determined. The design of manufacturing protocols for such oligo arrays leads to a combinatorial problem, requiring certain binary codes which have an additional balance property. Constructions using block designs and packings for these codes, within a range of interest in a practical manufacturing application, are developed. The focus is on equireplicate codes, constant weight codes in which every bit position is a one equally often.