E-best discrepancy matrices

This page gives graphs corresponding to all E-best discrepancy matrices (up to isomorphism) of order v<=15 for each possible row sum (i.e. concurrence excess) q>0. Also included are sub-optimal matrices as described below. A brief description of discrepancy matrices, their correspondence to graphs, and their function in determining optimal block designs, will be given here. For details see the paper Optimal Incomplete Block Designs. For E-optimal block designs based on these graphs, see the catalog of E-Optimal Block Designs by Concurrence Excess.

A discrepancy matrix is an symmetric, integer-valued matrix with zero diagonal and constant row sums q. The m-complement of a discrepancy matrix is found by replacing each and every off-diagonal entry e by m-e. If a discrepancy matrix of order v has maximum entry m, then its m-complement is the adjacency matrix for an undirected graph with no loops and with constant valency m(v-1)-q. If an undirected graph with no loops and constant valency has at most t edges connecting any two vertices (and t edges do connect some pair), then it is said to be t-regular. All discrepancy matrices cataloged here have minimum entry 0 or -1, and so each or its m-complement is equivalent to a t-regular graph for t = m or m+1, respectively.

A t-regular graph is equivalent to an equireplicate, binary block design with block size k=2. If entry (i,i') in the adjacency matrix is e, then there are e blocks containing treatments i and i'. As each (or its m-complement) corresponds to a t-regular graph for some t, discrepancy matrices in this catalog are stored as block designs with k=2. Complementation information for each is provided in the notes field.

For an incomplete block design (k<v=number of treatments), a discrepancy matrix describes departure of treatment concurrences from complete symmetry in that design. E-best discrepancy matrices describe departures that assure an E-optimal design within the binary, equireplicate class. For all matrices here, E-optimality of any associated block design in fact holds over the entire class including nonbinary and unequally replicated designs, provided k is greater than 2. Again, details may be found in Optimal Incomplete Block Designs.

For k=2, the general result for E-optimality in the binary, equireplicate class can currently be strengthened in only some cases. Interestingly, for k=2, discrepancy matrices directly describe not just E-optimal information matrices, but the designs themselves. Given b (number of blocks), v, and k=2 such that bk is a multiple of v, let lambda be the integer part of bk(k-1)/v(v-1)=2b/v(v-1). Then for discrepancy matrix D, the number of blocks containing treatments i and i' is the (i,i') entry in the matrix D+lambda (keep zeros on the diagonal). This fails only if lambda=0 and D contains a -1 (again, all matrices here have smallest element no less than -1). Whenever a list of E-best discrepancy matrices fails to have a member with smallest element 0, the best subject to having all nonegative entries has been determined, and all matrices as E-good or better than that matrix have also been included. Consequently, this catalog solves the E-optimality problem for k=2 and v<=15 within the binary, equireplicate class.

For some other values of v,b,k with k>2 no design exists for any of the corresponding E-best discrepancy matrices. In some cases the best discrepancy matrix for which a design does exist has been determined, and all matrices as good as or better than that matrix have been included.

The lists of designs are in DTRS external representation protocol version 2.0 format, compressed by bzip2. Each file has content type a, which means that all E-optimal discrepancy matrices (up to isomorphism) with the given (v,q) are represented as graphs/block designs in that file. Additional matrices are included in some files as described above; the number of extra matrices is denoted by x. Each file also has content type g, which means that each design in that file has the <automorphism_group> subtree.

The matrices (designs) in each file are ordered by E-value. No other ordering should be assumed. Individuals wishing to download the discrepancy matrices directly (as matrices rather than as graphs/block designs) can obtain them in R format here. The two catalogs maintain the same ordering.

This page constructed with joint support from the U.K. Engineering and Physical Sciences Research Council and the U.S. National Science Foundation.

Number of files = 63

Last updated: 2005-09-09 00:22:12.691048