Shifted Transversal Designs and Expander Graphs

Observation : A shifted transversal design (STD) is similar to the adjacency matrix of an (unbalanced) expander graph.

STD(n;q;k) is a matrix construction algorithm that accepts parameters : n,q and k to produce a (qk x n) 0-1 matrix with certain special properties. Each of the n columns has k 1’s in it, which are distributed, one in every q x n block. Each row has usually 1’s in it. Such matrices are very useful as pooling design schemes and error-correcting codes, among other things. The STD algorithm is due to N. Thierry-Mieg.

Expander Graphs are sparse but highly connected graphs. From here, we learn that a bipartite graph H = (X,Y,E) is said to be an ()-expander if |X|=n, |Y|=m, the degree of each node in X is d, and for every , the set of vertices that are adjacent to A satisfies . A higher value of implies a better expansion property.

Rat Poison and Information Theory

Consider this puzzle :

Some scientist-types have a week to throw a party. They have 7 bottles of wine in their cellar. However, the vintage bottles have lost their labels. Of these, 1 bottle was rat poison, but which one ? To test this out, they volunteer their pet rats, but have only 3 such rats. Also it takes a rat about a week to die of the poison. They need to figure out a way to test all 7 bottles using just 3 rats, such that, at the end of the week they know exactly which bottle was rat poison.