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.