An algorithm for completing partials, with an application to the smallest defining sets of the STS(15)

Abstract

We present an algorithm which, when given a collection S of k-subsets of a v-set V and the parameters of a t-(v, k, 1) design, finds all t-(v, k, 1) designs that contain S. We compare our algorithm with an existing general-purpose one, and use it to determine the sizes of smallest defining sets for all 80 Steiner triple systems on 15 points.