Recursive constructions for optimal (n,4,2)‐OOCs

In [ 3 ], a general recursive construction for optical orthogonal codes is presented, that guarantees to approach the optimum asymptotically if the original families are asymptotically optimal. A challenging problem on OOCs is to obtain optimal OOCs, in particular with λ > 1. Recently we developed an algorithmic scheme based on the maximal clique problem (MCP) to search for optimal (n, 4, 2)‐OOCs for orders up to n = 44. In this paper, we concentrate on recursive constructions for optimal (n, 4, 2)‐OOCs. While “most” of the codewords can be constructed by general recursive techniques, there remains a gap in general between this and the optimal OOC. In some cases, this gap can be closed, giving recursive constructions for optimal (n, 4, 2)‐OOCs. This is predicated on reducing a series of recursive constructions for optimal (n, 4, 2)‐OOCs to a single, finite maximal clique problem. By solving these finite MCP problems, we can extend the general recursive construction for OOCs in [ 3 ] to obtain new recursive constructions that give an optimal (n · 2^x, 4, 2)‐OOC with x ≥ 3, if there exists a CSQS(n). © 2004 Wiley Periodicals, Inc.     

Optimal (v, 4, 2, 1) optical orthogonal codes with small parameters

Optimal (v, 4,2,1) optical orthogonal codes (OOCs) with v ? 75 and v ≠ 71 are classified up to isomorphism. One (v, 4,2,1) OOC is presented for all v ? 181 , for which an optimal OOC exists. Copyright © 2011 Wiley Periodicals, Inc. J Combin Designs 20:142‐160, 2012     

Optical orthogonal codes and arcs in

We present a new construction for (n,w,λ)-optical orthogonal codes (OOCs). The construction is pleasingly simple, where codewords correspond to arcs, specifically normal rational curves. Moreover, our construction yields for each λ>1 an infinite family of OOCs which are asymptotically optimal (with respect to the Johnson bound).     

Constructions of optimal optical orthogonal codes with weight five

Several direct constructions via skew starters and Weil's theorem on character sum estimates are given in this paper for optimal (gv, 5, 1) optical orthogonal codes (OOCs) where 60 ≤ g ≤ 180 satisfying g ≡ 0 (mod 20) and v is a product of primes greater than 5. These improve the known existence results on optimal OOCs. Especially, we provide an optimal (v, 5, 1)‐OOC for any integer v ≡ 60, 420, 660, 780, 1020, 1140, 1380, 1740 (mod 1800). © 2004 Wiley Periodicals, Inc. J Combin Designs 13: 54–69, 2005.     

Constructions of optimal variable‐weight optical orthogonal codes

Variable‐weight optical orthogonal code (OOC) was introduced by G‐C Yang for multimedia optical CDMA systems with multiple quality of service (QoS) requirement. In this article, new infinite classes of optimal (u, W, 1, {1/2, 1/2})‐OOCs are obtained for W={3, 4}, {3, 5} and {3, 6}. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 274–291, 2010     

4‐*GDDs(3n) and generalized Steiner systems GS(2, 4, v, 3)

Generalized Steiner systems GS(2, k, v, g) were first introduced by Etzion and used to construct optimal constant weight codes over an alphabet of size g + 1 with minimum Hamming distance 2k ? 3, in which each codeword has length v and weight k. As to the existence of a GS(2, k, v, g), a lot of work has been done for k = 3, while not so much is known for k = 4. The notion k‐*GDD was first introduced and used to construct GS(2, 3, v, 6). In this paper, singular indirect product (SIP) construction for GDDs is modified to construct GS(2, 4, v, g) via 4‐*GDDs. Furthermore, it is proved that the necessary conditions for the existence of a 4‐*GDD(3ⁿ), namely, n ≡ 0, 1 (mod 4) and n ≥ 8 are also sufficient. The known results on the existence of a GS(2, 4, v, 3) are then extended. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 381–393, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10047     

Some combinatorial constructions for optimal perfect deletion-correcting codes

There are two kinds of perfect t-deletion-correcting codes of length k over an alphabet of size v, those where the coordinates may be equal and those where all coordinates must be different. We call these two kinds of codes T*(k − t, k, v)-codes and T(k − t, k, v)-codes respectively. The cardinality of a T(k − t, k, v)-code is determined by its parameters, while T*(k − t, k, v)-codes do not necessarily have a fixed size. Let N(k − t, k, v) denote the maximum number of codewords in any T*(k − t, k, v)-code. A T*(k − t, k, v)-code with N(k − t, k, v) codewords is said to be optimal. In this paper, some combinatorial constructions for optimal T*(2, k, v)-codes are developed. Using these constructions, we are able to determine the values of N(2, 4, v) for all positive integers v. The values of N(2, 5, v) are also determined for almost all positive integers v, except for v = 13, 15, 19, 27 and 34.      

