Search

For an ordering of the blocks of a design, the point sum of an element is the sum of the indices of blocks containing that element. Block labelling for popularity asks for the point sums to be as equal as possible. For Steiner systems of order v and strength t in general, the average point sum is O (v 2 t - 1) ; under various restrictions on block partitions of the Steiner system, the difference between the largest and smallest point sums is shown to be O (v (t + 1) / 2 log v) . Indeed for Steiner triple systems, direct and recursive constructions are given to establish that systems exist with all point sums equal for more than two thirds of the admissible orders. [ABSTRACT FROM AUTHOR]

Ordering the blocks of a design, the point sum of an element is the sum of the indices of blocks containing that element. Block labelling for popularity asks for the point sums to be as equal as possible. When all point sums are equal, the system is egalitarian; when point sums differ by at most one, it is almost egalitarian. For Steiner quadruple systems, a doubling construction is adapted to establish that an egalitarian S (3 , 4 , v) exists whenever v ≡ 4 , 20 (mod 24) and that an almost egalitarian S (3 , 4 , v) exists whenever v ≡ 8 , 16 (mod 24) and v ≠ 8. [ABSTRACT FROM AUTHOR]

Necessary conditions for existence of a resolvable group divisible design (GDD) with block size 3 and type [ABSTRACT FROM AUTHOR]

Abstract: Grooming uniform all-to-all traffic in optical ring networks with grooming ratio requires the determination of graph decompositions of the complete graph into subgraphs each having at most edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The minimum drop cost is determined for grooming ratio 9. Previously this bound was shown to be met when with two exceptions and eleven additional possible exceptions for , and also when with one exception and one possible exception for . In this paper it is shown that the bound is met for all with four exceptions for and one possible exception for . Using this result, it is further shown that when and is sufficiently large, the bound is also met. [Copyright &y& Elsevier]

A known recursive construction for perfect hash families multiplies the number of factors by q, where q is the largest prime power not exceeding the number of symbols. This is generalized to permit multiplication of the number of factors by powers of q; it is also improved upon by restricting the structure of the ingredient designs. For a perfect hash family of strength t, it may be possible to order its rows so that, for each , the first Ni rows form a perfect hash family of strength . This 'matroshka' ordering underlies a sometimes substantial reduction in the number of rows generated by the recursive construction. Perfect hash families with useful matroshka orderings are generated using linear orthogonal arrays, and with an effective one-row-at-a-time greedy algorithm. [ABSTRACT FROM AUTHOR]

Abstract: Grooming uniform all-to-all traffic in optical ring networks with grooming ratio requires the determination of graph decompositions of the complete graph into subgraphs each having at most edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The minimum possible drop cost is determined for grooming ratio 8, and this cost is shown to be realized with six exceptions, and 37 possible exceptions, the largest being 105. [Copyright &y& Elsevier]

Abstract: A -design of order embeds a given Steiner triple system if there is a subset of points on which the graphs of the design induce the blocks of the original Steiner triple system. It has been established that , and that when equality is met, such a minimum embedding of an STS() exists, except when . Equality only holds when . One natural question is: What is the smallest order such that some STS can be embedded into a -design of order ? We solve the problem for 7 of the 10 congruence classes modulo 30. [Copyright &y& Elsevier]

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 1/7 of the wavelength capacity, is determined within an additive constant. Indeed when the number n of sites satisfies n ≡ 1 (mod 3) and n ≠ 19, the determination is exact; when n ≠ 0 (mod 3), n ≢ 18 (mod 24), and n is large enough, the determination is also exact; and when n ≠ 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]