×

On the spectrum of Steiner \((v, k, t)\) trades. I. (English) Zbl 0959.05014

A \((v,k,t)\) trade \(T=T_1-T_2\) of volume \(m\) consists of two disjoint collections \(T_1\) and \(T_2\) each containing \(m\) \(k\)-subsets (blocks) of some set \(V\), such that every \(t\)-subset is contained in the same number of blocks in \(T_1\) and \(T_2\). If each \(t\)-subset occurs at most once in \(T_1\), then \(T\) is called a Steiner \((k,t)\) trade. The term \((k,t)\) trade is used when \(v\) is not specifically referred to. The spectrum \(S(k,t)\) of Steiner \((k,t)\) trades is defined as the set \(\{m \mid\) there exists a Steiner \((k,t)\) trade of volume \(m\}\). In this paper the authors investigate the spectrum of Steiner trades, with particular reference to the case \(t=2\). The main result is: (1) if \(0<m<2k-2\) or \(m=2k-1\), then \(m \notin S(k,2)\); (2) if \(m \geq 3k-3\), or \(m\) is even and \(2k-2 \leq m \leq 3k-4\), then \(m \in S(k,2)\); (3) a Steiner \((k,2)\) trade with \(m=2k-2\), or \(m=2k\) \((k \neq 3,4)\) has a unique structure. The authors fully determine the spectrum \(S(k,2)\) for \(k=5,6\), and leave just one unresolved case for \(k=7\), namely that of volume \(17\). A generalisation of these results to trades with blocks based on arbitrary simple graphs is presented. Finally, the case \(t>2\) is briefly discussed. Here the problem of determining \(S(k,2)\) appears more difficult as the volume of the smallest Steiner \((k,t)\) trade grows rapidly with \(k\), as the following result by the authors demonstrates: if \(T=T_1-T_2\) is a Steiner \((k,t)\) trade, \(t>1\), then \(m(T) \geq 1 + {{k}\choose {t-1}}\).

MSC:

05B05 Combinatorial aspects of block designs