Upper bounds on the general covering number Cλ(v,k, t,m)

A collection of k‐subsets (called blocks) of a v‐set X (v) = {1, 2,…, v} (with elements called points) is called a t‐(v, k, m, λ) covering if for every m‐subset M of X (v) there is a subcollection of with such that every block K ∈ has at least t points in common with M. It is required that v ≥ k ≥ t and v ≥ m ≥ t. The minimum number of blocks in a t‐(v, k, m, λ) covering is denoted by C_λ(v, k, t, m). We present some constructions producing the best known upper bounds on C_λ(v, k, t, m) for k = 6, a parameter of interest to lottery players. © 2004 Wiley Periodicals, Inc.     

Resolvable packings of Kv with K2 × Kc's

The study of resolvable packings of K_v with K_r × K_c's is motivated by the use of DNA library screening. We call such a packing a (v, K_r × K_c, 1)‐RP. As usual, a (v, K_r × K_c, 1)‐RP with the largest possible number of parallel classes (or, equivalently, the largest possible number of blocks) is called optimal. The resolvability implies v ≡ 0 (mod rc). Let ρ be the number of parallel classes of a (v, K_r × K_c, 1)‐RP. Then we have ρ ≤ ?(v‐1)/(r + c ? 2)?. In this article, we present a number of constructive methods to obtain optimal (v, K₂ × K_c, 1)‐RPs meeting the aforementioned bound and establish some existence results. In particular, we show that an optimal (v, K₂ × K₃, 1)‐RP meeting the bound exists if and only if v ≡ 0 (mod 6). © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 177–189, 2009     

The equivalence between optimal detecting arrays and super-simple OAs

The notion of a detecting array (DTA) was proposed, recently, by Colbourn and McClary in their research on software interaction tests. Roughly speaking, testing with a (d, t)−DTA(N, k, v) can locate d interaction faults and detect whether there are more than d interaction faults. In this paper, we establish a general lower bound on sizes of DTAs and explore an equivalence between optimal DTAs and super-simple orthogonal arrays (OAs). Taking advantage of this equivalence, a great number of DTAs are constructed, which are all optimal in the sense of their sizes. In particular, an optimal (2, t)−DTA(N, 5, v) of strength t = 2 or 3 is shown to exist whenever v ≥ 3 excepting (t, v) ? {(2, 3), (2, 6),(3, 4), (3, 6)}{(t, v) \in \{(2, 3), (2, 6),(3, 4), (3, 6)\}} .     

Generalized Steiner systems GS4 (2, 4, v,g) for g = 2, 3, 6

Generalized Steiner systems GS_d(t, k, v, g) were first introduced by Etzion and used to construct optimal constant‐weight codes over an alphabet of size g + 1 with minimum Hamming distance d, in which each codeword has length v and weight k. Much work has been done for the existence of generalized Steiner triple systems GS(2, 3, v, g). However, for block size four there is not much known on GS_d(2, 4, v, g). In this paper, the necessary conditions for the existence of a GS_d(t, k, v, g) are given, which answers an open problem of Etzion. Some singular indirect product constructions for GS_d(2, k, v, g) are also presented. By using both recursive and direct constructions, it is proved that the necessary conditions for the existence of a GS₄(2, 4, v, g) are also sufficient for g = 2, 3, 6. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 401–423, 2001     

Semicyclic 4-GDDs and related two-dimensional optical orthogonal codes

The existence problem for a semicyclic group divisible design (SCGDD) of type m ⁿ with block size 4 and index unity, denoted by 4-SCGDD, has been studied for any odd integer m to construct a kind of two-dimensional optical orthogonal codes (2-D OOCs) with the AM-OPPW (at most one-pulse per wavelength) restriction. In this paper, the existence of a 4-SCGDD of type m ⁿ is determined for any even integer m, with some possible exceptions. A complete asymptotic existence result for k-SCGDDs of type m ⁿ is also obtained for all larger k and odd integer m. All these SCGDDs are used to derive new 2-D OOCs with the AM-OPPW restriction, which are optimal in the sense of their sizes.     

Constructions for generalized Steiner systems <Emphasis Type="Italic">GS</Emphasis>(3, 4, <Emphasis Type="Italic">v</Emphasis>, 2)

Generalized Steiner systems GS (3, 4, v, 2) were first discussed by Etzion and used to construct optimal constant weight codes over an alphabet of size three with minimum Hamming distance three, in which each codeword has length v and weight four. Not much is known for GS (3, 4, v, 2)s except for a recursive construction and two small designs for v = 8,10 given by Etzion. In this paper, more small designs are found by computer search and also given are direct constructions based on finite fields and rotational Steiner quadruple systems and recursive constructions using three-wise balanced designs. Some infinite families are also obtained.      

