mwang (12/07/82)
DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF WATERLOO SEMINAR ACTIVITIES Jointly with Department of Combinatorics & Optimization THEORY SEMINAR - Friday, December 17, 1982. Prof. C. J. Colbourn of the University of Saskatchewan will speak on "Directing Triple Sys- tems". TIME: 3:30 PM ROOM: M&C 3007 ABSTRACT A triple system is a collection of 3-element subsets (triples) of a finite set having the property that every 2-element subset appears in the same number, lambda, of triples. Triple systems are combinatorial designs, employed in such applications as the design of experiments and the construction of error- correcting codes. Various researchers have examined "directed" analogues of triple systems, in which tri- ples are 3-element tuples, containing every 2-element tuple the same number of times. It is easy to see that if information about "direc- tions" is omitted from a directed triple system, one obtains an undirected triple system with even lambda. The converse also holds: Janelle Harms and I have shown that every undirected triple system with even lambda can be directed. The proof is constructive, and yields a polynomial time algorithm for construct- ing a directed version of a given undirected triple system. This talk outlines the algorithm for direct- ing, and applications to the constructin of various combinatorial configurations. December 7, 1982