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