New results on optimal (<Emphasis Type="Italic">v</Emphasis>, 4, 2, 1) optical orthogonal codes

We investigate further the existence question regarding optimal (v, 4, 2, 1) optical orthogonal codes begun in Momihara and Buratti (IEEE Trans Inform Theory 55:514–523, 2009). We give some non-existence results for infinitely many values of v ≡ ± 3 (mod 9) and several explicit constructions for infinite classes of perfect optical orthogonal codes.     

Some Infinite Classes of Optimal (v, {3, 4}, 1, Q)-OOCs with {Q \in \{(\frac {1}{3}, \frac {2}{3}), (\frac {2}{3}, \frac{1}{3})\}}

Variable-weight optical orthogonal code (OOC) was introduced by Yang for multimedia optical CDMA systems with multiple quality of service requirements. It is proved that optimal (v, {3, 4}, 1, (1/2, 1/2))-OOCs exist for some complete congruence classes of v. In this paper, for ${Q \in \{(1/3, 2/3), (2/3, 1/3)\}}$ , by using skew starters, it is also proved that optimal (v, {3, 4}, 1, Q)-OOCs exist for some complete congruence classes of v.     

Alternating groups and flag‐transitive 2‐(v,k, 4) symmetric designs

In this article, we study the classification of flag‐transitive, point‐primitive 2‐ (v, k, 4) symmetric designs. We prove that if the socle of the automorphism group G of a flag‐transitive, point‐primitive nontrivial 2‐ (v, k, 4) symmetric design ?? is an alternating group A_n for n≥5, then (v, k) = (15, 8) and ?? is one of the following: (i) The points of ?? are those of the projective space PG(3, 2) and the blocks are the complements of the planes of PG(3, 2), G = A₇ or A₈, and the stabilizer G_x of a point x of ?? is L₃(2) or AGL₃(2), respectively. (ii) The points of ?? are the edges of the complete graph K₆ and the blocks are the complete bipartite subgraphs K_{2, 4} of K₆, G = A₆ or S₆, and G_x = S₄ or S₄ × Z₂, respectively. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:475‐483, 2011     

On the chromatic numbers of Steiner triple systems

Geometric properties are used to determine the chromatic number of AG(4, 3) and to derive some important facts on the chromatic number of PG(n, 2). It is also shown that a 4-chromatic STS(v) exists for every admissible order v ≥ 21. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 1–10, 1999     

The spectrum of equitable, 4‐chromatic Steiner quadruple systems

A Steiner quadruple system of order v (briefly an SQS(v)) is a pair (X, ) with |X| = v and a set of quadruples taken from X such that every triple in X is in a unique quadruple in . Hanani [Canad J Math 12 (1960), 145–157] showed that an SQS(v) exists if and only if v is {admissible}, that is, v = 0,1 or v ≡ 2,4 (mod 6). Each SQS(v) has a chromatic number when considered as a 4‐uniform hypergraph. Here we show that a 4‐chromatic SQS(v) exists for all admissible v ≥ 20, and that no 4‐chromatic SQS(v) exists for v < 20. Each system we construct admits a proper 4‐coloring that is equitable, that is, any two color classes differ in size by at most one. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 369–392, 2007     

Covering arrays of strength 3 and 4 from holey difference matrices

A covering array CA(N; t, k, v) is an N × k array with entries from a set X of v symbols such that every N × t sub-array contains all t-tuples over X at least once, where t is the strength of the array. The minimum size N for which a CA(N; t, k, v) exists is called the covering array number and denoted by CAN(t, k, v). Covering arrays are used in experiments to screen for interactions among t-subsets of k components. One of the main problems on covering arrays is to construct a CA(N; t, k, v) for given parameters (t, k, v) so that N is as small as possible. In this paper, we present some constructions of covering arrays of strengths 3 and 4 via holey difference matrices with prescribed properties. As a consequence, some of known bounds on covering array number are improved. In particular, it is proved that (1) CAN(3, 5, 2v) ≤ 2v ²(4v + 1) for any odd positive integer v with gcd(v, 9) ≠ 3; (2) CAN(3, 6, 6p) ≤ 216p ³ + 42p ² for any prime p > 5; and (3) CAN(4, 6, 2p) ≤ 16p ⁴ + 5p ³ for any prime p ≡ 1 (mod 4) greater than 5.     

Some new bounds for the maximum number of vertex colorings of a (v,e)-graph

Let f(v, e, λ) denote the maximum number of proper vertex colorings of a graph with v vertices and e edges in λ colors. In this paper we present some new upper bounds for f(v, e, λ). In particular, a new notion of pseudo-proper colorings of a graph is given, which allows us to significantly improve the upper bounds for f(v, e, 3) given by Lazebnik and Liu in the case where e > v²/4. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 115–128, 1998