---

Design Theory and Coding Theory / Théorie du design et théorie des codes
(Org: John van Rees)

---

FRANK BENNETT, Mount Saint Vincent University, Halifax, Nova Scotia  B3M 2J6
Existence of (v, 5, w*)-PBDs

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 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 conditions are sufficient except possibly for w=53, 133, 293 and 453. For w º 1,5 mod 20, we show the necessary 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.

This is joint work with Yanxun Chang, Gennian Ge, and Malcolm Greig.

ILIYA BLUSKOV, University of Northern British Columbia
Computing "small" designs

I will discuss some computational aspects of finding small designs in connection to results on coverings and balanced incomplete block designs. These include findings from several recent papers, including joint works with J. Abel and M. Greig on (v,k,l) BIBDs with k=8,9; joint work with A. Assaf, F. Bennett and M. Greig on the covering number C(v,5,2) for v=0 mod 4; joint work with R. Bertolo, H. Hämäläinen and F. Santisi on the covering number C(v,k,t,m) and some results on the covering number C₂(v,k,t) for k=6, a parameter of interest to lottery players. I will present some small designs found by either direct constructions or by assuming some structure and then applying level-dependent experimental optimization, a method which proved to be successful in many searches.

ROBERT CRAIGEN, University of Manitoba, Winnipeg, Manitoba
Power Hadamard matrices

Let n be an integer and f a polynomial. A power Hadamard matrix, PH(n,f), is an array, H, of integer powers of an indeterminate, x, with the property that HH^* = nI mod f(x). Here H^* is the matrix obtained from H by performing the transpose and then replacing x with [ 1/(x)].

For example, the following array is a PH(3,1+x+x²):

1 1 1 1 x x2 1 x2 x

Power Hadamard matrices are a simple generalization of Butson Hadamard matrices, which are matrices H whose entries are (complex) roots of unity and HH^*=nI, where H^* is the Hermitian adjoint. That is, BH(n) = PH(n,f), where f is a suitable product of cyclotomic polynomials. Butson Hadamard matrices, in turn, generalize ordinary Hadamard matrices, whose entries are ±1 (square roots of unity). It is also possible to generalize weighing matrices and orthogonal designs along these lines.

I introduced power Hadamard matrices last summer with a group of undergraduate and graduate student research assistants. Among other things, they managed to use these matrices to eliminate the possibility of projective planes of order 12 having a certain type of internal structure. We will discuss this and some other interesing connections between PH's and more classical design-type objects.

DAVID DRAKE, University of Florida, Gainesville, Florida  32611, USA
Nets with and without ovals or hyperovals

A k-arc in a (Bruck) r-net is a set of k points such that each two, but no three are collinear. The existence of a k-arc implies that k £ r+1. A k-arc is called a hyperoval if k=r+1, an oval if k=r. If there is a 7-net of order 10, its extended binary code would contain exactly one word of weight 8 which is not a hyperoval.

There is a 7-net with a hyperoval held by a Desarguesian affine plane P(D) if and only if the division ring D is of characteristic 2 and cardinality at least 8; P(D) holds a 7-net with oval if and only if D contains a root of x³-x²-2x + 1.

There is a 7-net of order n with a hyperoval, and hence with an oval, for every n ³ 63. Let n=f₁¼f_t where each f_i is an odd prime power with f_i ³ 7. Then there is a 7-net of order n without a hyperoval. If also f_i\not º 0, ±1 mod 7 for each i, there is a 7-net of order n without an oval.

HADI KHARAGHANI, University of Lethbridge
A review of Ionin-type designs

The Ionin-Kharaghani conjecture states that:

For any integers h ¹ 0 and m > 0, if q=(2h-1)² is a prime power, then there exists a symmetric design with parameters

æ è  4h2(qm+1-1) q-1 ,(2h2-h)qm,(h2-h)qm ö ø .

This talk is a brief review of the state of this conjecture.

DON KREHER, Michigan Technical University
Computing transverse t-designs

Let P = {X₁,X₂,¼,X_r} be a partition of a set X and let G be an automorphism group of P. We present an algorithm to compute the G-orbits of k-element subsets transverse to the partition P and use it to compute tables of small transverse Steiner quadruple systems. This is joint work with Kimberly A. Lauinge.

CLEMENT LAM, Concordia University
An update on the computer search for a (22,33,12,8,4)-BIBD

(joint work with Richard Bilous, John van Rees, and Larry Thiel)

Amongst block designs, the smallest undecided case is the (22,33,12,8,4)-BIBD. If it exists, then its incidence matrix is contained in a (33,16) doubly-even self-orthogonal code (that does not contain a coordinate of zeros). There are 594 such codes, up to equivalence. It has been theoretically proven that 116 of these codes cannot contain the incidence matrix of such a design. For the remaining 478 codes, an exhaustive clique search may be tried, on the weight 12 words of a code, to determine whether or not it contains such an incidence matrix. We give an update on the progress of this search, and why we may need some volunteers to help finish the search.

