Defining set spectra for designs can have arbitrarily large gaps

Abstract

A set of blocks which is a subset of a unique t-(v, k, lambda) design D is a defining set of D. A defining set is minimal if it does not properly contain a defining set. Define the spectrum of minimal defining sets of D by spec(D) = {vertical bar M vertical bar : M is a minimal defining set of D}. Call h a hole in spec(D) if h is not an element of spec(D), but there are minimal defining sets of D with cardinalities both larger and smaller than h. If spec(D) does not contain a hole, then it is said to be continuous. Previously, the spectra of only a limited number of designs were known and all of these were continuous. The question "whether the spectrum is continuous for all designs" was raised by B. Gray et al. (Discrete Mathematics 261 (2003), 277-284). We describe a new algorithm which finds all minimal defining sets of t-(v, k, lambda) designs. Using this algorithm we investigated the spectra for a variety of small designs, and found several examples of non-continuous spectra. We also derive some theoretical results which enable us to construct an infinite family of designs with arbitrarily large sequences of consecutive holes in their spectra.