Combinatorial Theory

A summary of relevant concepts

Definitions and theorems are from the book "Combinatorial Theory" by Marshall Hall, Jr., Blaisdell Publishing Company, Waltham, MA, 1967. Relationships to Perfect-N and to Stearns Method, as well as all errors, are my own.

Definition. A balanced incomplete block design D(b,v,k,r,l) is an arrangement of v distinct objects into b blocks such that each block contains exactly k distinct objects, each object occurs in exactly r different blocks, and every pair of distinct objects occurs in exactly l blocks.

Block Designs D(b,v,k,r,l), where

b: blocks = heats
v: objects = cars
k: objects per block = lanes on track
r: occurrences = heats per car
l: pairing = number of times two cars race each other.

Elementary relations:

bk = vr
r(k-1) = l(v-1)

Perfect-N is concerned with the case where r = nk and b = nv, n is a positive integer.

When n = 1, the Perfect-N charts have b = v and, so, are called symmetric. Any two blocks in a symmetric block design always have exactly l objects (cars) in common. However, not all symmetric designs are Perfect-N, because Perfect-N requires r = nk, and, further, that the blocks may be written as ordered n-tuples in which each object (car) appears the same number of times in each position of the collection of blocks which make up the design.

Derived design and residual design block designs are based on symmetric designs but do not appear to be Perfect-N because they fail to satisfy the requirement that r = nk. (Hall's descriptions of these escape me for now.)

Another category of balanced incomplete block designs is called group-divisible. Each group of blocks contain each of the objects once, so there are v/k blocks in each group. The racing plan called Stearns Method consists of some number of such groups, but not necessarily r groups, i.e. enough to satisfy the bk = vr requirement. In fact, it appears that Stearns Method uses just enough groups to satisfy the racing duration parameter. Other priorities for Stearns Method are to try to have each car race as many other cars as possible and to race in as many lanes as possible. Balanced competition and balanced lane usage, however, are not priorities. (Oops... some Stearns Method charts appear to violate the specifications for "balanced incomplete block designs", so perhaps there is "something else going on in there"...)

Cyclic Characteristics

Definition: A set of k residues D: {a_1,...,a_k} modulo v is called a (v,k,l) difference set if for every d not equivalent to 0 (mod v) there are exactly l ordered pairs (a_i,a_j), a_i, a_j elements of D such that a_i - a_j equivalent to d (mod v).

Theorem: A set of k residues D: {a_1,...a_k} modulo v is a (v,k,l) difference set if and only if the sets B_i: {a_1+i,a_2+i,...,a_k+i} modulo v, i = 0,...,v-1 are a cyclic (v,k,l) block design B.

Every symmetric Perfect-N chart which I had previously created can be replaced by an equivalent cyclic (v,k,l) block design.

When b = nv, where integer n greater than 1, balanced incomplete block designs can sometimes be created from more than one difference set. Design (26,13,3,6,1) may be generated from difference sets [1,3,9] and [2,5,6] mod 13 or from [1,2,5] and [1,3,8] mod 13.