ESTHER LAMKEN, 773 Colby Street, San Francisco, California  94134
Skew SOLS-ordered room squares

One of the long open questions about Room squares from the 1960's asks: What is the relationship between orthogonal Latin squares and Room squares? In this talk, I will describe an answer to this old question. Let R be a skew Room square in standard position defined on N È{¥} and let [`(R)] be the skew complement of R. Let L be the array of pairs formed by the superposition of R and [`(R)] with the main diagonal deleted and with main diagonal (i,i) for i Î N. R is said to be SOLS-ordered if the pairs in R and [`(R)] can be ordered so that L is the array of pairs formed by the superposition of a self orthogonal Latin square and its transpose. We show that with a very small number of possible exceptions there exist skew Room squares which can be SOLS-ordered.

BEN LI, University of Manitoba, Winnipeg, Manitoba  R3T 2N2
A parallel algorithm for enumerating covering designs

In this talk, I will describe an algorithm for enumerating covering designs. This basic ideas of this algorithm were first discussed by Francois Margot which incorporate linear programming and isomorphism rejection techniques. I have made several improvements to this algorithm by introducing additional pruning techniques and by parallelizing the algorithm. This algorithm improved the lower bounds for several covering numbers.

GARY MULLEN, Department of Mathematics, The Pennsylvania State University, University Park, Pennsylvania  16802 USA
Sets of partially orthogonal latin squares and projective planes

This is joint work with A.D. Keedwell (University of Surrey).

We investigate the construction of sets of latin squares of a given non-prime power order q which are as close as possible to being mutually orthogonal sets. Using uniform cyclic neofields, for any even q > 2 we are able to construct q-1 latin squares of order q with the property that, when we juxtapose any two of them, we obtain 5q-4 distinct ordered pairs. More precisely, we obtain 4q-3 ordered pairs that occur exactly once, q-1 pairs that occur exactly q-3 times, and q²-5q+4 pairs that do not occur.

Thus for example in the case when q=6 and there is not even a pair of orthogonal latin squares of order 6, we are able to construct 5 latin squares of order 6 so that when any two of them are juxtaposed, we obtain 26 distinct ordered pairs. And when q=10, using a uniform cyclic neofield we are able to construct 9 latin squares of order 10 with the property that when any two of them are juxtaposed we obtain 46 distinct ordered pairs.

It is conjectured, and very likely true, that D-neofields exist for any finite order q except for q=2,6. In cases where a D-neofield exists, one can do even better. For example when q=10, we can construct 9 latin squares of order 10 so that of the total possible \binom92 10² = 3600 possible ordered pairs in a complete set of 9 MOLS of order 10, we obtain 2952 distinct ordered pairs. This represents 82% of the total possible pairs in a complete set.

RON MULLIN, University of Waterloo, Waterloo, Ontario  N2L 3G1
The factorization of certain polynomials in finite fields

The factorization of binomial polynomials over finite fields has application in the theory of error-correcting codes and elsewhere. In this talk we give explicit factorizations of some of these and other polynomials and discuss their connection to some conjectures.

KEVIN PHELPS, Auburn

VERA PLESS, Mathematics Department, University of Illinois at Chicago, Chicago, Illinois  60607-7045, USA
Explicit constructions of families of LDPC codes with girth at least six

(joint work with Jon-Lark Kim, Irina Perepelitsa and Uri Peled)

There are new families of codes which can be decoded by message passing soft-decision decoding. These codes perform very well. This performance seems to depend on characteristics of a graph associated to the code.

LDPC (low density parity check) codes are serious contenders to Turbo codes in terms of decoding performance. One of the main problems in LDPC codes is an explicit construction of such codes whose Tanner graphs have known girth. For a prime power q and an integer m larger than 1, Lazebnik and Ustimenko give an explicit construction of a q-regular bipartite graph D(m,q) on 2q^m vertices, which has girth at least m+5 for odd m. We regard these graphs as Tanner graphs of binary codes LU(m,q). We can determine all the parameters of LU(2,q). We know that their girth is 6 and their diameter is 4. We know that LU(3,q) has girth 8 and diameter 6 and we conjecture its dimension. We find some interesting LDPC codes by our partial row construction.

ROLF REES, Department of Mathematics and Statistics, Memorial University of Newfoundland, St. John's, Newfoundland  A1C 5S7
An application of Skolem sequences to the construction of pairwise balanced designs

We consider the construction of (v,{3,k})-PBDs where v and k are even and where there is at least one block of size 3. Such designs seem to be difficult to construct when v is "small" compared to k (i.e. k^3/2 £ v £ k²). We describe a technique by which Skolem and Skolem-type sequences can be used in an innovative way to construct certain classes of these designs.

JOE YUCAS, Southern Illinois University, Carbondale, Illinois  62901, USA
Paley triple arrays

For odd prime powers, Paley-type constructions of triple arrays are given providing the first infinite family of such arrays.